乔海燕_qhy_graph2道路与回路

1、1第二章 道路与回路2有向道路有向道路 有向图G=(V, A) 中，一条有向道路指的是一个首尾相接的弧的有限非空序列 P = a1 a2 ak (k1) 其中 viV ( i =0. k ), ajA ( j =1.k ) 且 aj= ( j=1. k ) v0 和vk分别称为P的起点和终点，k称为P的长度。在简单图中，也可记作 P = ( v0 ， v1 ，v2 ，vk ) 或 v0 v1 v2 vp 2.1 2.1 道路与回路道路与回路3简单道路简单道路 若对任意的ij有ai aj ，称之为简单有向道简单有向道路路。(没有重复边的路径)回路回路 若 v0 = vn ，称之为封闭的。封闭的。

2、简单封闭有向道路（闭迹）称为有向回路有向回路。初级道路初级道路若对任意的ij有 vi vj ，称之为初级道路初级道路/基本道路基本道路。 圈圈若对任意的ij有vi vj 而例外地v0 = vn，称之为初初级回路级回路/圈圈。无向图具有完全类似的定义。 2.1 2.1 简单道路与圈简单道路与圈4容易证明：定理定理2-1（1）基本道路是简单道路；（2）如果存在u到v的道路，则存在u到v 的基本道路； (3) n阶图的基本道路长度不超过n-1; (4) n阶图的圈的长度不超过n. 2.1 基本道路基本道路5定理定理2-2 无向图G=(V, E)，u, v V 且 uv。若 u,v 之间存在两条不同的

3、路，则 G 中存在一条回路。证明证明 （构造法）定理定理2-3 无向图G=(V, E) 中每个顶点的度均为偶数，且至少有一个顶点不是孤立点，则 G 中存在一条回路。 证明证明 （反证法）设v不是孤立点，从v出发的最长简单路径经过的顶点是v0(=v)v1vn-1vn，则必存在0in使得vn=vi，否则, 因为vn的度是偶数，存在与vn邻接另一个顶点u, 从而得到一条更长的简单路径。矛盾！2.1 2.1 道路与回路的关系道路与回路的关系6可达性可达性 对于有向图G=(V, A)中，若从 vi 到 vj 存在一条路，则称从 vi 到 vj 是可达的，或称 vi 可达 vj 。对无向图 G=(V, E

4、)，结点间的可达性是对称的。连通性连通性 对于无向图G=(V, E)，任意两点之间可达时，称G为连通的（连通图）。 G中的一个极大连通子图称为G的一个连通分支。一个图总是由一些连通分支构成的。 G的连通分支数，记为W(G)。2.2 2.2 连通性连通性7强连通性强连通性对于有向图G=(V, A)，如果任意两点之间相互可达，则称G为强连通的.弱弱 连通性连通性对于有向图G=(V, A), 若不考虑弧的方向后得到的无向图是连通的，则称有向图G是弱连通的。2.2 2.2 有向图的连通性有向图的连通性8定理定理2-5 G=(V, E)，n=|V|，若对任意 u, v V 且 uv，都有：Deg(u)

5、+ Deg(v) n1，则 G 连通。证明证明 (反证法) 设G可分为不连通的两部分G1=(V1, E1)和G2=(V2, E2)，选取 uV1, vV2 则 Deg(u) = |V1|-1， Deg(v) |V2|-1， 故 Deg(u) + Deg(v) 00 其他 可求得G的道路矩阵 P。 算法复杂度 O(n4)2.2 2.2 道路矩阵道路矩阵12道路矩阵可以通过二值矩阵的逻辑运算求得。定义定义 二值元素的逻辑运算： 0 0=0，0 1=1 0=1，1 1=1 0 0=0，0 1=1 0=0，1 1=1定义定义 二值矩阵的逻辑运算。设有矩阵A = (aij)，B = (bij)，矩阵元素

