离散数学通路、回路与图的连通性.ppt

《离散数学通路、回路与图的连通性.ppt》由会员分享，可在线阅读，更多相关《离散数学通路、回路与图的连通性.ppt（43页珍藏版）》请在三一办公上搜索。

1、1,7.2 通路、回路与图的连通性,简单通(回)路,初级通(回)路,复杂通(回)路连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥),2,在图中，一条通路是顶点和边的交替序列，以顶点 开始，以顶点结束。其中，第一条边的终点与第二 条边的始点重合.。第一条边的始点称为通路的 始点，最后一条边的终点称为通路的终点。,当通路的终点和始点重合时，称为回路。通路或回路中所含边数称为该通路或回路的长度。,一、通路和回路,3,1、简单通路：如果通路中各边都不相同。,如简单通路：v1v2 v5 v6 v2 v3 v4长度为6,如简单回路：v1v2 v3 v5 v2 v6 v1长度为6

2、,2、简单回路：如果回路中各边都不相同。,4,3、基本通路：如果通路中各个顶点都不相同。,4、基本回路：如果回路中各个顶点都不相同。,如基本通路：v1v6 v3 v4长度为3,如基本回路：v1v6 v3 v2 v1,显然，基本通路（回路）一定是简单通路（回路）。反之不然。,5,若通路(回路)中有边重复出现,则称为复杂通路(回路).,6,关于通路与回路的几点说明,表示方法 用顶点和边的交替序列(定义),如=v0e1v1e2elvl 用边的序列,如=e1e2el 简单图中,用顶点的序列,如=v0v1vl 非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构

3、成长度为2的圈.在无向简单图中,所有圈的长度3;在有向简单图中,所有圈的长度2.,7,在两种意义下计算的圈个数 定义意义下 在无向图中,一个长度为l(l3)的圈看作2l个不同的圈.如v0v1v2v0,v1v2v0v1,v2v0v1v2看作3个不同的圈.在有向图中,一个长度为l(l3)的圈看作l个不同的圈.同构意义下 所有长度相同的圈都是同构的,因而是1个圈.,8,定理 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.,推论 在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初级通路.,定理 在一个n阶图G中

4、，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.,推论 在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.,9,在图G中，如果A到B存在一条通路，则称A到B是可达的。1、无向图的连通性如果无向图中，任意两点是可达的，图为连通图。否则为不连通图。当图是不连通时，定是由几个连通子图构成。称这样的连通图是连通分支。,二、图的连通性：,10,无向图的连通性,设无向图G=,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系 R=|u,v V且uv是V上的等价关系连通图:平凡图,任意两点都连通的图连通分支:V关于R的等价类的导出子图 设V/R=

5、V1,V2,Vk,GV1,GV2,GVk是G的连通分支,其个数记作p(G)=k.G是连通图 p(G)=1,11,设 A=1,2,8,R=|x,yAxy(mod 3)即:A上模3等价关系的关系图为:,12,【例】求证：若图中只有两个奇度数顶点，则二顶点必连通。证明 用反证法来证明。设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。,13,【例】在一次国际会议中，由七人组成的小组a,b,c,d,e,f,g中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语

6、；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？,14,解 用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。,15,定理 在n阶简单图G,如果对G的每对顶点u和v,deg(u)+deg(v)n1,则G是连通图。证明 假设G不连通,则G至少有两个分图。设其中一个分图含有q个顶点,而其余各分图共含有n q个顶点。在这两部分中各取一个顶点u和v,则0de

7、g(u)q 1,0deg(v)n q 1,因此deg(u)+deg(v)n 2,这与题设deg(u)+deg(v)n 1矛盾。,16,短程线与距离,u与v之间的短程线:u与v之间长度最短的通路(u与v连通)u与v之间的距离d(u,v):u与v之间短程线的长度若u与v不连通,规定d(u,v)=.性质：d(u,v)0,且d(u,v)=0 u=v d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w),17,在实际问题中,除了考察一个图是否连通外,往往还要研究一个图连通的程度,作为某些系统的可靠性度量。图的连通性在计算机网、通信网和电力网等方面有着重要的应用。,图的连通性的应用,18,点割

8、集,在连通图中，如果删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去某个顶点v，就是将顶点v和与v关联的所有的边均删去；删除边只需将该边删除,19,例如”国际会议对话”任何一人请假，图G-v还连通，小组对话仍可继续进行，但如果f、g二人同时不在，G-f，g是分离图，则小组中的对话无法再继续进行。,20,点割集,记 Gv:从G中删除v及关联的边 GV:从G中删除V中所有的顶点及关联的边 Ge:从G中删除e GE:从G中删除E中所有边定义 设无向图G=,VV,若p(GV)p(G)且VV,p(GV)=p(G),则称V为G的点割集.若v为点割集,则称v为割点.,21,点割集(续),例 v1,v

9、4,v6是点割集,v6是割点.,22,例 v2,v7,v3,v4为点割集,v3,v4均为割点例 在下图中的那些是割点 v3和v2都是割点,v2,v3,v4,v1,v2,v4,v5都不是点割集。,23,边割集,定义 设无向图G=,EE,若p(GE)p(G)且EE,p(GE)=p(G),则称E为G的边割集.若e为边割集,则称e为割边或桥.在下图中，e1,e2，e1,e3,e5,e6，e8等是边割集，e8是桥，e7,e9,e5,e6是边割集吗？,24,图中 e1,e2,e1,e3,e4,e6,e7,e8,e2,e3,e4,e2,e3,e5,e4,e5,e7,e9,e8,e9,等都是割集,其中e6为桥

