应用离散数学第六章第2讲省名师优质课赛课获奖课件市赛课一等奖课件

第六章图第2讲图连通性第1页通信网络图论应用一个主要方面就是通信网络。如电话网络、计算机网络、管理信息系统、医疗数据网络、银行数据网络、开关网络等。这些网络基本要求是网络中各个用户能够快速安全地传递信息，不产生差错和故障，同时使建造和维护网络所需费用低。2023/9/13应用离散数学第六章第2讲2第2页第六章第2讲图连通性1.通路，回路2.连通性，点(边)割集,点连通度

,边连通度

3.Whitney定理,简单连通图,,之间关系4.2-连通,2-边连通充要条件5.割点,桥,块充要条件2023/9/13应用离散数学第六章第2讲3第3页通路与回路通路，回路简单通路，简单回路初级通路，初级回路初级通路判定定理2023/9/13应用离散数学第六章第2讲4第4页通路和回路通路，回路：给定图G=<V,E>.设G中顶点和边交替序列为Γ=v0e1v1e2…elvl.若Γ满足以下条件：vi-1是ei端点（G为有向图时，要求vi-1是ei起始点，vi是ei终点），则称Γ为v0到vl通路。v0和vl分别称为此通路起点和终点。Γ中所含边数目称为Γ长度。当v0=vl时，称通路为回路。2023/9/13应用离散数学第六章第2讲5afbcghied第5页通路和回路简单通路：若Γ中全部边各异；简单回路：类似；初级通路（路径）：若Γ中全部顶点各异，全部边也各异；初级回路（圈）：类似；奇圈，偶圈：圈长度为奇数或偶数。复杂通路：Γ中有边重复出现；复杂回路：类似2023/9/13应用离散数学第六章第2讲6第6页通路和回路回路是通路特殊情况；初级通路（回路）是简单通路（回路），但反之不真；(顶点各异且边各异则边各异；反之不然)通路表示法：顶点和边交替序列表示法；边序列；在简单图中，能够用顶点序列2023/9/13应用离散数学第六章第2讲7第7页通路和回路定理3：在一个n阶图中，若从顶点u到v（u和v不等）存在通路，则从u到v存在长度小于等于n-1初级通路。证实：最多该通路中有n个顶点，假如n个顶点互不相同（初级通路），则最多为n-1条边。2023/9/13应用离散数学第六章第2讲8第8页通路和回路定理4：在一个n阶图中，假如存在v到本身简单回路，则从v到本身存在长度不超出n初级回路。证实：类似。2023/9/13应用离散数学第六章第2讲9第9页连通性无向图连通性：在无向图G中，若顶点v1和v2之间存在通路，则称v1与v2是连通。要求v1与本身是连通。连通图：若无向图G是平凡图，或G中任意两顶点都是连通，则称G是连通图。不然称G为非连通图。2023/9/13应用离散数学第六章第2讲10平凡图任意两顶点都是连通第10页连通分支连通关系：设G=<V,E>为一无向图，设R={<x,y>|x,y∈V且x与y连通}则R是自反，对称，而且是传递，因而R是V上等价关系。连通分支：设R不一样等价类分别为V1，…，Vk,称它们导出子图G[V1]，…，G[Vk]为G连通分支，其连通分支个数记为p(G)。若p(G)=1，则G是连通图。2023/9/13应用离散数学第六章第2讲11第11页图中点之间距离短程线：若两点是连通，则称两点之间长度最短通路为两点之间短程线。距离：短程线长度称为两点之间距离，记为d(v1,v2)。2023/9/13应用离散数学第六章第2讲12两个连通分支第12页怎样定义连通度问题:怎样定量比较无向图连通性强与弱?2023/9/13应用离散数学第六章第2讲13试想？？第13页怎样定义连通度点连通度:为了破坏连通性,最少需要删除多少个顶点?边连通度:为了破坏连通性,最少需要删除多少条边?说明:“破坏连通性”指p(G-V’)>p(G),或p(G-E’)>p(G),即“变得愈加不连通”2023/9/13应用离散数学第六章第2讲14连通分支个数第14页割集(cutset)点割集(vertexcut)边割集(edgecut)割点(cutvertex)割边(cutedge)(桥)(bridge)2023/9/13应用离散数学第六章第2讲15第15页点割集(vertexcutset)点割集:无向图G=<V,E>,

V’V,满足(1)p(G-V’)>p(G);(2)极小性:

V’’V’,p(G-V’’)=p(G),则称V’为点割集.说明:“极小性”是为了确保点割集概念非平凡性2023/9/13应用离散数学第六章第2讲16第16页点割集(举例)G1:{f},{a,e,c},{g,k,j},{b,e,f,k,h}G2:{f},{a,e,c},{g,k,j},{b,e,f,k,h}2023/9/13应用离散数学第六章第2讲17abcdfeghkjiabcefdjighkG1G2Question?第17页割点(cut-point/cut-vertex)割点:v是割点

