应用离散数学第六章第2讲.ppt
《应用离散数学第六章第2讲.ppt》由会员分享,可在线阅读,更多相关《应用离散数学第六章第2讲.ppt(36页珍藏版)》请在三一办公上搜索。
1、第六章 图,第2讲 图的连通性,通信网络,图论应用的一个重要方面就是通信网络。如电话网络、计算机网络、管理信息系统、医疗数据网络、银行数据网络、开关网络等。这些网络的基本要求是网络中的各个用户能够快速安全地传递信息,不产生差错和故障,同时使建造和维护网络所需费用低。,2023/10/7,应用离散数学 第六章 第2讲,2,第六章 第2讲 图的连通性,1.通路,回路2.连通性,点(边)割集,点连通度,边连通度3.Whitney定理,简单连通图,之间的关系4.2-连通,2-边连通的充要条件5.割点,桥,块的充要条件,2023/10/7,应用离散数学 第六章 第2讲,3,通路与回路,通路,回路简单通路
2、,简单回路初级通路,初级回路初级通路判定定理,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,通路和回路,简单通路:若中所有边各异;简单回路:类似;初级通路(路径):若中所有顶点各异,所有边也各异;
3、初级回路(圈):类似;奇圈,偶圈:圈的长度为奇数或偶数。复杂通路:中有边重复出现;复杂回路:类似,2023/10/7,应用离散数学 第六章 第2讲,6,通路和回路,回路是通路的特殊情况;初级通路(回路)是简单通路(回路),但反之不真;(顶点各异且边各异则边各异;反之不然)通路的表示法:顶点和边的交替序列表示法;边序列;在简单图中,可以用顶点序列,2023/10/7,应用离散数学 第六章 第2讲,7,通路和回路,定理3:在一个n阶图中,若从顶点u到v(u和v不等)存在通路,则从u到v存在长度小于等于n-1的初级通路。证明:最多该通路中有n个顶点,如果n个顶点互不相同(初级通路),则最多为n-1条
4、边。,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连通 则
5、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讲,1
6、3,试想?,如何定义连通度,点连通度:为了破坏连通性,至少需要删除多少个顶点?边连通度:为了破坏连通性,至少需要删除多少条边?说明:“破坏连通性”指 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
7、)极小性: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,应用离散数学
8、第六章 第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,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用 离散数学 第六
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6225563.html