应用离散数学第六章第讲精.ppt

《应用离散数学第六章第讲精.ppt》由会员分享，可在线阅读，更多相关《应用离散数学第六章第讲精.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、应用离散数学第六章第讲第1页，本讲稿共36页通信网络图论应用的一个重要方面就是通信网络。如电话网络、计算机网络、管理信息系统、医疗数据网络、银行数据网络、开关网络等。这些网络的基本要求是网络中的各个用户能够快速快速安全地传递信息安全地传递信息，不产生差错和故障，同时使建造和维护网络所需费用低。2022/11/30应用离散数学 第六章 第2讲2第2页，本讲稿共36页第六章 第2讲 图的连通性1.通路，回路2.连通性，点(边)割集,点连通度,边连通度3.Whitney定理,简单连通图,之间的关系4.2-连通,2-边连通的充要条件5.割点,桥,块的充要条件2022/11/30应用离散数学 第六章 第

2、2讲3第3页，本讲稿共36页通路与回路通路，回路简单通路，简单回路初级通路，初级回路初级通路判定定理2022/11/30应用离散数学 第六章 第2讲4第4页，本讲稿共36页通路和回路通路，回路：给定图G=.设G中顶点和边的交替序列为=v0e1v1e2elvl.若满足如下条件：vi-1是ei端点（G为有向图时，要求vi-1是ei起始点，vi是ei的终点），则称为v0到vl的通路。v0和vl分别称为此通路的起点和终点。中所含边的数目称为的长度。当v0=vl时，称通路为回路。2022/11/30应用离散数学 第六章 第2讲5afbcghied第5页，本讲稿共36页通路和回路简单简单通路：若中所有边边

3、各异；简单回路简单回路：类似；初级初级通路（路径路径）：若中所有顶点顶点各异，所有边也各异；初级回路（圈）：类似；奇圈，偶圈：圈的长度为奇数或偶数。复杂复杂通路：中有边重复边重复出现；复杂回路：类似2022/11/30应用离散数学 第六章 第2讲6第6页，本讲稿共36页通路和回路回路是通路的特殊情况；初级通路（回路）是简单通路（回路），但反之不真；(顶点各异且边各异则边各异；反之不然)通路的表示法：顶点和边的交替序列表示法；边序列；在简单图中，可以用顶点序列2022/11/30应用离散数学 第六章 第2讲7第7页，本讲稿共36页通路和回路定理3：在一个n阶图中，若从顶点u到v（u和v不等）存在

4、通路，则从u到v存在长度小于等于n-1的初级通路。证明：最多该通路中有n个顶点，如果n个顶点互不相同（初级通路），则最多为n-1条边。2022/11/30应用离散数学 第六章 第2讲8第8页，本讲稿共36页通路和回路定理4：在一个n阶图中，如果存在v到自身的简单回路，则从v到自身存在长度不超过n的初级回路。证明：类似。2022/11/30应用离散数学 第六章 第2讲9第9页，本讲稿共36页连通性无向图的连通性：在无向图G中，若顶点v1和v2之间存在通路，则称v1与v2是连通的。规定v1与自身是连通的。连通图：若无向图G是平凡图，或G中任意两顶点都是连通的，则称G是连通图。否则称G为非连通图。2

5、022/11/30应用离散数学 第六章 第2讲10平凡图任意两顶点都是连通的第10页，本讲稿共36页连通分支连通关系：设G=为一无向图，设 R=|x,yV且x与y连通 则R是自反的，对称的，并且是传递的，因而R是V上的等价关系。连通分支：设R的不同等价类分别为V1，Vk,称它们的导出子图GV1，GVk 为G的连通分支，其连通分支的个数记为p(G)。若p(G)=1，则G是连通图。2022/11/30应用离散数学 第六章 第2讲11第11页，本讲稿共36页图中点之间的距离短程线：若两点是连通的，则称两点之间的长度最短的通路为两点之间的短程线。距离：短程线的长度称为两点之间的距离，记为d(v1,v2

6、)。2022/11/30应用离散数学 第六章 第2讲12两个连通分支第12页，本讲稿共36页如何定义连通度问题:如何定量比较无向图连通性的强与弱?2022/11/30应用离散数学 第六章 第2讲13试想？第13页，本讲稿共36页如何定义连通度点连通度:为了破坏连通性,至少需要删除多少个顶点?边连通度:为了破坏连通性,至少需要删除多少条边?说明:“破坏连通性”指 p(G-V)p(G),或p(G-E)p(G),即“变得更加不连通”2022/11/30应用离散数学 第六章 第2讲14连通分支的个数第14页，本讲稿共36页割集(cutset)点割集(vertex cut)边割集(edge cut)割点

7、(cut vertex)割边(cut edge)(桥)(bridge)2022/11/30应用离散数学 第六章 第2讲15第15页，本讲稿共36页点割集(vertex cutset)点割集:无向图G=,VV,满足 (1)p(G-V)p(G);(2)极小性:VV,p(G-V)=p(G),则称V为点割集.说明:“极小性”是为了保证点割集概念的非平凡性2022/11/30应用离散数学 第六章 第2讲16第16页，本讲稿共36页点割集(举例)G1:f,a,e,c,g,k,j,b,e,f,k,hG2:f,a,e,c,g,k,j,b,e,f,k,h2022/11/30应用离散数学 第六章 第2讲17abc

