道路与回路课件.ppt

《道路与回路课件.ppt》由会员分享，可在线阅读，更多相关《道路与回路课件.ppt（59页珍藏版）》请在三一办公上搜索。

1、第二章 道路与回路,2.1 道路与回路,有向道路 有向图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 道路与回路,简单道路 若对任意的ij有ai aj，称之为简单有向道路(simple path,没有重复边的路径)回路 若 v0=vn，称之为封闭的。简单封闭有向道路（闭迹）称为有向简单回路。初级道路若对任意的ij有 vi vj，称之为初

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

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

4、G为连通的（连通图）。G中的一个极大连通子图称为G的一个连通分支。一个图总是由一些连通分支构成的。G的连通分支数，记为W(G)。,2.2 连通性,强连通性对于有向图G=(V,A)，如果任意两点之间相互可达，则称G为强连通的.弱 连通性对于有向图G=(V,A),若不考虑弧的方向后得到的无向图是连通的，则称有向图G是弱连通的。,2.2 有向图的连通性,定理2-5 G=(V,E)，n=|V|，若对任意 u,v V 且 uv，都有：Deg(u)+Deg(v)n1，则 G 连通。证明(反证法)设G可分为不连通的两部分G1=(V1,E1)和G2=(V2,E2)，选取 uV1,vV2 则 Deg(u)=|V

5、1|-1，Deg(v)|V2|-1，故 Deg(u)+Deg(v)=|V1|+|V2|-2=n-2，与 Deg(u)+Deg(v)n1 矛盾。注意：未加特别声明时，我们讨论的都是简单图。,2.2 连通的判定,定理2-11 设Ann 是G的邻接矩阵，则连接 vi与vj（ij）的长度为 l 的路径的条数等于Al 的第i行第j列的元素的数值。证明（数学归纳法：对 l 归纳）,2.2 图的邻接矩阵,道路矩阵 对有向图 G=(V,R)，n=|V|，构造矩阵 P=(pij)nn，其中,称P为图G的道路矩阵（或可达矩阵）。,2.2 道路矩阵及Warshall算法,算法 求给定图G的道路矩阵P 设A为G的邻接

6、矩阵，B=A+A2+A3+An1，由定理2-11，bij表示由vi至vj，长度为1或2或或 n1的路径数目，即为由vi至vj的全部路径总和。令,可求得G的道路矩阵 P。算法复杂度 O(n4),2.2 道路矩阵,道路矩阵可以通过二值矩阵的逻辑运算求得。定义 二值元素的逻辑运算：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)，矩阵元素值域为 0,1，定义运算：,2.2 道路矩阵的计算,定义 A(k)=A(k1)A(k2)，A(1)=A注意 A(k)与Ak 的区别定理2-12 设 Ann 是图G的

7、邻接矩阵，若从vi 到vj存在长度为 l 的路，则 A(l)ij=1，否则 A(l)ij=0。证明 对 l 作归纳；或直接引用定理2-11。,2.2 道路矩阵的计算,Warshall算法 设 A nn是图G的邻接矩阵，求G的道路矩阵P。P Afor i=1 to n do for j=1 to n do for k=1 to n do pjk pjk(pji pik)计算复杂度 O(n3),2.2 道路矩阵及Warshall算法,初始：pij表示有无长度为1 的直达路径,第i次外层循环结束时：pjk表示有中间通过v1,v2,vi的路径。,例 图G的邻接矩阵A如右，使用Warshall算法求G的

8、道路矩阵P。,解 P A,2.2 道路矩阵及Warshall算法,(1)i=1,矩阵元素处理次序：p11，p12，p13，p14，p21，p22，p31，p41，p44，,2.2 道路矩阵及Warshall算法,如：p11=p11(p1i pi1)=p11(p11 p11)=0 p12=p12(p1i pi2)=p12(p11 p12)=1 p13=p13(p1i pi3)=p13(p11 p13)=0,结果为,2.2 道路矩阵及Warshall算法,2.3 图上的搜索,可以使用搜索的方法判断从一个顶点u到另一个顶点v是否有路径。深度优先DFS从顶点u出发检查其后继u1是否，如果不是，则从u1

9、开始进行深度优先搜索；如果没有后继,则回溯，直至找到或者没有可搜索的顶点。,2.3 图上的搜索,广度优先BFS从u出发，首先检查其所有的直接后继是否等于；然后依次检查这些后继的直接后继，直到找到或者没有可遍历顶点。,练习：编写一个使用深度优先或者广度优先搜索判定两个点之间是否有道路的程序。,Euler回路 若连通图 G=(V,E)中存在一条简单回路（无重复边）经过G的所有边，则称该回路为G中的一条Euler回路。存在Euler回路的图称为Euler图。定理2-6-1 设有连通图G=(V,E)，则下述命题等价：(1)G是一个Euler图；(2)G的每一个顶点的度是偶数；证明（略）,2.4 Eul

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

