【学习】第八章图与网络分析

1、整理课件1AB例例1、哥尼斯堡七桥问题、哥尼斯堡七桥问题BCAD整理课件2l一、图的概念：一、图的概念：1 1、图：、图：点和线所组成的图形，记为点和线所组成的图形，记为G=(V,E)，其中，其中V是是点的集合，点的集合，E是边的集合。是边的集合。2、端点、关联边：、端点、关联边：联结点联结点vi,vj的边记作的边记作e=(vi,vj)，称，称vi,vj为为e的端点，也称的端点，也称e为为vi,vj的关联边。的关联边。、相邻点、相邻边：、相邻点、相邻边：具有同一条关联边的点为相邻点，具有公共端点的边为具有同一条关联边的点为相邻点，具有公共端点的边为相邻边。相邻边。4、环：、环：一条边的两个端点

2、相同，则称该边为环（自回路）。一条边的两个端点相同，则称该边为环（自回路）。整理课件35、多重边：、多重边：若两端之间有多于一条边相关联，称这些边为多重边。若两端之间有多于一条边相关联，称这些边为多重边。 6、简单图与多重图：、简单图与多重图：不含环和多重边的图称为简单图，无环但不含环和多重边的图称为简单图，无环但含有多重边的图称为多重图。含有多重边的图称为多重图。7、次：、次：点点v的关联边个数称为点的关联边个数称为点v的次，记作的次，记作d(v)。8、悬挂点、悬挂边：、悬挂点、悬挂边：称次为称次为1的点为悬挂点，悬挂点所关联的边为悬挂边。的点为悬挂点，悬挂点所关联的边为悬挂边。v4v3v1

3、v2e1e2e3e4e5e6整理课件4定理：定理： 图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。点边序列中没有重复的点称为点边序列中没有重复的点称为初级链。初级链。若链首尾两端点重合，则称为若链首尾两端点重合，则称为圈。圈。v6v5v4v3

4、v2v1e1e5e4e3e2e6e7e8e9e10S1=v6,v5,v1,v5,v4,v3S2=v6,v5,v1,v4,v3整理课件52、连通图：、连通图：如果图中任意两点间至少有一条链相连，则如果图中任意两点间至少有一条链相连，则称此图为连通图。称此图为连通图。任何一个连通图都可以分为若干个连通子图，每个连通子任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原图的分图。图称为由原图的分图。整理课件6例例2、有有5名运动员参加游泳比赛，问如何安排比赛，才能名运动员参加游泳比赛，问如何安排比赛，才能 使每位运动员都不连续地参加比赛？使每位运动员都不连续地参加比赛？ 运动员运动员50m仰