6、值域为 0,1，定义运算：ijijikkjababijnijk=1(AB) =(AB) =()2.2 2.2 道路矩阵的计算道路矩阵的计算13定义定义 A(k) = A(k1) A ( k2 )，A(1) = A注意 A(k) 与Ak 的区别定理定理2-12 设 Ann 是图G的邻接矩阵，若从vi 到vj存在长度为 l 的路，则 A(l)ij = 1，否则 A(l)ij = 0。证明证明 对 l 作归纳；或直接引用定理2-11。2.2 2.2 道路矩阵的计算道路矩阵的计算14Warshall算法算法 设 A nn是图G的邻接矩阵，求G的道路矩阵P。1. P A2. for i=1 to n d

7、o3. for j=1 to n do4. for k=1 to n do5. pjk pjk (pji pik) 计算复杂度 O(n3)2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法初始：pij表示有无长度为1 的直达路径第i次外层循环结束时：pjk表示有中间通过v1,v2,vi的路径。15例例 图G的邻接矩阵A如右，使用Warshall算法求G的道路矩阵P。01000011A = 11011000解解 P A01000011P = 110110002.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法16(1) i =101000011P

8、 = 11011000 j =1,2,3,4 增量方向i =1 矩阵元素处理次序： p11， p12， p13， p14， p21， p22， p31， p41， ， p44，2.2 2.2 道路矩阵及道路矩阵及WarshallWarshall算法算法17 如： p11 = p11 (p1i pi1) = p11 (p11 p11) = 0 p12 = p12 (p1i pi2) = p12 (p11 p12) = 1 p13 = p13 (p1i pi3) = p13 (p11 p13) = 0 01000011P = 11011100 结果为2.2 2.2 道路矩阵及道路矩阵及Warsha

9、llWarshall算法算法182.2 图上的搜索图上的搜索可以使用搜索的方法判断从一个顶点u到另一个顶点v是否有路径。深度优先DFS从顶点u出发检查其后继u1是否，如果不是，则从u1开始进行深度优先搜索；如果没有后继,则回溯，直至找到或者没有可搜索的顶点。192.2 图上的搜索图上的搜索广度优先BFS从u出发，首先检查其所有的直接后继是否等于；然后依次检查这些后继的直接后继，直到找到或者没有可遍历顶点。练习：编写一个使用深度优先或者广度优先搜索判定两个点之间是否有道路的程序。20Euler回路回路 若连通图 G=(V, E) 中存在一条简单回路（无重复边）经过G的所有边，则称该回路为G中的一

10、条Euler回路。存在Euler回路的图称为Euler图。定理定理2-6-1 设有连通图G=(V, E)，则下述命题等价： (1) G是一个Euler图； (2) G的每一个顶点的度是偶数；证明证明（见戴一奇教材 p16定理2.3.1）2.3 Euler 2.3 Euler 回路回路21注意定理中对图的连通性的假定；Euler回路经过图的所有边一次且仅仅一次。定理对非简单图也成立；定理的证明过程给出了为一个Euler图构造Euler回路的构造算法。定理定理2-7 设连通图G=(V, E)中恰有2个顶点度为奇数，则G存在Euler道路。证明证明 连接两个奇度数结点形成Euler图，再删除该边即可

11、。2.3 Euler 2.3 Euler 回路回路22有向图的有向图的Euler回路回路 若有向连通图 G=(V, A) 中存在一条简单有向回路经过G的所有弧，则称该回路为G中的一条Euler回路，称该图为Euler有向图。定理定理2-6-2 设连通有向图G=(V, A)，则下述命题等价： (1) G是一个Euler有向图； (2) G的每一个顶点的入度等于出度；证明证明（略）2.3 Euler 2.3 Euler 回路回路23Hamilton路路 若连通图 G=(V, E) 中存在一条初级道路（无重复顶点）经过G中每个顶点一次，则称该道路为G中的一条Hamilton路。存在Hamilton回

