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

离散数学回路与图的连通性演示文稿第1页，共24页。（优选）离散数学回路与图的连通性第2页，共24页。31、简单通路：如果通路中各边都不相同。如简单通路：v1→v2→v5→v6→v2→v3→v4长度为6如简单回路：v1→v2→v3→v5→v2→v6→v1长度为62、简单回路：如果回路中各边都不相同。第3页，共24页。43、基本通路：如果通路中各个顶点和边都不相同。4、基本回路(圈)：如果回路中各个顶点和边都不相同。如基本通路：v1→v6→v3→v4长度为3如基本回路：v1→v6→v3→v2→v1显然，基本通路（回路）一定是简单通路（回路）。反之不然。第4页，共24页。5若通路(回路)中有边重复出现,则称为复杂通路(回路).第5页，共24页。6关于通路与回路的几点说明表示方法①用顶点和边的交替序列(定义),如

=v0e1v1e2…elvl②用边的序列,如

=e1e2…el③简单图中,用顶点的序列,如

=v0v1…vl④非简单图中,可用混合表示法,如

=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.第6页，共24页。7在图G中，如果A到B存在一条通路，则称A到B是可达的。1、无向图的连通性如果无向图中，任意两点是可达的，图为连通图。否则为不连通图。当图是不连通时，定是由几个连通子图构成。称这样的连通图是连通分支。二、图的连通性：

第7页，共24页。8无向图的连通性设无向图G=<V,E>,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={<u,v>|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)=1若G为非连通图，则P(G)≥2,在所有的n阶无向图中，n阶零图是连通分支最多的其分支数为n.第8页，共24页。9设A={1,2,…,8},

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

上述关系图被分成三个互不连通的部分，每部分中的数两两都有关系，不同部分的图无关系。第9页，共24页。10

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

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

单向连通

弱连通第18页，共24页。19有向图的连通性(续)

定理(强连通判别法)

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

D单向连通当且仅当D中存在经过每个顶点至少一次的通路(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通第19页，共24页。20思考：判断下列图中哪些是强连通图，哪些是单向连通图，哪些是弱连通图。(a)(b)(d)(c)答案:(a),(d)是强连通图,(b)是单向连通图,(c)是弱连通图.第20页，共24页。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>

注意:没有对称性第21页，共24页。227.7设n阶无向简单图G中，问应为多少？解：由于，说明G中任何顶点v的度数而由于G为简单图，于是则有，因此说明G中每个顶点的度数都为n-1,于是有说明G为n-1阶正则图，即G为n阶完全图。第22页，共24页。237.8一个n(n≥2)阶无向简单图G中，n为奇数，已知G中的r个奇数度顶