20-通路与连通070101.ppt

1、通路与连通,信号处理中的数学方法 第2-2讲,上一讲内容的回顾,图的定义与表示 图中的关系 顶点的度数 子图与图的同构 完全图 正则图 r部图 图模型,通路与连通,通路与回路 连通与连通图 扩大路径证明法 最短通路问题与Dijkstra算法,有边就有了路,通路的定义,定义：图G中的(v0,vk)-通路是一个非空序列v0e1v1e2v2vk-1ekvk, 其中viVG, eiEG,且ei的两个端点是vi-1和vi,(i=1,2,k)。 两种通路 简单通路：v0e1v1e2v2vk-1ekvk中，i,j, ij eiej 基本/初级通路(路径): v0e1v1e2v2vk-1ekvk中，i,j,

2、ij vivj,回路,起点与终点相同的通路又称为回路 即：v0e1v1e2v2vk-1ekvk中，v0=vk 注，简单图中，通路的表示可以简化：v0v1v2vk-1vk 例： 通路：uavfyfvgyhwbv 简单通路：wcxdyhwbvgy 基本通路：xcwhyeuav 回路：ueyhwbvau,基本通路的存在性,若图G中含(u,v)-通路(uv)，则一定含基本通路(u,v) 证明：(略) 设W= v0e1v1vk-1ekvk,是(u,v)-通路，其中v0=u, vk=v。 若i,j, 有ij vivj, 则W即基本通路。 否则，存在i,j(0ijk), 满足：vi=vj。 即W=v0e1v

3、1e2v2vi-1eivivj-1ejvjej+1vk-1ekvk, 则W= v0e1v1e2v2vi-1eiviej+1vk-1ekvk仍是(u,v)-通路，但W中的相同顶点对减少了。 注意: W是有限序列， 重复上述步骤可得(u,v)-路径。 注意：如果G中顶点数是n, (u,v)-路径长度最大为n-1。,回路和基本回路,图G中任意一条边e若在一简单回路中，则e一定在一基本回路中。 证明： 假设e的两个端点是u,v, 因为e在“边不重复”的回路中，所以存在不包含e的(u,v)-通路。 令图G=G-e (可以简写为G-e), G中含(u,v)-通路，则G中含(u,v)-基本通路P。 注意：P

4、中不含e, 则：P+e是基本回路。,最小顶点度数和回路(略),G是简单图，若dG=k (k1), 则G中必含长度至少为k+1的初级回路。 证明： 设P是图中一条路径，其端点为u,v。若u,v均不再与P以外的任意顶点相邻，则称P是G中的极大路径。 注意：只要G中有边，从任一条边开始，通过“扩大路径”一定可以构作一极大路径。 因为图G最小顶点度数非零，一定可以找到一条极大路径(v0, v1, v2,vm-1, vm), 则v0,至少与该路径中k-1个不同的顶点相邻，且这k-1个顶点中不含v1, 所以，这k-1个顶点中沿该路径离v0最远的一个下标一定不小于k, 设其为vt, 则(v0, v1, vt

5、, v0)构成长度不小于k+1的初级回路。,u,d(u)k,v,可达性关系 (略),定义：RcVGVG, u,vVG, Rc 当且仅当 G中存在(u,v)通路。 如果约定，对G中任意顶点u，存在长度为0的(u,u)-通路，则无向图上定义的Rc是等价关系。 Rc是VG上的相邻关系Ra的传递闭包 即：Ra Rc ,且RVGVG, 若R是传递关系，则Ra R, Rc R 证明： Ra Rc显然。 设R是包含Ra的传递关系。假设RcR，则存在Rc, 但R。 由Rc可知G中有(x,y)-通路，但x,y不相邻(否则，Ra R)。存在顶点序列x,v1,v2vk-1,vk,y, 满足：, , ,Ra R, 由

6、R的传递性可知：R, 矛盾。Rc R。,连通分支和连通图,可达性关系是等价关系，相应的等价类称为连通分支。 如果图G只含一个连通分支，则称G是连通图。 图G是连通图 当且仅当 u,vVG, G中存在uv-通路。,图与补图的连通,G是任意的简单图，G和其补图G中至少有一个是连通图。 证明： 假设G不连通。任给u,vG ： 如果uvEG, 则uv在G中相邻。 如果uvEG, 因为G是非连通图，一定存在顶点w与u,v再不同的连通分支中，于是uwEG, vwEG, 所以: uwEG, vw EG, (u,w,v)是G中的uv-通路。 G是连通图。,有关连通图的一个例子,G是至少含3个顶点的简单 连通图