5、泳仰泳50m蛙泳蛙泳100m蝶泳蝶泳100m自由泳自由泳200m自由泳自由泳甲甲乙乙丙丙丁丁戊戊整理课件7三、子图：三、子图：的子图。的子图。是是则称则称，），如果），如果（）（设有两个图设有两个图212121222111GGEEVVE,VG,E,VG的的真真子子图图。是是，则则称称，如如果果212121GGEEVV。的的生生成成子子图图（部部分分图图）是是，则则称称，如如果果212121GGEEVVv3e1v1v2e2e3e4e6v2e3e4v3v3v1v2e2e3e4整理课件8四、有向图：四、有向图：1、弧、有向图：、弧、有向图：带有方向的边称为弧，记作带有方向的边称为弧，记作a= (vi

6、,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,v1v6v5v4v3v2v1e1e5e4e3e2e6e7e8e9e10整理课件9l一、树的概念：一、树的概念：l树：无圈的连通图。树：无圈的连通图。l二、树的性质：二、树的性质：l（1）树枝数等于顶点数减）树枝数等于顶点数减

7、1；l（2）树的任意两个顶点之间有且仅有一条初级链。）树的任意两个顶点之间有且仅有一条初级链。l（3）去掉树的任一树枝，便得到一个非连通图；）去掉树的任一树枝，便得到一个非连通图；l（4）在树中任意两个顶点间添上一条边，恰好得到一）在树中任意两个顶点间添上一条边，恰好得到一 l 个初级圈。个初级圈。l（5）在所有连通的生成子图中，生成树的边数最少。）在所有连通的生成子图中，生成树的边数最少。整理课件10l三、根树（有向树）：三、根树（有向树）：lD=(V,A)中，中，v到到D的任一顶点都有路，则的任一顶点都有路，则v称为称为D的根，的根，D称为以称为以v为根的根树或有向树。为根的根树或有向树。

8、l四、图的生成树：四、图的生成树：的生成树。的生成树。为为）是树，则称）是树，则称（）的生成子图，如果）的生成子图，如果（）是图）是图（设图设图GTE,VTE,VGE,VTv6v5v4v3v2v1v6v5v4v3v2v1整理课件11定理定理2： 图G有生成树的充要条件是图有生成树的充要条件是图G是连通图。是连通图。寻找生成树的方法：寻找生成树的方法：、破圈法：、破圈法：在连通图中任取一个圈，去掉圈上的任意一条在连通图中任取一个圈，去掉圈上的任意一条 边，对余下的图重复这个步骤，直至无圈为止。边，对余下的图重复这个步骤，直至无圈为止。、避圈法：、避圈法：每次增加一条边，且与已有边不构成圈，直至恰

9、每次增加一条边，且与已有边不构成圈，直至恰 有有p-1条边为止。条边为止。v6v5v4v3v2v1整理课件12例、例、下图是某建筑物的平面图，要求在其内部从每一房下图是某建筑物的平面图，要求在其内部从每一房间都能走到别的所有的房间，问至少要在墙上开多少门？间都能走到别的所有的房间，问至少要在墙上开多少门？ 试给出一个开门的方案。试给出一个开门的方案。 一一二二三三四四五五六六七七八八九九一一二二三三四四五五六六七七八八九九一一二二三三四四五五六六七七八八九九整理课件13一、赋权图：一、赋权图：与点或边有关的某些与点或边有关的某些数量指标数量指标，通常称之为，通常称之为“权权”。定义：定义：图图

10、G中中,如果每条边如果每条边(弧弧) (vi,vj)都被赋予一个权数都被赋予一个权数wij, 则称则称G为赋权图为赋权图. 权可以表示为：权可以表示为：距离、费用、通过能力（数量）等。距离、费用、通过能力（数量）等。与无向图和有向图相对应，赋权图可分为无向赋权图和与无向图和有向图相对应，赋权图可分为无向赋权图和有向赋权图，分别记为有向赋权图，分别记为G=(V,E,W)和和D=(V,A,W)。整理课件14二、最小生成树（最小树）：二、最小生成树（最小树）：定义：定义：在给定连通赋权图在给定连通赋权图G=(V,E,W)中，求中，求G的生成树的生成树T=(V,E )，使，使E 各边权各边权Wij(

11、0)的总和最小的问题称为最小树的总和最小的问题称为最小树问题。其数学模型为：问题。其数学模型为：其中其中T*称为最小树。称为最小树。 许多网络问题都可归结为最小树问题，如设计长度最许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若干城市联通；设计用料最省的电话线网把小的公路网把若干城市联通；设计用料最省的电话线网把有关单位联系起来。有关单位联系起来。整理课件15求最小树的方法：求最小树的方法：、破圈法、破圈法(管梅谷算法管梅谷算法) ：（）先从图（）先从图G任取一个圈，并从圈中去掉一条权最大的边。任取一个圈，并从圈中去掉一条权最大的边。若在同一圈中有几条都是权最大边，则任选其中一边去

12、掉。若在同一圈中有几条都是权最大边，则任选其中一边去掉。（）在余下的子圈中，重复上述步骤，直至没有圈止。（）在余下的子圈中，重复上述步骤，直至没有圈止。、避圈法、避圈法(Kruskal算法算法) ：开始选一条权最小的边，以后每开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够直至选够q1条边止。条边止。v2v1v4v322344546v5v2v1v4v32234v5整理课件16例、例、今要在七个城市之间修筑一个公路网，每个城市之间今要在七个城市之间修筑一个公路网，每个城市之间的公路修筑费用就是各条

13、边上的权，试求总修筑费用最小的的公路修筑费用就是各条边上的权，试求总修筑费用最小的公路网。公路网。v1v4v7v6v5v3v28567632445310v1v4v7v6v5v3v2324453整理课件17 最短路问题是网络理论中应用最广泛的问题之一，许最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如管道铺设，设备更新，多优化问题可以使用这个模型，如管道铺设，设备更新，线路安排等。线路安排等。 给定给定D=(V,A,W)，其中，其中wij W，表示弧，表示弧(vi,vj)的权（可的权（可以是费用、时间、距离等）。设以是费用、时间、距离等）。设vs和和vt是是D中任意两

14、顶点，中任意两顶点，求一条路，使它是从求一条路，使它是从vs到到vt的所有路中总权最小的路。的所有路中总权最小的路。 其数学模型为：其数学模型为：ijWPWmin)(* (vi,vj)P 整理课件18求最短路的狄克斯特求最短路的狄克斯特DijkstraDijkstra标号法（标号法（W Wijij 0 0）1、基于以下基于以下原理原理：若序列：若序列vs,vi1,vik,vt是从是从vs到到vt的最的最短路，则序列短路，则序列vs,vi1,vik必为从必为从vs到到vik的最短路。的最短路。 2、Dijkstra标号法的基本思想是采用标号法的基本思想是采用两种标号两种标号： T标号标号与与P标

15、号标号，T标号为临时性标号标号为临时性标号(Temporary Label)，P标号为永久性标号标号为永久性标号(Permanent Label)。 从从vs开始，逐步向外探寻最短路。给开始，逐步向外探寻最短路。给vi点点P标号时，表标号时，表示从示从vs到到vi点的最短路权，点的最短路权，vi的标号不再改变。给的标号不再改变。给vi点点T标号标号时，表示从时，表示从vs到到vi点的最短路权上界的估计。凡没有得到点的最短路权上界的估计。凡没有得到P标号的点都有标号的点都有T标号。标号法每一步都是把某一标号。标号法每一步都是把某一T标号点改标号点改为为P标号，当终点标号，当终点vt得到得到P标号

16、时，计算全部结束。如果点标号时，计算全部结束。如果点vj不能由不能由T标号变为标号变为P标号，则说明标号，则说明vs到到vj不存在路。不存在路。整理课件19 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(v

17、jo)=minT(vj) vj为为T标号标号 若全部点均为若全部点均为P标号。则停止。否则以标号。则停止。否则以vjo代代vi，返回，返回(2)整理课件20v6v5v4v3v2v1v8v7356117423521695（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)=v2整理课件21v6v5v4v3v2v1v8v7356117423521695（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