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

第六章图第2讲图连通性第1页

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

第六章第2讲图连通性1.通路，回路2.连通性，点(边)割集,点连通度?,边连通度?3.Whitney定理,简单连通图?,?,?之间关系4.2-连通,2-边连通充要条件5.割点,桥,块充要条件2024/10/3应用离散数学第六章第2讲3第3页

通路与回路通路，回路简单通路，简单回路初级通路，初级回路初级通路判定定理2024/10/3应用离散数学第六章第2讲4第4页

通路和回路通路，回路：给定图G=V,E.设G中顶点和边交替序列为Γ=v0e1v1e2…elvl.若Γ满足以下条件：vi-1是ei端点（G为有向图时，要求vi-1是ei起始点，vi是ei终点），则称Γ为v0到vl通路。v0和vl分别称为此通路起点和终点。Γ中所含边数目称为Γ长度。当v0=vl时，称通路为回路。2024/10/3应用离散数学第六章第2讲5afbcghied第5页

通路和回路简单通路：若Γ中全部边各异；简单回路：类似；初级通路（路径）：若Γ中全部顶点各异，全部边也各异；初级回路（圈）：类似；奇圈，偶圈：圈长度为奇数或偶数。复杂通路：Γ中有边重复出现；复杂回路：类似2024/10/3应用离散数学第六章第2讲6第6页

通路和回路回路是通路特殊情况；初级通路（回路）是简单通路（回路），但反之不真；(顶点各异且边各异则边各异；反之不然)通路表示法：顶点和边交替序列表示法；边序列；在简单图中，能够用顶点序列2024/10/3应用离散数学第六章第2讲7第7页

通路和回路定理3：在一个n阶图中，若从顶点u到v（u和v不等）存在通路，则从u到v存在长度小于等于n-1初级通路。证实：最多该通路中有n个顶点，假如n个顶点互不相同（初级通路），则最多为n-1条边。2024/10/3应用离散数学第六章第2讲8第8页

通路和回路定理4：在一个n阶图中，假如存在v到本身简单回路，则从v到本身存在长度不超出n初级回路。证实：类似。2024/10/3应用离散数学第六章第2讲9第9页

连通性无向图连通性：在无向图G中，若顶点v1和v2之间存在通路，则称v1与v2是连通。要求v1与本身是连通。连通图：若无向图G是平凡图，或G中任意两顶点都是连通，则称G是连通图。不然称G为非连通图。2024/10/3应用离散数学第六章第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是连通图。2024/10/3应用离散数学第六章第2讲11第11页

图中点之间距离短程线：若两点是连通，则称两点之间长度最短通路为两点之间短程线。距离：短程线长度称为两点之间距离，记为d(v1,v2)。2024/10/3应用离散数学第六章第2讲12两个连通分支第12页

怎样定义连通度问题:怎样定量比较无向图连通性强与弱?2024/10/3应用离散数学第六章第2讲13试想？？第13页

怎样定义连通度点连通度:为了破坏连通性,最少需要删除多少个顶点?边连通度:为了破坏连通性,最少需要删除多少条边?说明:“破坏连通性”指p(G-V’)p(G),或p(G-E’)p(G),即“变得愈加不连通”2024/10/3应用离散数学第六章第2讲14连通分支个数第14页

割集(cutset)点割集(vertexcut)边割集(edgecut)割点(cutvertex)割边(cutedge)(桥)(bridge)2024/10/3应用离散数学第六章第2讲15第15页

点割集(vertexcutset)点割集:无向图G=V,E,??V’?V,满足(1)p(G-V’)p(G);(2)极小性:?V’’?V’,p(G-V’’)=p(G),则称V’为点割集.说明:“极小性”是为了确保点割集概念非平凡性2024/10/3应用离散数学第六章第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}2024/10