《离散数学通路、回路与图的连通性.ppt》由会员分享，可在线阅读，更多相关《离散数学通路、回路与图的连通性.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、7.2 通路、回路与图的连通性通路、回路与图的连通性 简简单单通通(回回)路路,初初级级通通(回回)路路,复复杂杂通通(回回)路路连通图连通图,连通分支连通分支弱连通图弱连通图,单向连通图单向连通图,强连通图强连通图点割集与割点点割集与割点边割集与割边边割集与割边(桥桥)1 在图中，一条通路是顶点和边的交替序列，以顶点在图中，一条通路是顶点和边的交替序列，以顶点 开始，以顶点结束。其中，第一条边的终点与第二开始，以顶点结束。其中，第一条边的终点与第二 条边的始点重合条边的始点重合.。第一条边的始点称为通路的。第一条边的始点称为通路的 始点，最后一条边的终点称为通路的终点。始点，最后一条边的终点
2、称为通路的终点。当通路的终点和始点重合时，称为回路。当通路的终点和始点重合时，称为回路。通路或回路中所含边数称为该通路或回路的长度。通路或回路中所含边数称为该通路或回路的长度。一、通路和回路一、通路和回路 21、简单通路：如果通路中各边都不相同。、简单通路：如果通路中各边都不相同。如简单通路：如简单通路：v1v2 v5 v6 v2 v3 v4长度为长度为6如简单回路：如简单回路：v1v2 v3 v5 v2 v6 v1长度为长度为62、简单回路：如果回路中各边都不相同。简单回路：如果回路中各边都不相同。33、基本通路：如果通路中各个顶点都不相同。、基本通路：如果通路中各个顶点都不相同。4、基本回
3、路：如果回路中各个顶点都不相同。、基本回路：如果回路中各个顶点都不相同。如基本通路：如基本通路：v1v6 v3 v4长度为长度为3如基本回路：如基本回路：v1v6 v3 v2 v1显然，基本通路（回路）一定是简单通路（回路）。显然，基本通路（回路）一定是简单通路（回路）。反之不然。反之不然。4若通路若通路(回路回路)中有边重复出现中有边重复出现,则称为则称为复杂通路复杂通路(回路回路).5关于通路与回路的几点说明关于通路与回路的几点说明n表示方法表示方法 用用 顶顶 点点 和和 边边 的的 交交 替替 序序 列列(定定 义义),如如=v0e1v1e2elvl 用边的序列用边的序列,如如=e1e
4、2el 简单图中简单图中,用顶点的序列用顶点的序列,如如=v0v1vl 非简单图中非简单图中,可用混合表示法可用混合表示法,如如=v0v1e2v2e5v3v4v5n环是长度为环是长度为1的圈的圈,两条平行边构成长度为两条平行边构成长度为2的圈的圈.n在无向简单图中在无向简单图中,所有圈的长度所有圈的长度 3;在有向简单图在有向简单图中中,所有圈的长度所有圈的长度 2.6n在两种意义下计算的圈个数在两种意义下计算的圈个数 定义意义下定义意义下 在在无无向向图图中中,一一个个长长度度为为l(l 3)的的圈圈看看作作2l个个不不同同的的圈圈.如如v0v1v2v0,v1v2v0v1,v2v0v1v2看
5、看作作3个个不不同同的的圈圈.在在有有向向图图中中,一一个个长长度度为为l(l 3)的的圈圈看看作作l个个不不同同的的圈圈.同构意义下同构意义下 所有长度相同的圈都是同构的所有长度相同的圈都是同构的,因而是因而是1个圈个圈.7定理定理 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vi vj）存在通）存在通路，则从路，则从vi到到vj存在长度小于等于存在长度小于等于n 1的通路的通路.推论推论 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vi vj）存在通）存在通路，则从路，则从vi到到vj存在长度小于等于存在长度小于等于n 1的初级通路的初级通路.定理定理 在一个在一个n阶
6、图阶图G中，若存在中，若存在vi到自身的回路，到自身的回路，则一定存在则一定存在vi到自身长度小于等于到自身长度小于等于n的回路的回路.推论推论 在一个在一个n阶图阶图G中，若存在中，若存在vi到自身的简单到自身的简单回路，则一定存在长度小于等于回路，则一定存在长度小于等于n的初级回路的初级回路.8在图在图G中，如果中，如果A到到B存在一条通路，则称存在一条通路，则称A到到B是可达的。是可达的。1、无向图的连通性、无向图的连通性如果无向图中，任意两点是可达的，图为连通图。否则为如果无向图中，任意两点是可达的，图为连通图。否则为不连通图。不连通图。当图是不连通时，定是由几个连通子图构成。称这样的
7、连当图是不连通时，定是由几个连通子图构成。称这样的连通图是连通分支。通图是连通分支。二、图的连通性：二、图的连通性：9无向图的连通性无向图的连通性 设设无向图无向图G=,u与与v连通连通:若若u与与v之间有通路之间有通路.规定规定u与自身总连通与自身总连通.连通关系连通关系 R=|u,v V且且u v是是V上的等价关系上的等价关系连通图连通图:平凡图平凡图,任意两点都连通的图任意两点都连通的图连通分支连通分支:V关于关于R的的等价类的导出子图等价类的导出子图 设设V/R=V1,V2,Vk,GV1,GV2,GVk是是G的连通分支的连通分支,其个数记作其个数记作p(G)=k.G是连通图是连通图 p
8、(G)=110设设 A=1,2,8,R=|x,yAxy(mod 3)即即:A上模上模3等价关系的关系图为等价关系的关系图为:11n【例例】求求证证：若若图图中中只只有有两两个个奇奇度度数数顶顶点点，则则二二顶点必连通。顶点必连通。n 证明证明 用反证法来证明。用反证法来证明。n 设设二二顶顶点点不不连连通通，则则它它们们必必分分属属两两个个不不同同的的连连通通分分支支，而而对对于于每每个个连连通通分分支支，作作为为G的的子子图图只只有有一一个个奇奇度度数数顶顶点点，余余者者均均为为偶偶度度数数顶顶点点，与与握握手手定定理理推推论论矛矛盾盾，因因此此，若若图图中中只只有有两两个个奇奇度度数数顶顶
9、点点，则则二顶点必连通。二顶点必连通。12【例例】在在一一次次国国际际会会议议中中，由由七七人人组组成成的的小小组组a,b,c,d,e,f,g中中，a会会英英语语、阿阿拉拉伯伯语语；b会会英英语语、西西班班牙牙语语；c会会汉汉语语、俄俄语语；d会会日日语语、西西班班牙牙语语；e会会德德语语、汉汉语语和和法法语语；f会会日日语语、俄俄语语；g会会英英语语、法法语语和和德德语语。问问：他他们们中中间间任任何何二二人人是是否否均均可可对对话话（必必要要时时可可通过别人翻译）？通过别人翻译）？13n解解 用用顶顶点点代代表表人人，如如果果二二人人会会同同一一种种语语言言，则则在在代代表表二二人人的的顶
10、顶点点间间连连边边，于于是是得得到到下下图图。问问题题归归结结为为：在在这这个个图图中中，任任何何两两个个顶顶点点间间是是否否都都存存在在着着通通路路？由由于于下下图图是是一一个个连连通通图图，因因此此，必必要要时时通通过过别别人翻译，他们中间任何二人均可对话。人翻译，他们中间任何二人均可对话。14定理定理 在在n阶简单图阶简单图G,如果对如果对G的的每对顶点每对顶点u和和v,deg(u)+deg(v)n1,则则G是连通图。是连通图。证明证明 假设假设G不连通不连通,则则G至少有两个分图至少有两个分图。设设其其中中一一个个分分图图含含有有q个个顶顶点点,而而其其余余各各分分图图共共含含有有n
11、q个顶点。个顶点。在这两部分中各取一个顶点在这两部分中各取一个顶点u和和v,则则0deg(u)q 1,0deg(v)n q 1,因此因此deg(u)+deg(v)n 2,这与题设这与题设deg(u)+deg(v)n 1矛盾。矛盾。15短程线与距离短程线与距离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
12、(u,w)16n在实际问题中在实际问题中,除了考察一个图是否除了考察一个图是否连通外连通外,往往还要研究一个图往往还要研究一个图连通的连通的程度程度,作为某些系统的作为某些系统的可靠性度量可靠性度量。n图的连通性在计算机网、通信网和图的连通性在计算机网、通信网和电力网等方面有着重要的应用。电力网等方面有着重要的应用。图的连通性的应用图的连通性的应用17点割集点割集 在在连连通通图图中中，如如果果删删去去一一些些顶顶点点或或边边，则则可可能能会会影影响响图图的的连连通通性性。所所谓谓从从图图中中删删去去某某个个顶顶点点v，就就是是将将顶顶点点v和和与与v关关联联的的所所有的边均删去；有的边均删去
13、；删除边只需将该边删除删除边只需将该边删除18 例例如如”国际会议对话”任任何何一一人人请请假假，图图G-v还还连连通通，小小组组对对话话仍仍可可继继续续进进行行，但但如如果果f、g二二人人同同时时不不在在，G-f，g是是分分离离图图，则则小小组组中中的的对话无法再继续进行。对话无法再继续进行。19点割集点割集 记记 G v:从从G中删除中删除v及关联的边及关联的边 G V:从从G中中删删除除V 中中所所有有的的顶顶点点及及关关联联的的边边 G e:从从G中删除中删除e G E:从从G中删除中删除E 中所有边中所有边定定义义 设设无无向向图图G=,VV,若若p(G V)p(G)且且 V V,p
14、(G V)=p(G),则则称称V 为为G的的点割集点割集.若若v为点割集为点割集,则称则称v为为割点割点.20点割集点割集(续续)例例 v1,v4,v6是点割集是点割集,v6是割点是割点.21例例 v2,v7,v3,v4为为点割集点割集,v3,v4均为均为割点割点例例 在下图中的那些是在下图中的那些是割点割点 v3和和v2都都是割点是割点,v2,v3,v4,v1,v2,v4,v5都都不不是点割集。是点割集。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e522边割集边割集定定义义 设设无无向向图图G=,EE,若若p(G E)p(G)且且 E E,p(G E)=p(G),则则称称E
15、 为为G的的边边割割集集.若若e为为边边割割集集,则称则称e为为割边割边或或桥桥.在下图中，在下图中，e1,e2，e1,e3,e5,e6，e8等是边割集，等是边割集，e8是桥，是桥，e7,e9,e5,e6是边割集吗？是边割集吗？23图中图中 e1,e2,e1,e3,e4,e6,e7,e8,e2,e3,e4,e2,e3,e5,e4,e5,e7,e9,e8,e9,等都是割集等都是割集,其中其中e6为桥。为桥。n割点或割边都是图连通的割点或割边都是图连通的关键部位关键部位,并不是所有的并不是所有的图都有割点或割边图都有割点或割边。n没有割点和割边的连通图没有割点和割边的连通图,需要去掉几条边或几个需
16、要去掉几条边或几个点点,图才会变得不连通。图才会变得不连通。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e524几点说明：几点说明：Kn无点割集无点割集n阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集.若若G连通，连通，E 为边割集，则为边割集，则p(G E)=2若若G连通，连通，V 为点割集，则为点割集，则p(G V)2 一个连通图一个连通图G，若存在点割集和边割集，一般，若存在点割集和边割集，一般并不唯一，且各个点（边）割集中所含的点并不唯一，且各个点（边）割集中所含的点（边）的个数也不尽相同。我们用含元素个数（边）的个数也不尽相同。我们用含元素个数最少的点割集和
17、边割集来刻画它的连通度最少的点割集和边割集来刻画它的连通度25下面从下面从数量观点数量观点来描述图的连通性。来描述图的连通性。定义定义 设设G=(V,E)是连通图是连通图,k(G)=min|V|V 是是G的点割集的点割集称为称为G的的点点连通度连通度;(G)=min|E|E 是是G的边割集的边割集称为称为G的的边边连通度连通度。n图图G的点连通度是为了使的点连通度是为了使G成为一个成为一个非连通图非连通图,需需要删除的点的最少数目要删除的点的最少数目。若图若图G中存在割点中存在割点,k(G)=1。n图图G的的边边连连通通度度是是为为了了使使G成成为为一一个个非非连连通通图图,需需要删除的边的最
18、少数目要删除的边的最少数目。若图若图G中存在割边中存在割边,(G)=1。26【例例】下图中的两个连通图都是下图中的两个连通图都是n=8，e=16，其中其中,（G1）=4,(G1）=4,（G2）=1，（G2）=3。27n假设假设n n个顶点代表个顶点代表n个站，个站，e e条边表示铁路或者条边表示铁路或者桥梁或者电话线，桥梁或者电话线，en-1en-1。为了使为了使n n个站之间个站之间的连接不容易被破坏，必须构造一个具有的连接不容易被破坏，必须构造一个具有n n个个顶点顶点e e条边的连通图，并使其具有最大的点连条边的连通图，并使其具有最大的点连通度和边连通度。按图中通度和边连通度。按图中G
19、G1 1的连接法，如果的连接法，如果3 3个站被破坏，或者个站被破坏，或者3 3条铁路被破坏，余下的站条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性。仍能继续相互联系，也就是仍具有连通性。但按图中但按图中G G2 2的连接法，如果的连接法，如果v v站被破坏，余下站被破坏，余下的站就不能保持连通。的站就不能保持连通。28定理定理 对任意的图对任意的图G=(V,E),有有 k(G)(G)(G)(*)证明证明 若若G是平凡图或非连通图是平凡图或非连通图,则则 k(G)=(G)=0,上式显然成立。上式显然成立。n若若G是连通图是连通图,则因则因每一顶点的所有关联边每一顶点的所有关联边构成
20、一构成一个个边割集边割集,所以所以 (G)(G)。n下面证明下面证明k(G)(G)。若若 (G)=1,则则G有一割边有一割边,此时此时 k(G)=(G)=1,(*)式成立。式成立。29n若若 (G)2,则必可删去某则必可删去某 (G)边边,使使G不连通不连通,而而删去其中删去其中(G)1条边条边,G仍然连通仍然连通,且有一条桥且有一条桥e=u,v。n对对 (G)1条边中的每一条边都选取一个不同于条边中的每一条边都选取一个不同于u,v的顶点的顶点,把这些把这些 (G)1个顶点删去则必至少删个顶点删去则必至少删去去 (G)1边。边。n若剩下的图是若剩下的图是不连通不连通的的,则则k(G)(G)1
21、(G);n若剩下的图是若剩下的图是连通连通的的,则则e仍是桥仍是桥,此时此时再删去再删去u和和v,就必产生一个就必产生一个非连通图非连通图,也有也有k(G)(G)。n综上所述综上所述,对任意的图对任意的图G,有有k(G)(G)(G)。30例例 在下图中在下图中,k(G)=1,(G)=2,(G)=3定义定义 设有图设有图G=(V,E),若若k(G)h,则称则称G是是h-连通连通的的;若若(G)h,则称则称G是是h-边连通边连通的。的。例例 上上图所示的图是图所示的图是1-连通连通的的,是是2-边连通边连通的。的。31n简单图都是简单图都是1-连通的和连通的和1-边连通的边连通的。nn阶完全图是阶
22、完全图是(n1)-连通的和连通的和(n1)-边连通的边连通的。n对于任何对于任何n阶连通图阶连通图,当且仅当没有割点时当且仅当没有割点时,它是它是2-连通连通的的;n当且仅当没有割边时当且仅当没有割边时,它是它是2-边连通的边连通的。n若图若图G是是h-连通的连通的,则则G也是也是h-边边连通的。连通的。(k(G)(G)n由定义可知由定义可知,若若h1h2,图图G是是h1-连通的连通的,则则G也是也是h2-连通的。连通的。n若若h1h2,图图G是是h1-边连通的边连通的,则则G也是也是h2-边边连通。连通。n一个一个图的连通度越大图的连通度越大,它的连通性能就越好它的连通性能就越好。32n例例
23、如如:下下图图的的边边连连通通度度是是3，所所以以它它是是3边边连连通通的的，也也是是2边边连连通通的的和和1-边边连连通通的的，但但不是不是4边连通的。边连通的。332、有向图的连通性、有向图的连通性对于有向图，对于有向图，“图中任意两点都有通路相连图中任意两点都有通路相连”，这个要求，这个要求很高，因为有向图虽然是连在一起的，但受到边的方向很高，因为有向图虽然是连在一起的，但受到边的方向的限制，任意两点不一定有通路。以下分三种情况讨论：的限制，任意两点不一定有通路。以下分三种情况讨论：341）强连通图：有向图中，任意）强连通图：有向图中，任意A、B是互为可达的。如图是互为可达的。如图(a)
24、2）单向连通图：在有向图中，任意两点）单向连通图：在有向图中，任意两点A、B存在着存在着A到到B的通路的通路 或存在着或存在着B到到A的通路。如图的通路。如图(b)3）弱连通图：在有向图中，如果其底图是无向连通图。如图）弱连通图：在有向图中，如果其底图是无向连通图。如图(c)显然：在有向图中，如果有一条通过图中所有点的回路，显然：在有向图中，如果有一条通过图中所有点的回路，则此图是强连通的。则此图是强连通的。如果有一条通过图中所有点的通路，如果有一条通过图中所有点的通路，则此图是单向连通图。则此图是单向连通图。(a)(b)(c)35单向连通图都是弱连通图，但弱连通图单向连通图都是弱连通图，但弱
25、连通图却不一定是单向连通图。却不一定是单向连通图。在弱连通图中，存在这样的顶点在弱连通图中，存在这样的顶点A、B，从从A到到B不可达，且从不可达，且从B 到到A也不可达。也不可达。强连通图既是单向连通图，又是弱连通图。强连通图既是单向连通图，又是弱连通图。即即强连通强连通单向连通单向连通弱连通弱连通 36有向图的连通性有向图的连通性(续续)定定理理(强强连连通通判判别别法法)D强强连连通通当当且且仅仅当当D中中存存在在经经过每个顶点至少一次的回路过每个顶点至少一次的回路定定理理(单单向向连连通通判判别别法法)D单单向向连连通通当当且且仅仅当当D中中存存在经过每个顶点至少一次的通路在经过每个顶点
26、至少一次的通路(1)(2)(3)例例 下图下图(1)强连通强连通,(2)单连通单连通,(3)弱弱连通连通37思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪些些 是弱连通图。是弱连通图。(a)(b)(d)(c)答案答案:(a),(d)是强连通图是强连通图,(b)是单向连通图是单向连通图,(c)是弱连通是弱连通图图.38有向图的有向图的短程线与距离短程线与距离u到到v的短程线的短程线:u到到v长度最短的通路长度最短的通路(u可达可达v)u与与v之间的距离之间的距离d:u到到v的短程线的长度的短程线的长度若若u不可达不可达v,规定规定d=
27、.性质：性质：d 0,且且d=0 u=v d+d d 注意注意:没有对称性没有对称性39定义：设定义：设G是有向图，是有向图，G是其子图，是其子图，若若G是强连通的（单向连通的，弱连通的）是强连通的（单向连通的，弱连通的）且没有包含且没有包含 G的更大的子图是强连通的的更大的子图是强连通的 （单向连通的，弱连通的），则称（单向连通的，弱连通的），则称G是是G的的 极大强连通子图（极大单向连通子图，极大极大强连通子图（极大单向连通子图，极大 弱连通子图），弱连通子图），也称为强分支（单向分支，弱分支）。也称为强分支（单向分支，弱分支）。40【例】求下图中求下图中G的所有强分图、单向分图和弱分图。的所有强分图、单向分图和弱分图。41n解解 nV1=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的导出子图的导出子图n GV4、GV5均均是是G的的单单向向分分图图（见见图图（b）G4、G5）；G是是弱弱连连通通的的，故故G的的弱弱分图就是分图就是G自身。自身。4243