12、路（圈）的图称 为Hamilton图。Hamilton路经过图的所有顶点一次且仅仅一次。引入记号：G =(V, E)，SV。从G中去除S中的顶点及其关联边得到的G的子图记为GS。2.4 Hamilton 2.4 Hamilton 道路道路242.2. Hamilton Hamilton 图图构造Hamilton圈的简单规则：Halmilton圈含n条边；Halmilton圈正好包含每个结点的两条关联边，其他边可以删除；左图如有H圈， 则必包含三个二度结点的邻接边，从而中心结点至少有三个邻接边包含在其中，故不可能有圈。25定理定理2-8 若G=(V, E)是一个Hamilton图，SV且S，则

13、G的子图GS的连通分支数 W(GS) |S|证明证明 记G中H-回路为C，C中包含了G中所有顶点。 考察CS：每从C中去除属于S的一个顶点，连通分支数至多增加1（第一次以及当该顶点处于边缘时操作不会增加连通分支数），故 W(CS) |S| 而G可视为向C中添加边构成，故W(GS) W(CS) 所以 W(GS) |S|2.2. Hamilton Hamilton 图图26例例 图 G12345786令S=2,6，则W(GS)=3。而|S|=2，即W(GS)|S|故图G不可能是Hamilton图。134578图图 G-S2.2. Hamilton Hamilton 图图27例例 Petersen图

14、。|V|=10，对任何SV，都有W(GS)S ，但Petersen图不是Hamilton图（留作习题）。Peterson 图存在Hamilton道路。2.2. Hamilton Hamilton 图图删除一个或者两个顶点仍然连通，删除三个顶点最多得到两个连通分支，28例例 下图不存在Hamilton圈。给图的相邻顶点标以A，B，则Hamilton圈包含相同个数的A,B. 2.2. Hamilton Hamilton 图图29定理定理2-9 简单图 G=(V, E)，n=|V|，若对任一对不相邻顶点 u, vV, uv，有deg(u) + deg(v) n1，则G中存在一条Hamilton路。证

15、明证明 (见戴一奇教材p18定理2.4.1)梗概: (1) G是连通的； (2) 如果v1,v2,vp是一条基本道路，pn, 则可以扩展这条道路：(a) v1,vp存在v1,vp之外的邻接点，可以立即扩展；(b) v1,vp仅与v1,vp邻接，则存在包含这些点的圈。 由连通性，存在圈外的结点与圈上某结点邻接，所以，这样的圈可以扩展成更长的基本道路，直至p=n.2.2. Hamilton Hamilton 道路道路30推论推论 上述有 deg(u) + deg(v) n 时，G为Hamilton图。证明证明 （见戴一奇教材p19推论2.4.1）假设 v1,v2,vn 是Hamilton路，如果v

16、1与 vn 不邻接， 设v1的邻接点集是vi1, vi2, ,vik, 则vn必与 vi1-1, vi2-1, ,vik-1之一邻接， 否则deg(vn) = n-1-k, deg(v1) =k, deg(v1)+deg(vn)=n-1。 矛盾！ 2.2. Hamilton Hamilton 道路道路31 定理及其推论 给出了Hamilton图成立的充分条件，可用于对Hamilton图的肯定性判定。 Hamilton图成立的充要条件尚未得到解决，是图论求解的课题之一。2.2. Hamilton Hamilton 图图32旅行商问题旅行商问题 已知n个城市，任两个城市之间都有无向路相通，求一条经

17、过所有城市一次且仅仅一次，并且总路程最短的回路。在一个边带正权的n阶无向完全图中，存在不同的Hamilton回路。旅行商问题在其中寻找一条最短的Hamilton回路。精确算法：分支与界法近似算法：最近邻法；最近插入法；2.2. 旅行商问题旅行商问题33最近邻法最近邻法 设城市之间道路长度符合三角不等式。算法算法 从v1出发,找到其最近邻城市vi2,再从vi2出发vin, 将vin与v1连接得到H-回路。2.2. 旅行商问题旅行商问题123456123456508691978350966558798696886754916588787097586778668379547066vvvvvvvvvv