10、。割点或割边都是图连通的关键部位,并不是所有的图都有割点或割边。没有割点和割边的连通图,需要去掉几条边或几个点,图才会变得不连通。,25,几点说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)2,一个连通图G，若存在点割集和边割集，一般并不唯一，且各个点（边）割集中所含的点（边）的个数也不尽相同。我们用含元素个数最少的点割集和边割集来刻画它的连通度,26,下面从数量观点来描述图的连通性。定义 设G=(V,E)是连通图,k(G)=min|V|V是G的点割集称为G的点连通度;(G)=min|E|E是G的边割集称为G的边连通度。

11、图G的点连通度是为了使G成为一个非连通图,需要删除的点的最少数目。若图G中存在割点,k(G)=1。图G的边连通度是为了使G成为一个非连通图,需要删除的边的最少数目。若图G中存在割边,(G)=1。,27,【例】下图中的两个连通图都是n=8，e=16，其中,（G1）=4,(G1）=4,（G2）=1，（G2）=3。,28,假设n个顶点代表n个站，e条边表示铁路或者桥梁或者电话线，en-1。为了使n个站之间的连接不容易被破坏，必须构造一个具有n个顶点e条边的连通图，并使其具有最大的点连通度和边连通度。按图中G1的连接法，如果3个站被破坏，或者3条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性

12、。但按图中G2的连接法，如果v站被破坏，余下的站就不能保持连通。,29,定理 对任意的图G=(V,E),有 k(G)(G)(G)(*)证明 若G是平凡图或非连通图,则 k(G)=(G)=0,上式显然成立。若G是连通图,则因每一顶点的所有关联边构成一个边割集,所以(G)(G)。下面证明k(G)(G)。若(G)=1,则G有一割边,此时 k(G)=(G)=1,(*)式成立。,30,若(G)2,则必可删去某(G)边,使G不连通,而删去其中(G)1条边,G仍然连通,且有一条桥e=u,v。对(G)1条边中的每一条边都选取一个不同于u,v的顶点,把这些(G)1个顶点删去则必至少删去(G)1边。若剩下的图是不

13、连通的,则k(G)(G)1(G);若剩下的图是连通的,则e仍是桥,此时再删去u和v,就必产生一个非连通图,也有k(G)(G)。综上所述,对任意的图G,有k(G)(G)(G)。,31,例 在下图中,k(G)=1,(G)=2,(G)=3,定义 设有图G=(V,E),若k(G)h,则称G是h-连通的;若(G)h,则称G是h-边连通的。例 上图所示的图是1-连通的,是2-边连通的。,32,简单图都是1-连通的和1-边连通的。n阶完全图是(n1)-连通的和(n1)-边连通的。对于任何n阶连通图,当且仅当没有割点时,它是2-连通的;当且仅当没有割边时,它是2-边连通的。若图G是h-连通的,则G也是h-边连

14、通的。(k(G)(G)由定义可知,若h1h2,图G是h1-连通的,则G也是h2-连通的。若h1h2,图G是h1-边连通的,则G也是h2-边连通。一个图的连通度越大,它的连通性能就越好。,33,例如:下图的边连通度是3，所以它是3边连通的，也是2边连通的和1-边连通的，但不是4边连通的。,34,2、有向图的连通性,对于有向图，“图中任意两点都有通路相连”，这个要求很高，因为有向图虽然是连在一起的，但受到边的方向的限制，任意两点不一定有通路。以下分三种情况讨论：,35,1）强连通图：有向图中，任意A、B是互为可达的。如图(a)2）单向连通图：在有向图中，任意两点A、B存在着A到B的通路 或存在着B

15、到A的通路。如图(b)3）弱连通图：在有向图中，如果其底图是无向连通图。如图(c),显然：在有向图中，如果有一条通过图中所有点的回路，则此图是强连通的。如果有一条通过图中所有点的通路，则此图是单向连通图。,(a)(b)(c),36,单向连通图都是弱连通图，但弱连通图却不一定是单向连通图。在弱连通图中，存在这样的顶点A、B，从A到B不可达，且从B 到A也不可达。强连通图既是单向连通图，又是弱连通图。即强连通单向连通弱连通,37,有向图的连通性(续),定理(强连通判别法)D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)D单向连通当且仅当D中存在经过每个顶点至少一次的通路,3

16、8,思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪些 是弱连通图。,(a),(b),(d),(c),答案:(a),(d)是强连通图,(b)是单向连通图,(c)是弱连通图.,39,有向图的短程线与距离,u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离d:u到v的短程线的长度若u不可达v,规定d=.性质：d0,且d=0 u=v d+d d 注意:没有对称性,40,定义：设G是有向图，G是其子图，若G是强连通的（单向连通的，弱连通的）且没有包含 G的更大的子图是强连通的（单向连通的，弱连通的），则称G是G的 极大强连通子图（极大单向连通子图，极大 弱连通子图），也称为强分支（单向分支，弱分支）。,41,【例】求下图中G的所有强分图、单向分图和弱分图。,42,解 V1=v1，v4，v5、V2=v2，v6、V3=v3的导出子图GV1、GV2、GV3均是G的强分图见图（a）G1、G2、G3；V4=v1，v2，v3，v4，v6、V5=v2，v3，v6的导出子图 GV4、GV5均是G的单向分图（见图（b）G4、G5）；G是弱连通的，故G的弱分图就是G自身。,43,