{v}是割集例:G1中f是割点,G2中无割点2023/9/13应用离散数学第六章第2讲18abcdfeghkjiabcefdjighkG1G2第18页边割集(edgecutset)边割集:无向图G=<V,E>,E’E,满足(1)p(G-E’)>p(G);(2)极小性:

E’’E’,p(G-E’’)=p(G),则称E’为边割集.说明:“极小性”是为了确保边割集概念非平凡性2023/9/13应用离散数学第六章第2讲19第19页边割集(举例)G1:{(a,f),(e,f),(d,f)},{(f,g),(f,k),(j,k),(j,i)}{(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)},{(c,d)}G2:{(b,a),(b,e),(b,c)}2023/9/13应用离散数学第六章第2讲20abcdfeghkjiabcefdjighkG1G2注意：极小性第20页割边(cut-edge)(桥)割边:(u,v)是割边(桥)

{(u,v)}是边割集例:G1中(f,g)是桥,G2中无桥2023/9/13应用离散数学第六章第2讲21abcdfelhkjiabcefdjighkG1G2g第21页扇形割集(fancutset)IG(v)不一定是边割集(不一定极小)IG(v)不是边割集

v是割点扇形割集:E’是边割集

E’

IG(v)例:{(a,g),(a,b)},{(g,a),(g,b),(g,c)},{(c,d)},{(d,e),(d,f)},{(a,b),(g,b),(g,c)}2023/9/13应用离散数学第六章第2讲22abcgdfe???关联集:IG(v)={e|e与v关联

}割点割点第22页点连通度(vertex-connectivity)点连通度:G是无向连通非完全图,(G)=min{|V’||V’是G点割集}要求:(Kn)=n-1,G非连通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=42023/9/13应用离散数学第六章第2讲23GHF第23页边连通度(edge-connectivity)边连通度:G是无向连通图,(G)=min{|E’||E’是G边割集}要求:G非连通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=42023/9/13应用离散数学第六章第2讲24GHF第24页k-连通图,k-边连通图k-连通图(k-connected):(G)kk-边连通图(k-edge-connected):(G)k例:彼得森图=3,=3;它是1-连通图,2-连通图,3-连通图,但不是4-连通图;它是1-边连通图,2-边连通图,3-边连通图,但不是4-边连通图2023/9/13应用离散数学第六章第2讲25点连通度边连通度第25页Whitney定理定理10:

.证实:不妨设G是3阶以上连通简单非完全图.()设d(v)=,则|IG(v)|=,IG(v)中一定有边割集E’,所以|E’||IG(v)|=.(

)设E’是边割集,|E’|=,从V(E’)中找出点割集V’,使得|V’|,所以|V’|.2023/9/13应用离散数学第六章第2讲26为图最小度。为点连通度为边连通度第26页Whitney定理(续)证实(续):()设G-E’2个连通分支是G1,G2.设uV(G1),vV(G2),使得(u,v)E(G).以下结构V’’:eE’,选择e异于u,v一个端点放入V’’.|V’’||E’|.G-V’’G-E’=G1G2,u和v在G-V’’中不连通,所以V’’中含有点割集V’.所以|V’||V’’||E’|=.#2023/9/13应用离散数学第六章第2讲27uv详细结构策略第27页引理1引理1:设E’是边割集,则p(G-E’)=p(G)+1.证实:假如p(G-E’)>p(G)+1,则E’不是边割集,因为不满足定义中极小性.#说明:点割集无此性质2023/9/13应用离散数学第六章第2讲28第28页引理2引理2:设E’是非完全图G边割集,(G)=|E’|,G-E’2个连通分支是G1,G2,则存在uV(G1),vV(G2),使得(u,v)E(G)证实:(反证)不然(G)=|E’|=|V(G1)||V(G2)|

|V(G1)|+|V(G2)|-1=n-1,与G非完全图相矛盾!#说明:a1b1(a-1)(b-1)=ab-a-b+10aba+b-1.2023/9/13应用离散数学第六章第2讲29为边连通度任意两点都连同第29页推论推论:k-连通图一定是k-边连通图.#2023/9/13应用离散数学第六章第2讲30依据Whitney定理和k-连通图、k-边连通图概念，可证第30页自学有向图连通性及其分类可达；短程线；距离连通图，强连通图，弱连通图，单向连通图连通性判别法2023/9/13应用离散数学第六章第2讲31第31页HasslerWhitney(1907~1989)美国数学家,曾取得Wolf奖主要研究拓扑学.20世纪30年代发表了十几篇图论论文,定义了“对偶图”概念,推进了四色定理研究.一生最终致力于数学教育,提倡应该让年轻人用自己直觉(intuition)来处理问题,而不是教一些与他们经验无关技巧和结果.2023/9/13应用离散数学第六章第2讲32第32页Whitney看法应该让年轻人用