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

离散数学回路与图的连通性第一页，共二十六页，2022年，8月28日2

在图中，一条通路是顶点和边的交替序列，以顶点

开始，以顶点结束。其中，第一条边的终点与第二条边的始点重合…...。第一条边的始点称为通路的始点，最后一条边的终点称为通路的终点。当通路的终点和始点重合时，称为回路。通路或回路中所含边数称为该通路或回路的长度。一、通路和回路

第二页，共二十六页，2022年，8月28日31、简单通路：如果通路中各边都不相同。如简单通路：v1→v2→v5→v6→v2→v3→v4长度为6如简单回路：v1→v2→v3→v5→v2→v6→v1长度为62、简单回路：如果回路中各边都不相同。第三页，共二十六页，2022年，8月28日43、基本通路：如果通路中各个顶点和边都不相同。4、基本回路(圈)：如果回路中各个顶点和边都不相同。如基本通路：v1→v6→v3→v4长度为3如基本回路：v1→v6→v3→v2→v1显然，基本通路（回路）一定是简单通路（回路）。反之不然。第四页，共二十六页，2022年，8月28日5若通路(回路)中有边重复出现,则称为复杂通路(回路).第五页，共二十六页，2022年，8月28日6关于通路与回路的几点说明表示方法①用顶点和边的交替序列(定义),如=v0e1v1e2…elvl②用边的序列,如=e1e2…el③简单图中,用顶点的序列,如=v0v1…vl④非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.第六页，共二十六页，2022年，8月28日7在图G中，如果A到B存在一条通路，则称A到B是可达的。1、无向图的连通性如果无向图中，任意两点是可达的，图为连通图。否则为不连通图。当图是不连通时，定是由几个连通子图构成。称这样的连通图是连通分支。二、图的连通性：

第七页，共二十六页，2022年，8月28日8无向图的连通性设无向图G=<V,E>,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={<u,v>|u,v

V且uv}是V上的等价关系连通图:平凡图,任意两点都连通的图连通分支:V关于R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,其个数记作p(G)=k.G是连通图

p(G)=1若G为非连通图，则P(G)≥2,在所有的n阶无向图中，n阶零图是连通分支最多的其分支数为n.第八页，共二十六页，2022年，8月28日9设A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}即:A上模3等价关系的关系图为:

上述关系图被分成三个互不连通的部分，每部分中的数两两都有关系，不同部分的图无关系。第九页，共二十六页，2022年，8月28日10

【例】求证：若图中只有两个奇度数顶点，则二顶点必连通。证明用反证法来证明。设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通。第十页，共二十六页，2022年，8月28日11

【例】在一次国际会议中，由七人组成的小组{a,b,c,d,e,f,g}中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语。问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？第十一页，共二十六页，2022年，8月28日12解用顶点代表人，如果二人会同一种语言，则在代表二人的顶点间连边，于是得到下图。问题归结为：在这个图中，任何两个顶点间是否都存在着通路？由于下图是一个连通图，因此，必要时通过别人翻译，他们中间任何二人均可对话。第十二页，共二十六页，2022年，8月28日13定理在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)+deg(v)≥n–1矛盾。第十三页，共二十六页，2022年，8月28日14无向图的短程线与距离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,w)d(u,w)第十四页，共二十六页，2022年，8月28日15在实际问题中,除了考察一个图是否连通外,往往还要研究一个图连通的程度,作为某些系统的可靠性度量。图的连通性在计算机网、通信网和电力网等方面有着重要的应用。图的连通性的应用第十五页，共二十六页，2022年，8月28日162、有向图的连通性对于有向图，“图中任意两点都有通路相连”，这个要求很高，因为有向图虽然是连在一起的，但受到边的方向的限制，任意两点不一定有通路。以下分三种情况讨论：第十六页，共二十六页，2022年，8月28日171）强连通图：有向图中，任意A、B是互为可达的。如图(a)2）单向连通图：在有向图中，任意两点A、B存在着A到B的通路或存在着B到A的通路。如图(b)3）弱连通图：在有向图中，如果其底图是无向连通图。如图(c)显然：在有向图中，如果有一条通过图中所有点的回路，则此图是强连通的。如果有一条通过图中所有点的通路，则此图是单向连通图。(a)(b)(c)第十七页，共二十六页，2022年，8月28日18单向连通图都是弱连通图，但弱连通图却不一定是单向连通图。在弱连通图中，存在这样的顶点A、B，从A到B不可达，且从B到A也不可达。强连通图既是单向连通图，又是弱连通图。即强连通单向连通弱连通第十八页，共二十六页，2022年，8月28日19有向图的连通性(续)

定理(强连通判别法)

D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)

D单向连通当且仅当D中存在经过每个顶点至少一次的通路(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通第十九页，共二十六页，2022年，8月28日20思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪些是弱连通图。(a)(b)(d)(c)答案:(a),(d)是强连通图,(b)是单向连通图,(c)是弱连通图.第二十页，共二十六页，2022年，8月28日21有向图的短程线与距离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,w>d<u,w>

注意:没有对称性第二十一页，共二十六页，2022年，8月28日227.7设n阶无向简单图G中，问应为多少？解：由于，说明G中任何顶点v的度数而由于G为简单图，于是则有，因此说明G中每个顶点的度数都为n-1,于是有说明G为n-1阶正则图，即G为n阶完全图。第二十二页，共二十六页，2022年，8月28日237.8一个n(n≥2)阶无向简单图G中，n为奇数，已知G中的r个奇数度顶点，问G的补图有几个奇数度顶点？解：由于而n为奇数，于是Kn中各顶点的度数n-1为偶数，对于，应有，且由于n-1为偶数，所以同为奇数或同为偶数。因此G中的r个奇数度顶点，则也有r个奇数度顶点