7、，若G不是完全图， 则G中一定含三个顶点u,v,w, 满足：uwVG, wvVG, 但uvVG。 由于G非完全图，一定有顶点x,y不相邻。但G是连通图，所以G中存在xy-路径(x, v1,vm-1, vm=y)。其中m2。令vk是沿这条路径离x最近的与x不相邻的顶点(注意：x,y不相邻保证这个vk一定能找到)。显然k1，则x, vk-1和vk就满足u,w,v的要求。,带权图与最短路问题,带权图：三元组 (V, E, W)，(V, E)是图，W 是从E到非负整数集的一个函数。W(e)表示边e的权。 一条通路上所有边的权的和称为该通路的权。 两点之间权尽可能小的通路称为两点之间的最短路，不一定是唯

8、一的。 单源点最短路问题 给定带权图 G(V, E, W)并指定一个源点，确定该源点到图中其它任一顶点的最短路（长度和路径）。,局部最优未必导致全局最优,2,4,5,8,求最短路的Dijkstra算法,输入：连通带权图G，|VG|=n, 指定顶点sVG 输出：每个顶点v的标注(L(v), u), 其中： L(v)即从s到v的最短路径长度 u是该路径上v前一个顶点。,求最短路的Dijkstra算法步骤,1初始化：i=0, S0=s, L(s)=0，u=s, 对其它一切vVG, 将L(v)置为。若n=1，结束。 2vSi=VG-Si, 比较L(v)和L(ui)+W(ui, v)的值 (uiSi)

9、如果L(ui)+W(ui, v)L(v), 则将v的标注更新为(L(ui)+W(ui, v), ui)，即： L(v)=minL(v), L(u)+W(u,v) 3. 对所有Si中的顶点，找出具有最小L(v)的顶点v, 作为u 4Si+1 = Si u 5. i = i+1; 若i=n-1, 终止。否则：转到第2步。,求最短路的一个例子,s,7,7,2,1,2,5,1,2,4,4,8,3,5,3,4,6,3,0,s,7,7,2,1,2,5,1,2,4,4,8,3,5,3,4,6,3,0,1,2,8,7,4,1,2,8,7,4,4,求最短路的一个例子(续),求最短路的一个例子(续),s,7,7,

10、2,1,2,5,1,2,4,4,8,3,5,3,4,6,3,0,s,7,7,2,1,2,3,1,2,4,4,8,3,5,3,4,6,0,1,2,6,6,4,1,2,8,6,4,3,3,9,6,9,5,求最短路的一个例子(续),Dijkstra算法的证明 可终止性,算法复杂度O(V2+E)-O(E+V)logV)-O(VlogV+E) 算法的可终止性是显然的。 计数控制 需证明当算法终止时 L(v)=d(s,v)对一切v成立。 由标记中的诸ui确定的路径是一条最短路径 (这里d(s,v)是s到v的最短通路长度，即距离。),Dijkstra算法的证明 最短路长度(略),需证明：当算法终止时L(v)

11、=d(s,v)对一切vS成立 使用数学归纳法证明：对Si, L(v)=d(s,v)对一切vSi成立, i=0,1,2,n-1 i=0时显然，根据算法第一步：L(s)=0。 假设结论对一切vSi成立，而Si+1=Siui+1，下面证明L(ui+1)=d(s, ui+1) 根据算法第3步以及第2步: L(ui+1)=minvSiL(v), L(u)+W(u,v) 根据归纳假设，L(u)=d(s,u), 上式= minvSiL(v), L(u)+W(u,v) 根据算法中对ui+1的选择，minuSi, vSid(s,u)+W(u,v) 即 d(s,u)+W(u,ui+1)= d(s, ui+1),D

12、ijkstra算法的证明 最短路径(略),需要证明：对任意vs, s(=w0) w1w2wk(=v)是最短的sv-路。 其中wi是标记为(L(wi), wi-1)的顶点(i=1,2,n-1) 证明： 由算法，s(=w0) w1w2wk(=v)显然是一条sv-路, 且L(v)即其长度。 对任意vs, 假设算法终止时，v的标记是(L(v), wk-1), 由算法第2步，L(v)=L(wk-1)+w(wk-1,v), 而L(wk-1)=d(s, wk-1), 所以上述通路的长度即d(s,v)。,See also Bellman-Ford O(|E|V|) 负权边 负权环 DAG O(|V|+|E|) 单目标节点最短路径 单节点对最短路径 所有节点对最短路径 Floyd O(|V|3),Dijkstra, Edsgar Wybe