离散数学通路、回路与图的连通性.ppt

《离散数学通路、回路与图的连通性.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.2通路、回路与图的连通性简单通(回)路,初级通(回)路,复杂通(回)路连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)1在图中，一条通路是顶点和边的交替序列，以顶点开始，以顶点结束。其中，第一条边的终点与第二条边的始点重合…...。第一条边的始点称为通路的始点，最后一条边的终点称为通路的终点。当通路的终点和始点重合时，称为回路。通路或回路中所含边数称为该通路或回路的长度。一、通路和回路21、简单通路：如果通路中各边都不相同。如简单通路：v1→v2→v5→v6→v2→v3→v4长度为6如简单回路

2、：v1→v2→v3→v5→v2→v6→v1长度为62、简单回路：如果回路中各边都不相同。33、基本通路：如果通路中各个顶点都不相同。4、基本回路：如果回路中各个顶点都不相同。如基本通路：v1→v6→v3→v4长度为3如基本回路：v1→v6→v3→v2→v1显然，基本通路（回路）一定是简单通路（回路）。反之不然。4若通路(回路)中有边重复出现,则称为复杂通路(回路).5关于通路与回路的几点说明表示方法①用顶点和边的交替序列(定义),如=v0e1v1e2…elvl②用边的序列,如=e1e2…el③简单图中,用顶点的序列,如

3、=v0v1…vl④非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.在无向简单图中,所有圈的长度3;在有向简单图中,所有圈的长度2.6在两种意义下计算的圈个数①定义意义下在无向图中,一个长度为l(l3)的圈看作2l个不同的圈.如v0v1v2v0,v1v2v0v1,v2v0v1v2看作3个不同的圈.在有向图中,一个长度为l(l3)的圈看作l个不同的圈.②同构意义下所有长度相同的圈都是同构的,因而是1个圈.7定理在n阶图G中，若从顶点vi到vj（vivj）存

4、在通路，则从vi到vj存在长度小于等于n1的通路.推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n1的初级通路.定理在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.8在图G中，如果A到B存在一条通路，则称A到B是可达的。1、无向图的连通性如果无向图中，任意两点是可达的，图为连通图。否则为不连通图。当图是不连通时，定是由几个连通子图构成。称这样的连通图是连通分

5、支。二、图的连通性：9无向图的连通性设无向图G=,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={

6、u,vV且uv}是V上的等价关系连通图:平凡图,任意两点都连通的图连通分支:V关于R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,其个数记作p(G)=k.G是连通图p(G)=110设A={1,2,…,8},R={

7、x,y∈A∧x≡y(mod3)}即:A上模3等价关系的关系图为:11【例】求证：若图中只有两个奇度数

8、顶点，则二顶点必连通。证明用反证法来证明。设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。12【例】在一次国际会议中，由七人组成的小组{a,b,c,d,e,f,g}中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？13解用顶点代表人，如果二人

9、会同一种语言，则在代表二人的顶点间连边，于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。14定理在n阶简单图G,如果对G的每对顶点u和v,deg(u)+deg(v)≥n–1,则G是连通图。证明假设G不连通,则G至少有两个分图。设其中一个分图含有q个顶点,而其余各分图共含有n–q个顶点。在这两部分中各取一个顶点u和v,则0≤deg(u)≤q–1,0≤deg(v)≤n–q–1,因此deg(u)+deg(v)≤n–2,这与题设deg(u

10、)+deg(v)≥n–1矛盾。15短程线与距离u与v之间的短程线:u与v之间长度最短的通路(u与v连通)u与v之间的距离d(u,v):u与v之间短程线的长度若u与v不连通,规定d(u,v)=∞.性质：d(u,v)0,且d(u,v)=0u=vd(u,v)=d(v,u)d(u,v)+d(v