8、dfeghkjiabcefdjighkG1G2Question?第17页，本讲稿共36页割点(cut-point/cut-vertex)割点:v是割点 v是割集例:G1中f是割点,G2中无割点 2022/11/30应用离散数学 第六章 第2讲18abcdfeghkjiabcefdjighkG1G2第18页，本讲稿共36页边割集(edge cutset)边割集:无向图G=,EE,满足 (1)p(G-E)p(G);(2)极小性:EE,p(G-E)=p(G),则称E为边割集.说明:“极小性”是为了保证边割集概念的非平凡性2022/11/30应用离散数学 第六章 第2讲19第19页，本讲稿共36页边割

9、集(举例)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)2022/11/30应用离散数学 第六章 第2讲20abcdfeghkjiabcefdjighkG1G2注意：极小性第20页，本讲稿共36页割边(cut-edge)(桥)割边:(u,v)是割边(桥)(u,v)是边割集例:G1中(f,g)是桥,G2中无桥 2022/11/30应用离散数学 第六章 第2讲21abcdfelhkjiabcefdjighkG1G2g第21页，本讲稿共3

10、6页扇形割集(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)2022/11/30应用离散数学 第六章 第2讲22abcgdfe?关联集:IG(v)=e|e与v关联 割点割点第22页，本讲稿共36页点连通度(vertex-connectivity)点连通度:G是无向连通非完全图,(G)=min|V|V是G的点割集 规定:(Kn)=n-1,G非连通:(G)=0例:(G)=1,(H)=2,(F

11、)=3,(K5)=4 2022/11/30应用离散数学 第六章 第2讲23GHF第23页，本讲稿共36页边连通度(edge-connectivity)边连通度:G是无向连通图,(G)=min|E|E是G的边割集 规定:G非连通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=42022/11/30应用离散数学 第六章 第2讲24GHF第24页，本讲稿共36页k-连通图,k-边连通图k-连通图(k-connected):(G)kk-边连通图(k-edge-connected):(G)k 例:彼得森图=3,=3;它是1-连通图,2-连通图,3-连通图,但不是4-连通图;它是1-边连通图

12、,2-边连通图,3-边连通图,但不是4-边连通图2022/11/30应用离散数学 第六章 第2讲25点连通度边连通度第25页，本讲稿共36页Whitney定理定理10:.证明:不妨设G是3阶以上连通简单非完全图.()设d(v)=,则|IG(v)|=,IG(v)中一定有边割集E,所以|E|IG(v)|=.()设E是边割集,|E|=,从V(E)中找出点割集V,使得|V|,所以|V|.2022/11/30应用离散数学 第六章 第2讲26为图的最小度。为点连通度为边连通度第26页，本讲稿共36页Whitney定理(续)证明(续):()设G-E的2个连通分支是G1,G2.设uV(G1),vV(G2),使

13、得(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|=.#2022/11/30应用离散数学 第六章 第2讲27uv具体的构造策略第27页，本讲稿共36页引理1引理1:设E是边割集,则p(G-E)=p(G)+1.证明:如果p(G-E)p(G)+1,则E不是边割集,因为不满足定义中的极小性.#说明:点割集无此性质2022/11/30应用离散数学 第六章 第2讲28第28页，本讲稿共36页引理2引理2:设E是非完全图G的边割集,(G)=|E|,G-E的2个连通分支是G1,G2,

14、则存在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.2022/11/30应用离散数学 第六章 第2讲29为边连通度任意两点都连同第29页，本讲稿共36页推论推论:k-连通图一定是k-边连通图.#2022/11/30应用离散数学 第六章 第2讲30根据Whitney定理和k-连通图、k-边连通图的概念，可证第30页，本讲稿共36页自学有向图的连通性及其分类可达；短程线；距离连通图，强连通图，弱连通图

15、，单向连通图连通性判别法2022/11/30应用离散数学 第六章 第2讲31第31页，本讲稿共36页Hassler Whitney(19071989)美国数学家,曾获得Wolf奖 主要研究拓扑学.20世纪30年代发表了十几篇图论论文,定义了“对偶图”概念,推动了四色定理的研究.一生的最后20年致力于数学教育,提倡应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无关的技巧和结果.2022/11/30应用离散数学 第六章 第2讲32第32页，本讲稿共36页Whitney的看法应当让年轻人用自己的直觉(intuition)来解决问题,而不是教一些与他们的经验无关的技

16、巧和结果.什么是直觉?-习惯成自然,熟能生巧骑自行车:“平衡感”游泳:“水感”学外语:“语感”如何取得经验?-自己动手练习!不能只听不做.2022/11/30应用离散数学 第六章 第2讲33积累经验第33页，本讲稿共36页割点的充分必要条件定理11:无向连通图G中顶点v是割点 可以把V(G)-v划分成V1与V2,使得从V1中任意顶点u到V2中任意顶点w的路径都要经过v.#2022/11/30应用离散数学 第六章 第2讲34vuwV1V2第34页，本讲稿共36页桥的充分必要条件定理18:无向连通图G中边e是桥 G的任何圈都不经过e.#定理19:无向连通图G中边e是桥 可以把V(G)划分成V1与V2,使得从V1中任意顶点u到V2中任意顶点v的路径都要经过e.#2022/11/30应用离散数学 第六章 第2讲35euvV1V2第35页，本讲稿共36页第十一周课程总结点割集,边割集,割点,桥,块点连通度,边连通度,Whitney定理割点,桥的充要条件2022/11/30应用离散数学 第六章 第2讲36第36页，本讲稿共36页