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

17.2通路、回路与图的连通性简单通(回)路,初级通(回)路,复杂通(回)路连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)2在图中，一条通路是顶点和边的交替序列，以顶点开始，以顶点结束。其中，第一条边的终点与第二条边的始点重合…...。第一条边的始点称为通路的始点，最后一条边的终点称为通路的终点。当通路的终点和始点重合时，称为回路。通路或回路中所含边数称为该通路或回路的长度。一、通路和回路31、简单通路：如果通路中各边都不相同。如简单通路：v1→v2→v5→v6→v2→v3→v4长度为6如简单回路：v1→v2→v3→v5→v2→v6→v1长度为62、简单回路：如果回路中各边都不相同。43、基本通路：如果通路中各个顶点都不相同。4、基本回路：如果回路中各个顶点都不相同。如基本通路：v1→v6→v3→v4长度为3如基本回路：v1→v6→v3→v2→v1显然，基本通路（回路）一定是简单通路（回路）。反之不然。5若通路(回路)中有边重复出现,则称为复杂通路(回路).6关于通路与回路的几点说明表示方法①用顶点和边的交替序列(定义),如=v0e1v1e2…elvl②用边的序列,如=e1e2…el③简单图中,用顶点的序列,如=v0v1…vl④非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.在无向简单图中,所有圈的长度3;在有向简单图中,所有圈的长度2.7在两种意义下计算的圈个数①定义意义下在无向图中,一个长度为l(l3)的圈看作2l个不同的圈.如v0v1v2v0,v1v2v0v1,v2v0v1v2看作3个不同的圈.在有向图中,一个长度为l(l3)的圈看作l个不同的圈.②同构意义下所有长度相同的圈都是同构的,因而是1个圈.8定理在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的通路.推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初级通路.定理在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.9在图G中，如果A到B存在一条通路，则称A到B是可达的。1、无向图的连通性如果无向图中，任意两点是可达的，图为连通图。否则为不连通图。当图是不连通时，定是由几个连通子图构成。称这样的连通图是连通分支。二、图的连通性：10无向图的连通性设无向图G=V,E,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={u,v|u,vV且uv}是V上的等价关系连通图:平凡图,任意两点都连通的图连通分支:V关于R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,其个数记作p(G)=k.G是连通图p(G)=111设A={1,2,…,8},R={x,y|x,y∈A∧x≡y(mod3)}即:A上模3等价关系的关系图为:12【例】求证：若图中只有两个奇度数顶点，则二顶点必连通。证明用反证法来证明。设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。13【例】在一次国际会议中，由七人组成的小组{a,b,c,d,e,f,g}中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？14dabfgce解用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。15定理在n阶简单图G,如果对G的每对顶点u和v,deg(u)+deg(v)≥n–1,则G是连通图。证明假设G不连通,则G至少有两个分图。设其中一个分图含有q个顶点,而其余各分图共含有n–q个顶点。在这两部分中各取一个顶点u和v,则0≤deg(u)≤q–1,0≤deg(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=vd(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)17在实际问题中,除了考察一个图是否连通外,往往还要研究一个图连通的程度,作为某些系统的可靠性度量。图的连通性在计算机网、通信网和电力网等方面有着重要的应用。图的连通性的应用18点割集在连通图中，如果删去一些顶点或边，则可能会影响图的连通性。所谓从图中删去某个顶点v，就是将顶点v和与v关联的所有的边均删去；删除边只需将该边删除19例如”国际会议对话”任何一人请假，图G-v还连通，小组对话仍可继续进行，但如果f、g二人同时不在，G-{f，g}是分离图，则小组中的对话无法再继续进行。dabfgce20点割集记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义设无向图G=V,E,VV,若p(GV)p(G)且VV,p(GV)=p(G),则称V为G的点割集.若{v}为点割集,则称v为割点.21点割集(续)例{v1,v4},{v6}是点割集,v6是割点.22例{v2,v7},{v3},{v4}为点割集,{v3},{v4}均为割点例在下图中的那些是割点{v3}和{v2}都是割点,{v2,v3,v4},{v1,v2,v4,v5}都不是点割集。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e523边割集定义设无向图G=V,E,EE,若p(GE)p(G)且EE,p(GE)=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}为桥。割点或割边都是图连通的关键部位,并不是所有的图都有割点或割边。没有割点和割边的连通图,需要去掉几条边或几个点,图才会变得不连通。v7v2v3v1v4v5v6e4e2e3e1e7e9e8e6e525几点说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)2一个连通图G，若存在点割集和边割集，一般并不唯一，且各个点（边）割集中所含的点（边）的个数也不尽相同。我们用含元素个数最少的点割集和边割集来刻画它的连通度26下面从数量观点来描述图的连通性。定义设G=(V,E)是连通图,k(G)=min{|V||V是G的点割集}称为G的点连通度;(G)=min{|E||E是G的边割集}称为G的边连通度。图G的点连通度是为了使G成为一个非连通图,需要删除的点的最少数目。若图G中存在割点,k(G)=1。图G的边连通度是为了使G成为一个非连通图,需要删除的边的最少数目。若图G中存在割边,(G)=1。27G1G2【例】下图中的两个连通图都是n=8，e=16，其中,κ（G1）=4,λ(G1）=4,κ（G2）=1，λ（G2）=3。28假设n个顶点代表n个站，e条边表示铁路或者桥梁或者电话线，e≥n-1。为了使n个站之间的连接不容易被破坏，必须构造一个具有n个顶点e条边的连通图，并使其具有最大的点连通度和边连通度。按图中G1的连接法，如果3个站被破坏，或者3条铁路被破坏，余下的站仍能继续相互联系，也就是仍具有连通性。但按图中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边。若剩下的图是不连通的,则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阶完全图是(n–1)-连通的和(n–1)-边连通的。对于任何n阶连通图,当且仅当没有割点时,它是2-连通的;当且仅当没有割边时,它是2-边连通的。若图G是h-连通的,则G也是h-边连通的。(k(G)≤(G))由定义可知,若h1h2,图G是h1-连通的,则G也是h2-连通的。若h1h2,图G是h1-边连通的,则G也是h2-边连通。一个图的连通度越大,它的连通性能就越好。33例如:下图的边连通度是3，所以它是3―边连通的，也是2―边连通的和1-边连通的，但不是4―边连通的。342、有向图的连通性对于有向图，“图中任意两点都有通路相连”，这个要求很高，因为有向图虽然是连在一起的，但受到边的方向的限制，任意两点不一定有通路。以下分三种情况讨论：351）强连通图：有向图中，任意A、B是互为可达的。如图(a)2）单向连通图：在有向图中，任意两点A、B存在着A到B的通路或存在着B到A的通路。如图(b)3）弱连通图：在有向图中，如果其底图是无向连通图。如图(c)显然：在有向图中，如果有一条通过图中所有点的回路，则此图是强连通的。如果有一条通过图中所有点的通路，则此图是单向连通图。(a)(b)(c)36单向连通图都是弱连通图，但弱连通图却不一定是单向连通图。在弱连通图中，存在这样的顶点A、B，从A到B不可达，且从B到A也不可达。强连通图既是单向连通图，又是弱连通图。即强连通单向连通弱连通37有向图的连通性(续)定理(强连通判别法)D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)D单向连通当且仅当D中存在经过每个顶点至少一次的通路(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通38思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪些是弱连通图。(a)(b)(d)(c)答案:(a),(d)是强连通图,(b)是单向连通图,(c)是弱连通图.39有向图的短程线与距离u到v的短程线:u到v长度最短的通路(u可达v)u与v之间的距离du,v:u到v的短程线的长度若u不可达v,规定du,v=∞.性质：du,v0,且du,v=0u=vdu,v+dv,wdu,w注意:没有对称性40定义：设G是有向图，G′是其子图，若G′是强连