11、每一个顶点的入度等于出度；证明（略）,2.4 Euler 回路,Hamilton路 若连通图 G=(V,E)中存在一条初级道路（无重复顶点）经过G中每个顶点一次，则称该道路为G中的一条Hamilton路。存在Hamilton回路（圈）的图称 为Hamilton图。Hamilton路经过图的所有顶点一次且仅仅一次。引入记号：G=(V,E)，SV。从G中去除S中的顶点及其关联边得到的G的子图记为GS。,2.5 Hamilton 道路,2.5 Hamilton 图,构造Hamilton圈的简单规则：Halmilton圈含n条边；Halmilton圈正好包含每个结点的两条关联边，其他边可以删除；,左图

12、如有H圈，则必包含三个二度结点的邻接边，从而中心结点至少有三个邻接边包含在其中，故不可能有圈。,定理2-8 若G=(V,E)是一个Hamilton图，SV且S，则 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.5 Hamilton 图,例 图 G,令S=2,6，则W(GS)=3。而|S|=2，即W(GS)|S|故图G不可能是Hamilto

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

14、明(梗概)(1)G是连通的；(2)如果v1,v2,vp是一条基本道路，pn,则可以扩展这条道路：(a)v1,vp存在v1,vp之外的邻接点，可以立即扩展；(b)v1,vp仅与v1,vp邻接，则存在包含这些点的圈。由连通性，存在圈外的结点与圈上某结点邻接，所以，这样的圈可以扩展成更长的基本道路，直至p=n.,2.5 Hamilton 道路,推论 上述有 deg(u)+deg(v)n 时，G为Hamilton图。证明 假设 v1,v2,vn 是Hamilton路，如果v1与 vn 不邻接，设v1的邻接点集是vi1,vi2,vik,则vn必与 vi1-1,vi2-1,vik-1之一邻接，否则deg(

15、vn)=n-1-k,deg(v1)=k,deg(v1)+deg(vn)=n-1。矛盾！,2.5 Hamilton 道路,定理及其推论 给出了Hamilton图成立的充分条件，可用于对Hamilton图的肯定性判定。Hamilton图成立的充要条件尚未得到解决，是图论求解的课题之一。,2.5 Hamilton 图,旅行商问题 已知n个城市，任两个城市之间都有无向路相通，求一条经过所有城市一次且仅仅一次，并且总路程最短的回路。在一个边带正权的n阶无向完全图中，存在不同的Hamilton回路。旅行商问题在其中寻找一条最短的Hamilton回路。精确算法：分支与界法近似算法：最近邻法；最近插入法；,2

16、.6 旅行商问题,最近邻法 设城市之间道路长度符合三角不等式。算法 从v1出发,找到其最近邻城市vi2,再从vi2出发vin,将vin与v1连接得到H-回路。,2.6 旅行商问题,例,结果是：v1 v2 v5 v6 v3 v4 v1 回路长度=407,但是：v1 v2 v4 v6 v5 v3 v1 回路长度=404,最近插入法 先构成一个初始旅行圈，再选择与该圈最接近的城市扩展。扩展时可采用某种策略，如便宜算法，直至得到H-回路。,2.6 旅行商问题,v1,如果w(v1,v4)-w(v1,v2)w(v3,v4)-w(v2,v3),则连接v1,v4,否则,连接v3,v4.,设v4是距C3 上v2

17、最近的点,v1,v2,C3,v3,v4,网络 有向图 G=(V,A)中，给每条边 a=赋予一个非负实数权 wij，得到一个有向网络。距离矩阵 对上述网络，定义 D=(dij)nn，n=|V|wij 当 A dij=其它带权路径长度 对上述网络，路径 v1,v2,vk 的带权路径长度定义为,2.7 最短路径,两点间的最短距离 对上述网络，结点vi到vj可达时，vi到vj的所有路径中具有最小带权路径长度者称为vi到vj的最短路径，其带权路径长度称为vi到vj的最短距离。引理 在有向网络中，若路径 v1,v2,vk-1,vk是v1到vk的最短路，则路径 v1,v2,vk-1 是v1到vk-1的最短路

18、。,2.7 最短路径,证明如果路径 v1,v2,vk-1 不是v1到vk-1的最短路，则v1,v2,vk-1,vk不是v1到vk的最短路。,2.7 Dijkstra 算法,Dijkstra算法基本思想:如果v0至u的最短路经经过v1,那么v0到v1的路径也是v0至v1的最短路经。按路径长度的递增次序，逐步产生最短路径.设源点为v0首先求出v0为源点长度最短的一条最短路径，即具有最小权的边;求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的最短路径（v0v)和边构成；重复2直到从顶点v0到其它各顶点的最短路径全部求出为止。,2.7 Dijkstra

