应用离散数学第六章第2讲.ppt
第六章 图,第2讲 图的连通性,通信网络,图论应用的一个重要方面就是通信网络。如电话网络、计算机网络、管理信息系统、医疗数据网络、银行数据网络、开关网络等。这些网络的基本要求是网络中的各个用户能够快速安全地传递信息，不产生差错和故障，同时使建造和维护网络所需费用低。,2023/10/7,应用离散数学 第六章 第2讲,2,第六章 第2讲 图的连通性,1.通路，回路2.连通性，点(边)割集,点连通度,边连通度3.Whitney定理,简单连通图,之间的关系4.2-连通,2-边连通的充要条件5.割点,桥,块的充要条件,2023/10/7,应用离散数学 第六章 第2讲,3,通路与回路,通路，回路简单通路，简单回路初级通路，初级回路初级通路判定定理,2023/10/7,应用离散数学 第六章 第2讲,4,通路和回路,通路，回路：给定图G=.设G中顶点和边的交替序列为=v0e1v1e2elvl.若满足如下条件：vi-1是ei端点（G为有向图时，要求vi-1是ei起始点，vi是ei的终点），则称为v0到vl的通路。v0和vl分别称为此通路的起点和终点。中所含边的数目称为的长度。当v0=vl时，称通路为回路。,2023/10/7,应用离散数学 第六章 第2讲,5,a,f,b,c,g,h,i,e,d,通路和回路,简单通路：若中所有边各异；简单回路：类似；初级通路（路径）：若中所有顶点各异，所有边也各异；初级回路（圈）：类似；奇圈，偶圈：圈的长度为奇数或偶数。复杂通路：中有边重复出现；复杂回路：类似,2023/10/7,应用离散数学 第六章 第2讲,6,通路和回路,回路是通路的特殊情况；初级通路（回路）是简单通路（回路），但反之不真；(顶点各异且边各异则边各异；反之不然)通路的表示法：顶点和边的交替序列表示法；边序列；在简单图中，可以用顶点序列,2023/10/7,应用离散数学 第六章 第2讲,7,通路和回路,定理3：在一个n阶图中，若从顶点u到v（u和v不等）存在通路，则从u到v存在长度小于等于n-1的初级通路。证明：最多该通路中有n个顶点，如果n个顶点互不相同（初级通路），则最多为n-1条边。,2023/10/7,应用离散数学 第六章 第2讲,8,通路和回路,定理4：在一个n阶图中，如果存在v到自身的简单回路，则从v到自身存在长度不超过n的初级回路。证明：类似。,2023/10/7,应用离散数学 第六章 第2讲,9,连通性,无向图的连通性：在无向图G中，若顶点v1和v2之间存在通路，则称v1与v2是连通的。规定v1与自身是连通的。连通图：若无向图G是平凡图，或G中任意两顶点都是连通的，则称G是连通图。否则称G为非连通图。,2023/10/7,应用离散数学 第六章 第2讲,10,平凡图,任意两顶点都是连通的,连通分支,连通关系：设G=为一无向图，设 R=|x,yV且x与y连通 则R是自反的，对称的，并且是传递的，因而R是V上的等价关系。连通分支：设R的不同等价类分别为V1，Vk,称它们的导出子图GV1，GVk 为G的连通分支，其连通分支的个数记为p(G)。若p(G)=1，则G是连通图。,2023/10/7,应用离散数学 第六章 第2讲,11,图中点之间的距离,短程线：若两点是连通的，则称两点之间的长度最短的通路为两点之间的短程线。距离：短程线的长度称为两点之间的距离，记为d(v1,v2)。,2023/10/7,应用离散数学 第六章 第2讲,12,两个连通分支,如何定义连通度,问题:如何定量比较无向图连通性的强与弱?,2023/10/7,应用离散数学 第六章 第2讲,13,试想？,如何定义连通度,点连通度:为了破坏连通性,至少需要删除多少个顶点?边连通度:为了破坏连通性,至少需要删除多少条边?说明:“破坏连通性”指 p(G-V)p(G),或p(G-E)p(G),即“变得更加不连通”,2023/10/7,应用离散数学 第六章 第2讲,14,连通分支的个数,割集(cutset),点割集(vertex cut)边割集(edge cut)割点(cut vertex)割边(cut edge)(桥)(bridge),2023/10/7,应用离散数学 第六章 第2讲,15,点割集(vertex cutset),点割集:无向图G=,VV,满足(1)p(G-V)p(G);(2)极小性:VV,p(G-V)=p(G),则称V为点割集.说明:“极小性”是为了保证点割集概念的非平凡性,2023/10/7,应用离散数学 第六章 第2讲,16,点割集(举例),G1:f,a,e,c,g,k,j,b,e,f,k,hG2:f,a,e,c,g,k,j,b,e,f,k,h,2023/10/7,应用离散数学 第六章 第2讲,17,a,b,c,d,f,e,g,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,Question?,割点(cut-point/cut-vertex),割点:v是割点 v是割集例:G1中f是割点,G2中无割点,2023/10/7,应用离散数学 第六章 第2讲,18,a,b,c,d,f,e,g,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,边割集(edge cutset),边割集:无向图G=,EE,满足(1)p(G-E)p(G);(2)极小性:EE,p(G-E)=p(G),则称E为边割集.说明:“极小性”是为了保证边割集概念的非平凡性,2023/10/7,应用离散数学 第六章 第2讲,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/10/7,应用离散数学 第六章 第2讲,20,a,b,c,d,f,e,g,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,注意：极小性,割边(cut-edge)(桥),割边:(u,v)是割边(桥)(u,v)是边割集例:G1中(f,g)是桥,G2中无桥,2023/10/7,应用离散数学 第六章 第2讲,21,a,b,c,d,f,e,l,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,g,扇形割集(fan cutset),IG(v)不一定是边割集(不一定极小)IG(v)不是边割集 v是割点扇形割集:E是边割集EIG(v)例:(a,g),(a,b),(g,a),(g,b),(g,c),(c,d),(d,e),(d,f),(a,b),(g,b),(g,c),2023/10/7,应用离散数学 第六章 第2讲,22,a,b,c,g,d,f,e,?,关联集:IG(v)=e|e与v关联,割点,割点,点连通度(vertex-connectivity),点连通度:G是无向连通非完全图,(G)=min|V|V是G的点割集 规定:(Kn)=n-1,G非连通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=4,2023/10/7,应用离散数学 第六章 第2讲,23,G,H,F,边连通度(edge-connectivity),边连通度:G是无向连通图,(G)=min|E|E是G的边割集 规定:G非连通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=4,2023/10/7,应用离散数学 第六章 第2讲,24,G,H,F,k-连通图,k-边连通图,k-连通图(k-connected):(G)kk-边连通图(k-edge-connected):(G)k 例:彼得森图=3,=3;它是1-连通图,2-连通图,3-连通图,但不是4-连通图;它是1-边连通图,2-边连通图,3-边连通图,但不是4-边连通图,2023/10/7,应用离散数学 第六章 第2讲,25,点连通度,边连通度,Whitney定理,定理10:.证明:不妨设G是3阶以上连通简单非完全图.()设d(v)=,则|IG(v)|=,IG(v)中一定有边割集E,所以|E|IG(v)|=.()设E是边割集,|E|=,从V(E)中找出点割集V,使得|V|,所以|V|.,2023/10/7,应用离散数学 第六章 第2讲,26,为图的最小度。为点连通度为边连通度,Whitney定理(续),证明(续):()设G-E的2个连通分支是G1,G2.设uV(G1),vV(G2),使得(u,v)E(G).如下构造V:eE,选择e的异于u,v的一个端点放入V.|V|E|.G-VG-E=G1G2,u和v在G-V中不连通,所以V中含有点割集V.所以|V|V|E|=.#,2023/10/7,应用离散数学 第六章 第2讲,27,u,v,具体的构造策略,引理1,引理1:设E是边割集,则p(G-E)=p(G)+1.证明:如果p(G-E)p(G)+1,则E不是边割集,因为不满足定义中的极小性.#说明:点割集无此性质,2023/10/7,应用离散数学 第六章 第2讲,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+10 aba+b-1.,2023/10/7,应用离散数学 第六章 第2讲,29,为边连通度,任意两点都连同,推论,推论:k-连通图一定是k-边连通图.#,2023/10/7,应用离散数学 第六章 第2讲,30,根据Whitney定理和k-连通图、k-边连通图的概念，可证,自学,有向图的连通性及其分类可达；短程线；距离连通图，强连通图，弱连通图，单向连通图连通性判别法,2023/10/7,应用离散数学 第六章 第2讲,31,Hassler Whitney(19071989),美国数学家,曾获得Wolf奖 主要研究拓扑学.20世纪30年代发表了十几篇图论论文,定义了“对偶图”概念,推动了四色定理的研究.一生的最后20年致力于数学教育,提倡应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无关的技巧和结果.,2023/10/7,应用离散数学 第六章 第2讲,32,Whitney的看法,应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无关的技巧和结果.什么是直觉?-习惯成自然,熟能生巧骑自行车:“平衡感”游泳:“水感”学外语:“语感”如何取得经验?-自己动手练习!不能只听不做.,2023/10/7,应用离散数学 第六章 第2讲,33,积累经验,割点的充分必要条件,定理11:无向连通图G中顶点v是割点 可以把V(G)-v划分成V1与V2,使得从V1中任意顶点u到V2中任意顶点w的路径都要经过v.#,2023/10/7,应用离散数学 第六章 第2讲,34,v,u,w,V1,V2,桥的充分必要条件,定理18:无向连通图G中边e是桥 G的任何圈都不经过e.#定理19:无向连通图G中边e是桥 可以把V(G)划分成V1与V2,使得从V1中任意顶点u到V2中任意顶点v的路径都要经过e.#,2023/10/7,应用离散数学 第六章 第2讲,35,e,u,v,V1,V2,第十一周课程总结,点割集,边割集,割点,桥,块点连通度,边连通度,Whitney定理割点,桥的充要条件,2023/10/7,应用离散数学 第六章 第2讲,36,
