第八章 图与网络分析.ppt

第八章第八章 图与网络分析图与网络分析l一、图的概念：一、图的概念：1 1、图：、图：点和线所组成的图形，记为点和线所组成的图形，记为G=(V,E)，其中，其中V是是点的集合，点的集合，E是边的集合。是边的集合。2、端点、关联边：、端点、关联边：联联结结点点vi,vj的的边边记记作作e=(vi,vj)，称称vi,vj为为e的的端端点点，也也称称e为为vi,vj的关联边。的关联边。、相邻点、相邻边：、相邻点、相邻边：具具有有同同一一条条关关联联边边的的点点为为相相邻邻点点，具具有有公公共共端端点点的的边边为为相邻边。相邻边。4、环：、环：一条边的两个端点相同，则称该边为环（自回路）。一条边的两个端点相同，则称该边为环（自回路）。6.1 6.1 图与网络的基本概念图与网络的基本概念25、多重边：、多重边：若两端之间有多于一条边相关联，称这些边为多重边。若两端之间有多于一条边相关联，称这些边为多重边。6、简简单单图图与与多多重重图图：不不含含环环和和多多重重边边的的图图称称为为简简单单图图，无无环环但但含有多重边的图称为多重图。含有多重边的图称为多重图。7、次：、次：点点v的关联边个数称为点的关联边个数称为点v的次，记作的次，记作d(v)。8、悬挂点、悬挂边：、悬挂点、悬挂边：称次为称次为1的点为悬挂点，悬挂点所关联的边为悬挂边。的点为悬挂点，悬挂点所关联的边为悬挂边。v4v3v1v2e1e2e3e4e5e63定理：定理：图G=(V,E)中，所有点的次数之和等于边数的两倍。中，所有点的次数之和等于边数的两倍。二、连通图二、连通图1、链、圈：、链、圈：在无向图在无向图G=(V,E)，称一个点和边交替的序列，称一个点和边交替的序列vi1,ei1,vi2,ei2,vit-1,vit为连接为连接vi1和和vit的一条链。的一条链。简记为简记为vi1,vi2,vit。其中。其中eik=(vik,vik+1),k=1,2,t-1。点边序列中没有重复的点称为点边序列中没有重复的点称为初级链。初级链。若链首尾两端点重合，则称为若链首尾两端点重合，则称为圈。圈。v6v5v4v3v2v1e1e5e4e3e2e6e7e8e9e10S1=v6,v5,v1,v5,v4,v3S2=v6,v5,v1,v4,v342、连连通通图图：如如果果图图中中任任意意两两点点间间至至少少有有一一条条链链相相连连，则则称此图为连通图。称此图为连通图。任任何何一一个个连连通通图图都都可可以以分分为为若若干干个个连连通通子子图图，每每个个连连通通子子图称为由原图的分图。图称为由原图的分图。5例例2、有有5名运动员参加游泳比赛，问如何安排比赛，才能名运动员参加游泳比赛，问如何安排比赛，才能 使每位运动员都不连续地参加比赛？使每位运动员都不连续地参加比赛？运动员运动员50m仰泳仰泳50m蛙泳蛙泳100m蝶泳蝶泳100m自由泳自由泳200m自由泳自由泳甲甲乙乙丙丙丁丁戊戊6三、子图：三、子图：v3e1v1v2e2e3e4e6v2e3e4v3v3v1v2e2e3e47四、有向图：四、有向图：1、弧、有向图：、弧、有向图：带有方向的边称为弧，记作带有方向的边称为弧，记作a=(vi,vj)。由一些由一些点点和和弧弧组成的集合称为有向图，记作组成的集合称为有向图，记作D=(V,A)。A表示表示G中弧的集合。中弧的集合。、路：、路：在在有有向向图图D=(V,A)中中，称称链链vi1,vi2,vit为为一一条条从从vi1到到vit的的路。若路。若vi1=vit，则称之为回路。，则称之为回路。S1=v6,v5,v1,v5,v4,v3 S2=v1,v5,v1v6v5v4v3v2v1e1e5e4e3e2e6e7e8e9e1086.2 6.2 树与最小生成树树与最小生成树l一、树的概念：一、树的概念：l树：无圈的连通图。树：无圈的连通图。l二、树的性质：二、树的性质：l（1）树枝数等于顶点数减）树枝数等于顶点数减1；l（2）树的任意两个顶点之间有且仅有一条初级链。）树的任意两个顶点之间有且仅有一条初级链。l（3）去掉树的任一树枝，便得到一个非连通图；）去掉树的任一树枝，便得到一个非连通图；l（4）在树中任意两个顶点间添上一条边，恰好得到一）在树中任意两个顶点间添上一条边，恰好得到一 l 个初级圈。个初级圈。l（5）在所有连通的生成子图中，生成树的边数最少。）在所有连通的生成子图中，生成树的边数最少。9l三、根树（有向树）：三、根树（有向树）：lD=(V,A)中，中，v到到D的任一顶点都有路，则的任一顶点都有路，则v称为称为D的根，的根，D称为以称为以v为根的根树或有向树。为根的根树或有向树。l四、图的生成树：四、图的生成树：v6v5v4v3v2v1v6v5v4v3v2v110定理定理2：图G有生成树的充要条件是图有生成树的充要条件是图G是连通图。是连通图。寻找生成树的方法：寻找生成树的方法：、破圈法：、破圈法：在连通图中任取一个圈，去掉圈上的任意一条在连通图中任取一个圈，去掉圈上的任意一条 边，对余下的图重复这个步骤，直至无圈为止。边，对余下的图重复这个步骤，直至无圈为止。、避圈法：、避圈法：每次增加一条边，且与已有边不构成圈，直至恰每次增加一条边，且与已有边不构成圈，直至恰 有有p-1条边为止。条边为止。v6v5v4v3v2v111例、例、下图是某建筑物的平面图，要求在其内部从每一房下图是某建筑物的平面图，要求在其内部从每一房间都能走到别的所有的房间，问至少要在墙上开多少门？间都能走到别的所有的房间，问至少要在墙上开多少门？试给出一个开门的方案。试给出一个开门的方案。一一二二三三四四五五六六七七八八九九一一二二三三四四五五六六七七八八九九一一二二三三四四五五六六七七八八九九126.3 6.3 最小树问题最小树问题一、赋权图：一、赋权图：与点或边有关的某些与点或边有关的某些数量指标数量指标，通常称之为，通常称之为“权权”。定义：定义：图图G中中,如果每条边如果每条边(弧弧)(vi,vj)都被赋予一个权数都被赋予一个权数wij,则称则称G为赋权图为赋权图.权可以表示为：权可以表示为：距离、费用、通过能力（数量）等。距离、费用、通过能力（数量）等。与无向图和有向图相对应，赋权图可分为无向赋权图和与无向图和有向图相对应，赋权图可分为无向赋权图和有向赋权图，分别记为有向赋权图，分别记为G=(V,E,W)和和D=(V,A,W)。13二、最小生成树（最小树）：二、最小生成树（最小树）：定义：定义：在给定连通赋权图在给定连通赋权图G=(V,E,W)中，求中，求G的生成树的生成树T=(V,E)，使，使E 各边权各边权Wij(0)的总和最小的问题称为最的总和最小的问题称为最小树问题。其数学模型为：小树问题。其数学模型为：其中其中T*称为最小树。称为最小树。许许多多网网络络问问题题都都可可归归结结为为最最小小树树问问题题，如如设设计计长长度度最最小小的的公公路路网网把把若若干干城城市市联联通通；设设计计用用料料最最省省的的电电话话线线网网把把有关单位联系起来。有关单位联系起来。14求最小树的方法：求最小树的方法：、破圈法、破圈法(管梅谷算法管梅谷算法)：（）先先从从图图G任任取取一一个个圈圈，并并从从圈圈中中去去掉掉一一条条权权最最大大的的边边。若在同一圈中有几条都是权最大边，则任选其中一边去掉。若在同一圈中有几条都是权最大边，则任选其中一边去掉。（）在余下的子圈中，重复上述步骤，直至没有圈止。（）在余下的子圈中，重复上述步骤，直至没有圈止。、避圈法、避圈法(Kruskal算法算法)：开始选一条权最小的边，以后每开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够直至选够q1条边止。条边止。v2v1v4v322344546v5v2v1v4v32234v515例、例、今要在七个城市之间修筑一个公路网，每个城市之间今要在七个城市之间修筑一个公路网，每个城市之间的公路修筑费用就是各条边上的权，试求总修筑费用最小的的公路修筑费用就是各条边上的权，试求总修筑费用最小的公路网。公路网。v1v4v7v6v5v3v28567632445310v1v4v7v6v5v3v2324453166.4 6.4 最短路问题最短路问题 最最短短路路问问题题是是网网络络理理论论中中应应用用最最广广泛泛的的问问题题之之一一，许许多多优优化化问问题题可可以以使使用用这这个个模模型型，如如管管道道铺铺设设，设设备备更更新新，线路安排等。线路安排等。给给定定D=(V,A,W)，其其中中wij W，表表示示弧弧(vi,vj)的的权权（可可以以是是费费用用、时时间间、距距离离等等）。设设vs和和vt是是D中中任任意意两两顶顶点点，求一条路，使它是从求一条路，使它是从vs到到vt的所有路中总权最小的路。的所有路中总权最小的路。其数学模型为：其数学模型为：17求最短路的狄克斯特求最短路的狄克斯特DijkstraDijkstra标号法（标号法（W Wijij 0 0）1、基基于于以以下下原原理理：若若序序列列vs,vi1,vik,vt是是从从vs到到vt的的最最短路，则序列短路，则序列vs,vi1,vik必为从必为从vs到到vik的最短路。的最短路。2、Dijkstra标号法的基本思想是采用标号法的基本思想是采用两种标号两种标号：T标标号号与与P标标号号，T标标号号为为临临时时性性标标号号(Temporary Label)，P标号为永久性标号标号为永久性标号(Permanent Label)。从从vs开开始始，逐逐步步向向外外探探寻寻最最短短路路。给给vi点点P标标号号时时，表表示示从从vs到到vi点点的的最最短短路路权权，vi的的标标号号不不再再改改变变。给给vi点点T标标号号时时，表表示示从从vs到到vi点点的的最最短短路路权权上上界界的的估估计计。凡凡没没有有得得到到P标标号号的的点点都都有有T标标号号。标标号号法法每每一一步步都都是是把把某某一一T标标号号点点改改为为P标标号号，当当终终点点vt得得到到P标标号号时时，计计算算全全部部结结束束。如如果果点点vj不能由不能由T标号变为标号变为P标号，则说明标号，则说明vs到到vj不存在路。不存在路。18 3、步骤：、步骤：(1)给给vs以以P标号，标号，P(vs)=0，其余各点给，其余各点给T标号，且标号，且 T(vi)=+。(2)若若vi点为刚得到点为刚得到P标号的点，考虑标号的点，考虑T标号点标号点vj,(vi,vj)A。对对vj的的T标号进行如下的更改：标号进行如下的更改：T(vj)=minT(vj),P(vi)+wij (3)比较所有具有比较所有具有T标号点，把最小者改为标号点，把最小者改为P标号，即：标号，即：P(vjo)=minT(vj)vj为为T标号标号 若全部点均为若全部点均为P标号。则停止。否则以标号。则停止。否则以vjo代代vi，返回，返回(2)19v6v5v4v3v2v1v8v7356117423521695（1）P(v1)=0,T(vi)=+,i=2,3,4,5,6,7,8 T(v2)=min+,0+3=3，k(v2)=v1 T(v3)=min+,0+5=5，k(v3)=v1 T(v4)=min+,0+6=6，k(v4)=v1（2）P(v2)=3 T(v3)=min5,3+1=4，k(v3)=v2 T(v5)=min+,3+7=10，k(v5)=v2 T(v6)=min+,3+4=7，k(v4)=v220v6v5v4v3v2v1v8v7356117423521695（3）P(v3)=4 T(v4)=min6,4+1=5，k(v4)=v3 T(v6)=min7,4+2=6，k(v6)=v3（4）P(v4)=5 T(v6)=min6,5+3=6，k(v6)=v3 T(v7)=min+,5+5=10，k(v7)=v4（5）P(v6)=6 T(v5)=min10,6+2=8，k(v5)=v6 T(v7)=min10,6+1=7，k(v7)=v6 T(v8)=min+,6+9=15，k(v8)=v621v6v5v4v3v2v1v8v7356117423521695（6）P(v7)=7 T(v8)=min15,7+5=12，k(v8)=v7（7）P(v5)=8 T(v8)=min12,8+6=12，k(v8)=v7（8）P(v8)=12（9）反向追踪找最短路径：反向追踪找最短路径：v vv vv vv vv vv v22