1、12021/6/77.2通路、回路与图的连通性通路、回路与图的连通性简单通简单通(回回)路路,初级通初级通(回回)路路,复杂通复杂通(回回)路路连通图连通图,连通分支连通分支弱连通图弱连通图,单向连通图单向连通图,强连通图强连通图点割集与割点点割集与割点边割集与割边边割集与割边(桥桥)22021/6/7在图中，一条通路是顶点和边的交替序列，以顶点在图中，一条通路是顶点和边的交替序列，以顶点开始，以顶点结束。其中，第一条边的终点与第二开始，以顶点结束。其中，第一条边的终点与第二条边的始点重合条边的始点重合.。第一条边的始点称为通路的。第一条边的始点称为通路的
2、始点，最后一条边的终点称为通路的终点。始点，最后一条边的终点称为通路的终点。当通路的终点和始点重合时，称为回路。当通路的终点和始点重合时，称为回路。通路或回路中所含边数称为该通路或回路的长度。通路或回路中所含边数称为该通路或回路的长度。一、通路和回路一、通路和回路32021/6/71、简单通路：如果通路中各边都不相同。、简单通路：如果通路中各边都不相同。如简单通路：如简单通路：v1v2v5v6v2v3v4长度为长度为6如简单回路：如简单回路：v1v2v3v5v2v6v1长度为长度为62、简单回路：如果回路中各边都不相同。、简单回路：如果回路中各边都不相同。
3、42021/6/73、基本通路：如果通路中各个顶点都不相同。、基本通路：如果通路中各个顶点都不相同。4、基本回路：如果回路中各个顶点都不相同。、基本回路：如果回路中各个顶点都不相同。如基本通路：如基本通路：v1v6v3v4长度为长度为3如基本回路：如基本回路：v1v6v3v2v1显然，基本通路（回路）一定是简单通路（回路）。显然，基本通路（回路）一定是简单通路（回路）。反之不然。反之不然。52021/6/7若通路若通路(回路回路)中有边重复出现中有边重复出现,则称为则称为复杂通路复杂通路(回路回路).62021/6/7关于通路与回路的几点说明关于通路与回
4、路的几点说明n表示方法表示方法用顶点和边的交替序列用顶点和边的交替序列(定义定义),如如=v0e1v1e2elvl用边的序列用边的序列,如如=e1e2el简单图中简单图中,用顶点的序列用顶点的序列,如如=v0v1vl非简单图中非简单图中,可用混合表示法可用混合表示法,如如=v0v1e2v2e5v3v4v5n环是长度为环是长度为1的圈的圈,两条平行边构成长度为两条平行边构成长度为2的圈的圈.n在无向简单图中在无向简单图中,所有圈的长度所有圈的长度3;在有向简单图在有向简单图中中,所有圈的长度所有圈的长度2.72021/6/7n在两种意义下计算的圈
5、个数在两种意义下计算的圈个数定义意义下定义意义下在无向图中在无向图中,一个长度为一个长度为l(l3)的圈看作的圈看作2l个不同的个不同的圈圈.如如v0v1v2v0,v1v2v0v1,v2v0v1v2看作看作3个不同的圈个不同的圈.在有向图中在有向图中,一个长度为一个长度为l(l3)的圈看作的圈看作l个不同的个不同的圈圈.同构意义下同构意义下所有长度相同的圈都是同构的所有长度相同的圈都是同构的,因而是因而是1个圈个圈.82021/6/7定理定理在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vivj）存在通）存在通路，则从路，则从vi到到vj
6、存在长度小于等于存在长度小于等于n1的通路的通路.推论推论在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vivj）存在通）存在通路，则从路，则从vi到到vj存在长度小于等于存在长度小于等于n1的初级通路的初级通路.定理定理在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的回路，到自身的回路，则一定存在则一定存在vi到自身长度小于等于到自身长度小于等于n的回路的回路.推论推论在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的简单到自身的简单回路，则一定存在长度小于等于回路，则一定存在长度小于等于n的初级回路的初级回路.92021/6/7在图在图G
7、中，如果中，如果A到到B存在一条通路，则称存在一条通路，则称A到到B是可达的。是可达的。1、无向图的连通性、无向图的连通性如果无向图中，任意两点是可达的，图为连通图。否则为如果无向图中，任意两点是可达的，图为连通图。否则为不连通图。不连通图。当图是不连通时，定是由几个连通子图构成。称这样的连当图是不连通时，定是由几个连通子图构成。称这样的连通图是连通分支。通图是连通分支。二、图的连通性：二、图的连通性：102021/6/7无向图的连通性无向图的连通性设无向图设无向图G=,u与与v连通连通:若若u与与v之间有通路之间有通路.规定规定u与自身总连通与自身总连通.连通关系
8、连通关系R=|u,vV且且uv是是V上的等价关系上的等价关系连通图连通图:平凡图平凡图,任意两点都连通的图任意两点都连通的图连通分支连通分支:V关于关于R的等价类的导出子图的等价类的导出子图设设V/R=V1,V2,Vk,GV1,GV2,,GVk是是G的的连通分支连通分支,其个数记作其个数记作p(G)=k.G是连通图是连通图p(G)=1112021/6/7设设A=1,2,8,R=|x,yAxy(mod3)即即:A上模上模3等价关系的关系图为等价关系的关系图为:122021/6/7n【例】【例】求证：若图中只有两个奇度数顶点，则二求证：
9、若图中只有两个奇度数顶点，则二顶点必连通。顶点必连通。n证明证明用反证法来证明。用反证法来证明。n设二顶点不连通，则它们必分属两个不同的连通设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为分支，而对于每个连通分支，作为G的子图只有一的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。二顶点必连通。132021/6/7【例】【例】在一次国际会议中，由七人组成的小在一次国际会议中，由七人组成的小组
10、组a,b,c,d,e,f,g中，中，a会英语、阿拉伯语；会英语、阿拉伯语；b会英语、西班牙语；会英语、西班牙语；c会汉语、俄语；会汉语、俄语；d会会日语、西班牙语；日语、西班牙语；e会德语、汉语和法语；会德语、汉语和法语；f会日语、俄语；会日语、俄语；g会英语、法语和德语。问：会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可他们中间任何二人是否均可对话（必要时可通过别人翻译）？通过别人翻译）？142021/6/7dabfgcen解解用顶点代表人，如果二人会同一种语言，则在代用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到下图。
11、问题归结为：表二人的顶点间连边，于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。译，他们中间任何二人均可对话。152021/6/7定理定理在在n阶简单图阶简单图G,如果对如果对G的的每对顶点每对顶点u和和v,deg(u)+deg(v)n1,则则G是连通图。是连通图。证明证明假设假设G不连通不连通,则则G至少有两个分图至少有两个分图。设其中一个分图含有设其中一个分图含有q个顶点个顶
12、点,而其余各分图共含有而其余各分图共含有nq个顶点。个顶点。在这两部分中各取一个顶点在这两部分中各取一个顶点u和和v,则则0deg(u)q1,0deg(v)nq1,因此因此deg(u)+deg(v)n2,这与题设这与题设deg(u)+deg(v)n1矛盾。矛盾。162021/6/7短程线与距离短程线与距离u与与v之间的短程线之间的短程线:u与与v之间长度最短的通路之间长度最短的通路(u与与v连通连通)u与与v之间的距离之间的距离d(u,v):u与与v之间短程线的长之间短程线的长度度若若u与与v不连通不连通,规定规定d(u,v)=.性
13、质：性质：d(u,v)0,且且d(u,v)=0u=vd(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)172021/6/7n在实际问题中在实际问题中,除了考察一个图是否除了考察一个图是否连通外连通外,往往还要研究一个图往往还要研究一个图连通的连通的程度程度,作为某些系统的作为某些系统的可靠性度量可靠性度量。n图的连通性在计算机网、通信网和图的连通性在计算机网、通信网和电力网等方面有着重要的应用。电力网等方面有着重要的应用。图的连通性的应用图的连通性的应用182021/6/7点割集点割集在连通图中，如果删去一些顶点或边，则在连通图中，如果
14、删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去可能会影响图的连通性。所谓从图中删去某个顶点某个顶点v，就是将顶点，就是将顶点v和与和与v关联的所关联的所有的边均删去；有的边均删去；删除边只需将该边删除删除边只需将该边删除192021/6/7例如例如”国际会议对话”任何一人请假，图任何一人请假，图G-v还还连通，小组对话仍可继续进行，但如果连通，小组对话仍可继续进行，但如果f、g二二人同时不在，人同时不在，G-f，g是分离图，则小组中的是分离图，则小组中的对话无法再继续进行。对话无法再继续进行。dabfgce202021/6/7点割集点割集记记G
15、v:从从G中删除中删除v及关联的边及关联的边GV:从从G中删除中删除V中所有的顶点及关联的边中所有的顶点及关联的边Ge:从从G中删除中删除eGE:从从G中删除中删除E中所有边中所有边定义定义设无向图设无向图G=,VV,若若p(GV)p(G)且且VV,p(GV)=p(G),则称则称V为为G的的点割集点割集.若若v为点割集为点割集,则称则称v为为割点割点.212021/6/7点割集点割集((续续))例例v1,v4,v6是点割集是点割集,v6是割点是割点.222021/6/7例例v2,v7,v3,v4为
16、为点割集点割集,v3,v4均为均为割点割点例例在下图中的那些是在下图中的那些是割点割点v3和和v2都都是割点是割点,v2,v3,v4,v1,v2,v4,v5都都不不是点割集。是点割集。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e5232021/6/7边割集边割集定义定义设无向图设无向图G=,EE,若若p(GE)p(G)且且EE,p(GE)=p(G),则称则称E为为G的的边割集边割集.若若e为边割集为边割集,则称则称e为为割边割边或或桥桥.在下图中，在下图中，e1,e2，e1,e3,e5,
17、e6，e8等是边割集，等是边割集，e8是桥，是桥，e7,e9,e5,e6是边割集吗？是边割集吗？242021/6/7图中图中e1,e2,e1,e3,e4,e6,e7,e8,e2,e3,e4,e2,e3,e5,e4,e5,e7,e9,e8,e9,等都是割集等都是割集,其中其中e6为桥。为桥。n割点或割边都是图连通的割点或割边都是图连通的关键部位关键部位,并不是所有的图并不是所有的图都有割点或割边都有割点或割边。n没有割点和割边的连通图没有割点和割边的连通图,需要去掉几条边或几个点需要去掉几条边或几个点,图才会变得不连通。图才会变得不
18、连通。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e5252021/6/7几点说明：几点说明：Kn无点割集无点割集n阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集.若若G连通，连通，E为边割集，则为边割集，则p(GE)=2若若G连通，连通，V为点割集，则为点割集，则p(GV)2一个连通图一个连通图G，若存在点割集和边割集，一般，若存在点割集和边割集，一般并不唯一，且各个点（边）割集中所含的点并不唯一，且各个点（边）割集中所含的点（边）的个数也不尽相同。我们用含元素个数（边）的个数也不尽相同。我们用含元素
19、个数最少的点割集和边割集来刻画它的连通度最少的点割集和边割集来刻画它的连通度262021/6/7下面从下面从数量观点数量观点来描述图的连通性。来描述图的连通性。定义定义设设G=(V,E)是连通图是连通图,k(G)=min|V||V是是G的点割集的点割集称为称为G的的点连通点连通度度;(G)=min|E||E是是G的边割集的边割集称为称为G的的边连边连通度通度。n图图G的点连通度是为了使的点连通度是为了使G成为一个成为一个非连通图非连通图,需需要删除的点的最少数目要删除的点的最少数目。若图若图G中存在割点中存在割点,k(G)=1。
21、构造一个具有的连接不容易被破坏，必须构造一个具有nn个个顶点顶点ee条边的连通图，并使其具有最大的点连条边的连通图，并使其具有最大的点连通度和边连通度。按图中通度和边连通度。按图中GG11的连接法，如果的连接法，如果33个站被破坏，或者个站被破坏，或者33条铁路被破坏，余下的站条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性。仍能继续相互联系，也就是仍具有连通性。但按图中但按图中GG22的连接法，如果的连接法，如果vv站被破坏，余下站被破坏，余下的站就不能保持连通。的站就不能保持连通。292021/6/7定理定理对任意的图对任意的图G=(V,
22、E),有有k(G)(G)(G)(*)证明证明若若G是平凡图或非连通图是平凡图或非连通图,则则k(G)=(G)=0,上式显然成立。上式显然成立。n若若G是连通图是连通图,则因则因每一顶点的所有关联边每一顶点的所有关联边构成一构成一个个边割集边割集,所以所以(G)(G)。n下面证明下面证明k(G)(G)。若若(G)=1,则则G有一割边有一割边,此时此时k(G)=(G)=1,(*)式成立。式成立。302021/6/7n若若(G)2,则必可删去某则必可删去某(G)边边,使使G不连通不连通,而删而删去其中去其中(G
23、)1条边条边,G仍然连通仍然连通,且有一条桥且有一条桥e=u,v。n对对(G)1条边中的每一条边都选取一个不同于条边中的每一条边都选取一个不同于u,v的顶点的顶点,把这些把这些(G)1个顶点删去则必至少删个顶点删去则必至少删去去(G)1边。边。n若剩下的图是若剩下的图是不连通不连通的的,则则k(G)(G)1(G);n若剩下的图是若剩下的图是连通连通的的,则则e仍是桥仍是桥,此时此时再删去再删去u和和v,就必产生一个就必产生一个非连通图非连通图,也有也有k(G)(G)。n综上所述综上所述,对任意的图对任意的图G,有有k(G)(G)
24、(G)。312021/6/7例例在下图中在下图中,k(G)=1,(G)=2,(G)=3定义定义设有图设有图G=(V,E),若若k(G)h,则称则称G是是h-连通连通的的;若若(G)h,则称则称G是是h-边连通边连通的。的。例例上上图所示的图是图所示的图是1-连通连通的的,是是2-边连通边连通的。的。322021/6/7n简单图都是简单图都是1-连通的和连通的和1-边连通的边连通的。nn阶完全图是阶完全图是(n1)-连通的和连通的和(n1)-边连通的边连通的。n对于任何对于任何n阶连通图阶连通图,当且仅当没有割点时当且仅当没有割点
25、时,它是它是2-连通连通的的;n当且仅当没有割边时当且仅当没有割边时,它是它是2-边连通的边连通的。n若图若图G是是h-连通的连通的,则则G也是也是h-边边连通的。连通的。(k(G)(G)n由定义可知由定义可知,若若h1h2,图图G是是h1-连通的连通的,则则G也是也是h2-连连通的。通的。n若若h1h2,图图G是是h1-边连通的边连通的,则则G也是也是h2-边边连通。连通。n一个一个图的连通度越大图的连通度越大,它的连通性能就越好它的连通性能就越好。332021/6/7n例如例如:下图的边连通度是下图的边连通度是3，所以它是，所以它是3边边连通的，也
26、是连通的，也是2边连通的和边连通的和1-边连通的，边连通的，但不是但不是4边连通的。边连通的。342021/6/72、有向图的连通性、有向图的连通性对于有向图，对于有向图，“图中任意两点都有通路相连图中任意两点都有通路相连”，这个要求，这个要求很高，因为有向图虽然是连在一起的，但受到边的方向很高，因为有向图虽然是连在一起的，但受到边的方向的限制，任意两点不一定有通路。以下分三种情况讨论：的限制，任意两点不一定有通路。以下分三种情况讨论：352021/6/71）强连通图：有向图中，任意）强连通图：有向图中，任意A、B是互为可达的。如图是互为可达的。如图(a)2）单向连通图：
27、在有向图中，任意两点）单向连通图：在有向图中，任意两点A、B存在着存在着A到到B的通路的通路或存在着或存在着B到到A的通路。如图的通路。如图(b)3）弱连通图：在有向图中，如果其底图是无向连通图。如图）弱连通图：在有向图中，如果其底图是无向连通图。如图(c)显然：在有向图中，如果有一条通过图中所有点的回路，显然：在有向图中，如果有一条通过图中所有点的回路，则此图是强连通的。则此图是强连通的。如果有一条通过图中所有点的通路，如果有一条通过图中所有点的通路，则此图是单向连通图。则此图是单向连通图。(a)(b)(c)362021/6/7单向连通图都是弱连通图，但弱连通图单向连
28、通图都是弱连通图，但弱连通图却不一定是单向连通图。却不一定是单向连通图。在弱连通图中，存在这样的顶点在弱连通图中，存在这样的顶点A、B，从从A到到B不可达，且从不可达，且从B到到A也不可达。也不可达。强连通图既是单向连通图，又是弱连通图。强连通图既是单向连通图，又是弱连通图。即即强连通强连通单向连通单向连通弱连通弱连通372021/6/7有向图的连通性有向图的连通性((续续))定理定理(强连通判别法强连通判别法)D强连通当且仅当强连通当且仅当D中存在经过中存在经过每个顶点至少一次的回路每个顶点至少一次的回路定理定理(单向连通判别法单向连通判别法)D单向连通当且仅当单向连通当且仅当D中存在中存在经过每个顶点至少一次的通路经过每个顶点至少一次的通路(1)(2)(3)例例下图下图(1)强连通强连通,(2)单连通单连通,(3)弱连通弱连通38