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

离散数学回路与图的连通性21、简单通路:如果通路中各边都不相同。如简单通路:v1→v2→v5→v6→v2→v3→v4长度为6如简单回路: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③简单图中,用顶点得序列,如

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

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

7无向图得连通性设无向图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设A={1,2,…,8},

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

上述关系图被分成三个互不连通得部分,每部分中得数两两都有关系,不同部分得图无关系。9

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

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

单向连通

弱连通19有向图得连通性(续)

定理(强连通判别法)D强连通当且仅当D中存在经过每个顶点至少一次得回路定理(单向连通判别法)D单向连通当且仅当D中存在经过每个顶点至少一次得通路(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通20思考:判断下列图中哪些就是强连通图,哪些就是单向连通图,哪些就是弱连通图。(a)(b)(d)(c)答案:(a),(d)就是强连通图,(b)就是单向连通图,(c)就是弱连通图、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>

注意:没有对称性227、7设n阶无向简单图G中,问应为多少？解：由于，说明G中任何顶点v的度数而由于G为简单图，于是则有，因此说明G中每个顶点得度数都为n-1,于就是有说明G为n-1阶正则图,即G为n阶完全图。237、8一个n(n≥2)阶无向简单图G中,n为奇数,已知G中得r个奇数度顶点,问G得补图有几个奇数度顶点？解:由于而n为奇数,于就是Kn中各顶点得度数n-1为偶数,对于，应有，且由于n-1为偶数，所以