18、vv例例结果是： v1 v2 v5 v6 v3 v4 v1 回路长度=407但是： v1 v2 v4 v6 v5 v3 v1 回路长度=40434最近插入法最近插入法 先构成一个初始旅行圈，再选择与该圈最接近的城市扩展。扩展时可采用某种策略，如便宜算法，直至得到H-回路。2.2. 旅行商问题旅行商问题v1v1C1设v2是距C1最近的点C2v1v2设v3是距C2最近的点v1v2C3 v3设v3是距C2最近的点v1v2C2 v335如果w(v1,v4)-w(v1,v2) w(v3,v4)-w(v2,v3),则连接v1,v4, 否则,连接v3,v4.设v4是距C3 上v2最近的点v1v2C3 v3v

19、436网络网络 有向图有向图 G=(V, A) 中，给每条边中，给每条边 a= 赋予赋予一个非负实数权一个非负实数权 wij ，得到一个有向网络。，得到一个有向网络。距离矩阵距离矩阵 对上述网络，定义对上述网络，定义 D=(dij)n n，n=|V| wij 当当 A dij = 其它其它带权路径长度带权路径长度 对上述网络，路径对上述网络，路径 v1, v2 , ,vk 的带权的带权路径长度定义为路径长度定义为2.6 2.6 最短路径最短路径1,11ki iidw37两点间的最短距离两点间的最短距离 对上述网络，结点对上述网络，结点vi到到vj可达时，可达时， vi到到vj的所有路径中具有最

20、小带权路径长度者称为的所有路径中具有最小带权路径长度者称为vi到到vj的最短路径，其带权路径长度称为的最短路径，其带权路径长度称为vi到到vj的最短的最短距离。距离。引理引理 在有向网络中，若路径在有向网络中，若路径 v1, v2 , ,vk-1 ,vk是是v1到到vk的最短路，则的最短路，则路径路径 v1, v2 , ,vk-1 是是v1到到vk-1的最的最短路。短路。2.6 2.6 最短路径最短路径证明证明如果路径 v1, v2 , ,vk-1 不是v1到vk-1的最短路，则v1, v2 , ,vk-1 ,vk不是v1到vk的最短路。382.6 Dijkstra 算法算法Dijkstra算

21、法基本思想: 如果v0至u的最短路经经过v1,那么v0到v1的路径也是v0至v1的最短路经。 按路径长度的递增次序，逐步产生最短路径. 设源点为v01.首先求出v0为源点长度最短的一条最短路径， 即具有最小权的边;2.求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的最短路径（v0v)和边构成；3.重复2直到从顶点v0到其它各顶点的最短路径全部求出为止392.6 Dijkstra 算法算法例：求例：求v0其他各点的最短路径其他各点的最短路径用用S表示已求出最短路径的结点集表示已求出最短路径的结点集初始状态：初始状态：S=v0v5v4v3v2v1v0

22、 100 6030101020 5 50第一条最短路径：第一条最短路径：( v0, v2)S = v0,v2求下一条最短路径：求下一条最短路径：先求先求v0到其他顶点到其他顶点vi的的只经过只经过S结点的路径：结点的路径：v0 -v1: v0-v3: (v0,v2,v3) 60v0-v4: (v0,v4) 30v0-v5: (v0,v5) 100第二条最短路径：第二条最短路径： (v0,v4) ， S = v0,v2, v4402.6 Dijkstra 算法算法v5v4v3v2v1v0 100 6030101020 5 50第一条最短路径：第一条最短路径：( v0, v2)S = v0,v2求

23、下一条最短路径：求下一条最短路径：先求先求v0到其他顶点到其他顶点vi的的只经过只经过S结点的路径：结点的路径：v0 -v1: v0-v3: (v0,v2,v3) 60, (v0,v4,v3) 50v0-v5: (v0,v5) 100, (v0,v4,v5) 90第二条最短路径：第二条最短路径： (v0,v4) ， S = v0,v2, v4第三条最短路径：第三条最短路径： (v0,v4,v3) ， S = v0,v2, v4, v3第四条最短路径：第四条最短路径： (v0,v4,v3,v5) ， S = v0,v2, v4, v3, v5412.6 Dijkstra 算法算法 用S表示当前找