19、算法,例：求v0其他各点的最短路径用S表示已求出最短路径的结点集初始状态：S=v0,第一条最短路径：(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,v4,2.7 Dijkstra 算法,第一条最短路径：(v0,v2)S=v0,v2,求下一条最短路径：先求v0到其他顶点vi的只经过S结点的路径：,v0-v1:v0-v3:(v0,v2,v3)60,(v0,v4,v3)50v0-v5:(v0,v5

20、)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,v5,2.7 Dijkstra 算法,用S表示当前找到最短路径的终点集；引入一个辅助数组D,Dj表示当前找到的从源点v0到终点vi 的途径S的最短路径的长度。初始状态：S=v0若从源点v0到顶点vi有边，则Di为该边上的权值；若从源点v0到顶点vi 没有边，则Di为+,一般情况下，,2.7 Dijkstra 算法,初始化S：S0=1;S1.n-1=0；初始化D:Dj=W

21、;在D中选择最小的路径长度Dk,并将vk加入S；修改数组D:Dj=minDj,Dk+W;重复3，4 n-1次，直至求得v0到所有顶点的最短路径,此外,增设一个数组P记录v0到各点的最短路径：若v0，w1,wk,v是v0到v的最短路径，则Pv=wk,Pwk=w(i-1),Pw1=v0.,2.7 Dijkstra 算法,Dijkstra算法要求图上的权是非负数，否则结果不正确；Dijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。习题 证明Dijkstra算法的正确性。,例,2.7 求单源点最短距离的Dijkstra算法,结果：U=(0,50,55,40,25)计算复杂度：O(n

22、2),Dijkstra算法的证明对于任意结点v,假如在将加入之前另外有一条更短的路径，首先经过，然后到达，那么在之前加入，矛盾。,2.8 关键路径,作业网络 一项工程通常包括多个工序，这些工序间存在次序的约束：一个工序的开始的前提是某些工序已经结束。每个工序有预计的完成时间。,编号 课程号 先修课 时间,2.8 AOV网,顶点表示活动的图(AOV网)：工序用顶点表示，工序j在工序i之后开始用有向边表示，其权表示工序i所需的时间。,2.8 AOV网,一个工程的两个问题：工程能否顺利进行，即可否找到工序的一个线性排列：v1,v2,v3,v4,v5,v6,使得如果是一条有向边，那么ij.拓扑排序问题

23、。估算工程完成所需要的最短时间。求关键路径问题。,2.8 拓扑排序,拓扑排序 将一个n阶有向图G=(V,A)的所有顶点排列成一个线性序v1,v2,vn，使得如果A,则ij.称这样的序列为的一个拓扑排序。,例如，左图的一个拓扑排序是：1,2,3,4,6,5,2.8 拓扑排序,定理 若有向图G=(V,A)不存在有向回路，则存在拓扑排序。,证明设v0是出度为零的顶点，记G1=G-v0,令v1是G1中出度为零的结点，由此反复，则序列v0,v1,vn是G的一个拓扑排序。,引理 若有向图G=(V,A)不存在有向回路，则存在入度为零和出度为零的结点。,AOV网络 有向连通网络 G=(V,A)：每一结点表示一

24、个作业，有向边表示作业vj必须在vi完成之后开始；边所带的非负实数权为完成作业vi所需时间；作业开始条件：该作业的所有前驱作业全部完成；无回路假设(DAG:Directed Acyclic Graph 有向无环图)；网络中有且只有一点入度为0，称为源点，表示工程开始；有且只有一点出度为0，称为汇点，表示工程结束。,2.8 关键路径,2.8 关键路径,关键路径 AOV网络G=(V,A)中从源点v1到汇点vn的最长路径。关键路径不一定是唯一的。关键路径的长度为完成任务所需的必要时间T。关键作业 处于关键路径上的作业。记(vi,vj)为vi到vj的最长距离。特别地，(vi)=(v1,vi).则有,根

25、据以上关系，可以按照拓扑排序顺序求(vi)。定理4-5-2 将AOE网G=(V,A)的结点按照拓扑序列排序为v1,v2,vn,则(v1)=0,(vj)=max(vi)+wij|1 i A时的边的非负实权，规定A时 wij=。则 uj 为 v1 到 vj 的最长路径长度。,2.8 关键路径,例,2.8 关键路径,v1,v8,0,0,0,0,(v1)=0,(v2)=0,(v3)=0,(v4)=3,(v5)=1,(v6)=5,(v7)=2,(v8)=5关键路径v1,v2,v4,v6,v8长度(v8)=5。,2.8 关键路径,作业最早开始时间 从源点到该作业vk的最长路径长度(vk)作业最晚开始时间 设作业vk最晚可开始于(vk)时刻而不会影响任务完成的预期时间T=(vn),则有 缓冲时间 不影响任务完成的预期时间T的前提下，vk 的作业的缓冲时间为(vk)(vk)。,2.8 AOE网络,一个作业网络也可以表示为边表示活动的图.AOE 一个有向边表示一个作业，权表示活动完成需要的时间，起点表示活动的开始，终点表示活动的结束。,AOV网络,AOE网络,习题求下面AOE网络的关键路径,2.8 关键路径,