20-通路与连通070101.ppt

《20-通路与连通070101.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、本/初级通路(路径):v0e1v1e2v2…vk-1ekvk中，i,j,ijvivj回路起点与终点相同的通路又称为回路即：v0e1v1e2v2…vk-1ekvk中，v0=vk注，简单图中，通路的表示可以简化：v0v1v2…vk-1vk例：通路：uavfyfvgyhwbv简单通路：wcxdyhwbvgy基本通路：xcwhyeuav回路：ueyhwbvaudhgfaeuyvxwcb基本通路的存在性若图G中含(u,v)-通路(uv)，则一定含基本通路(u,v)证明：(略)设W=v0e1v1…v

3、k-1ekvk,是(u,v)-通路，其中v0=u,vk=v。若i,j,有ijvivj,则W即基本通路。否则，存在i,j(0i

4、路图G中任意一条边e若在一简单回路中，则e一定在一基本回路中。证明：假设e的两个端点是u,v,因为e在“边不重复”的回路中，所以存在不包含e的(u,v)-通路。令图G’=G-{e}(可以简写为G-e),G’中含(u,v)-通路，则G’中含(u,v)-基本通路P。注意：P中不含e,则：P+e是基本回路。最小顶点度数和回路(略)G是简单图，若dG=k(k>1),则G中必含长度至少为k+1的初级回路。证明：设P是图中一条路径，其端点为u,v。若u,v均不再与P以外的任意顶点相邻，则称P是G中的极大路径。

5、注意：只要G中有边，从任一条边开始，通过“扩大路径”一定可以构作一极大路径。因为图G最小顶点度数非零，一定可以找到一条极大路径(v0,v1,v2,…,vm-1,vm),则v0,至少与该路径中k-1个不同的顶点相邻，且这k-1个顶点中不含v1,所以，这k-1个顶点中沿该路径离v0最远的一个下标一定不小于k,设其为vt,则(v0,v1,…,vt,v0)构成长度不小于k+1的初级回路。ud(u)kv可达性关系(略)定义：RcVGVG,u,vVG,Rc当且仅当G中存在(u,v)通路。

6、如果约定，对G中任意顶点u，存在长度为0的(u,u)-通路，则无向图上定义的Rc是等价关系。Rc是VG上的相邻关系Ra的传递闭包即：RaRc,且R'VGVG,若R'是传递关系，则RaR',RcR'证明：RaRc显然。设R'是包含Ra的传递关系。假设RcR'，则存在Rc,但R'。由Rc可知G中有(x,y)-通路，但x,y不相邻(否则，RaR')。存在顶点序列x,v1,v2…vk-1,vk,y,满足：,,…

7、,…RaR',由R'的传递性可知：R',矛盾。RcR'。连通分支和连通图可达性关系是等价关系，相应的等价类称为连通分支。如果图G只含一个连通分支，则称G是连通图。图G是连通图当且仅当u,vVG,G中存在uv-通路。图与补图的连通G是任意的简单图，G和其补图G'中至少有一个是连通图。证明：假设G不连通。任给u,vG'：如果uvEG,则uv在G'中相邻。如果uvEG,因为G是非连通图，一定存在顶点w与u,v再不同的连通分支中，于是uwEG,

8、vwEG,所以:uwEG',vwEG',(u,w,v)是G'中的uv-通路。G'是连通图。有关连通图的一个例子G是至少含3个顶点的简单连通图，若G不是完全图，则G中一定含三个顶点u,v,w,满足：uwVG,wvVG,但uvVG。由于G非完全图，一定有顶点x,y不相邻。但G是连通图，所以G中存在xy-路径(x,v1,…,vm-1,vm=y)。其中m2。令vk是沿这条路径离x最近的与x不相邻的顶点(注意：x,y不相邻保证这个vk一定能找到)。显然k>1，则x,vk-1和v