24、到最短路径的终点集；Dj表示0 0 一般情况下，一般情况下，),(),(=0ikiSvvvWkDvvWMiniDk422.6 Dijkstra 算法算法1. 初始化S：S0=1;S1.n-1=0；2. 初始化D: Dj = W;3. 在D中选择最小的路径长度Dk, 并将vk加入S；4. 修改数组D: Dj=minDj, Dk + W;5. 重复3，4 n-1次， 直至求得v0到所有顶点的最短路径此外此外 , , 增设一个数组增设一个数组P P记录记录v0v0到各点的最短路径：到各点的最短路径：若若v v0 0，w w1 1, , ,w,wk k,v,v是是v v0 0到到v v的最短路径，的最

25、短路径， 则则PvPv=w=wk k, Pw, Pwk k=w=w(i-1)(i-1), , , Pw, Pw1 1=v=v0 0. .432.6 Dijkstra 算法算法 Dijkstra算法要求图上的权是非负数，否则结果不正确； Dijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。 习题 证明Dijkstra算法的正确性。44例例2.6 2.6 求单源点最短距离的求单源点最短距离的DijkstraDijkstra算法算法12345554025520402010202520102555vDvvvv 结果：结果：U = (0, 50 , 55 , 40 , 25) 计算复

26、杂度：计算复杂度：O(n2)45Dijkstra算法的证明对于任意结点v, 假如在将加入之前另外有一条更短的路径，首先经过，然后到达，那么在之前加入，矛盾。462.7 2.7 关键路径关键路径作业网络作业网络 一项工程通常包一项工程通常包括多个工序，这些工序括多个工序，这些工序间存在次序的约束：一间存在次序的约束：一个工序的开始的前提是个工序的开始的前提是某些工序已经结束。每某些工序已经结束。每个工序有预计的完成时个工序有预计的完成时间。间。1CS10132CS10213CS201 CS101CS10224CS302 CS20115CS305 CS30216CS405 CS3021编号 课程号

27、 先修课 时间472.7 AOV网网1CS10132CS10213CS201CS101CS10224CS302CS10215CS305CS201 CS30216CS405CS3021142365311211顶点表示活动的图(AOV网)：工序用顶点表示，工序j在工序i之后开始用有向边表示，其权表示工序i所需的时间。482.7 AOV网网142365311211一个工程的两个问题：工程能否顺利进行，即可否找到工序的一个线性排列：v1,v2,v3,v4,v5,v6,使得如果是一条有向边，那么ij.拓扑排序问题。 估算工程完成所需要的最短时间。求关键路径问题。492.7 拓扑排序拓扑排序1423653

28、11211拓扑排序 将一个n阶有向图G=(V,A)的所有顶点排列成一个线性序v1,v2,vn，使得如果A, 则ij.称这样的序列为的一个拓扑排序。例如，左图的一个拓扑排序是：1,2,3,4,6,5502.7 拓扑排序拓扑排序定理 若有向图G=(V,A) 不存在有向回路，则存在拓扑排序。证明设v0是出度为零的顶点，记G1=G-v0, 令v1是G1中出度为零的结点，由此反复，则序列v0,v1, vn是G的一个拓扑排序。 引理 若有向图G=(V,A) 不存在有向回路，则存在入度为零和出度为零的结点。51AOV网络网络 有向连通网络有向连通网络 G=(V, A)： 每一结点表示一个作业，有向边每一结点

29、表示一个作业，有向边表示作业表示作业vj必须在必须在vi完成之后开始；完成之后开始； 边边所带的非负实数权为完成作业所带的非负实数权为完成作业vi所需时间；所需时间； 作业开始条件：该作业的所有前驱作业全部完成；作业开始条件：该作业的所有前驱作业全部完成； 无回路假设无回路假设 (DAG: Directed Acyclic Graph 有向无环图有向无环图)； 网络中有且只有一点入度为网络中有且只有一点入度为0，称为源点，表示工程开始；，称为源点，表示工程开始；有且只有一点出度为有且只有一点出度为0，称为汇点，表示工程结束。，称为汇点，表示工程结束。2.7 2.7 关键路径关键路径524.5 4.5 关键路径关键路径关键路径关键路径 AOV网络网络G=