離散數(shù)學(xué)回路與圖的連通性

離散數(shù)學(xué)回路與圖的連通性第一頁，共二十六頁，2022年，8月28日2

在圖中，一條通路是頂點(diǎn)和邊的交替序列，以頂點(diǎn)

開始，以頂點(diǎn)結(jié)束。其中，第一條邊的終點(diǎn)與第二條邊的始點(diǎn)重合…...。第一條邊的始點(diǎn)稱為通路的始點(diǎn)，最后一條邊的終點(diǎn)稱為通路的終點(diǎn)。當(dāng)通路的終點(diǎn)和始點(diǎn)重合時(shí)，稱為回路。通路或回路中所含邊數(shù)稱為該通路或回路的長度。一、通路和回路

第二頁，共二十六頁，2022年，8月28日31、簡單通路：如果通路中各邊都不相同。如簡單通路：v1→v2→v5→v6→v2→v3→v4長度為6如簡單回路：v1→v2→v3→v5→v2→v6→v1長度為62、簡單回路：如果回路中各邊都不相同。第三頁，共二十六頁，2022年，8月28日43、基本通路：如果通路中各個(gè)頂點(diǎn)和邊都不相同。4、基本回路(圈)：如果回路中各個(gè)頂點(diǎn)和邊都不相同。如基本通路：v1→v6→v3→v4長度為3如基本回路：v1→v6→v3→v2→v1顯然，基本通路（回路）一定是簡單通路（回路）。反之不然。第四頁，共二十六頁，2022年，8月28日5若通路(回路)中有邊重復(fù)出現(xiàn),則稱為復(fù)雜通路(回路).第五頁，共二十六頁，2022年，8月28日6關(guān)于通路與回路的幾點(diǎn)說明表示方法①用頂點(diǎn)和邊的交替序列(定義),如=v0e1v1e2…elvl②用邊的序列,如=e1e2…el③簡單圖中,用頂點(diǎn)的序列,如=v0v1…vl④非簡單圖中,可用混合表示法,如=v0v1e2v2e5v3v4v5環(huán)是長度為1的圈,兩條平行邊構(gòu)成長度為2的圈.第六頁，共二十六頁，2022年，8月28日7在圖G中，如果A到B存在一條通路，則稱A到B是可達(dá)的。1、無向圖的連通性如果無向圖中，任意兩點(diǎn)是可達(dá)的，圖為連通圖。否則為不連通圖。當(dāng)圖是不連通時(shí)，定是由幾個(gè)連通子圖構(gòu)成。稱這樣的連通圖是連通分支。二、圖的連通性：

第七頁，共二十六頁，2022年，8月28日8無向圖的連通性設(shè)無向圖G=<V,E>,u與v連通:若u與v之間有通路.規(guī)定u與自身總連通.連通關(guān)系R={<u,v>|u,v

V且uv}是V上的等價(jià)關(guān)系連通圖:平凡圖,任意兩點(diǎn)都連通的圖連通分支:V關(guān)于R的等價(jià)類的導(dǎo)出子圖設(shè)V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的連通分支,其個(gè)數(shù)記作p(G)=k.G是連通圖

p(G)=1若G為非連通圖，則P(G)≥2,在所有的n階無向圖中，n階零圖是連通分支最多的其分支數(shù)為n.第八頁，共二十六頁，2022年，8月28日9設(shè)A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}即:A上模3等價(jià)關(guān)系的關(guān)系圖為:

上述關(guān)系圖被分成三個(gè)互不連通的部分，每部分中的數(shù)兩兩都有關(guān)系，不同部分的圖無關(guān)系。第九頁，共二十六頁，2022年，8月28日10

【例】求證：若圖中只有兩個(gè)奇度數(shù)頂點(diǎn)，則二頂點(diǎn)必連通。證明用反證法來證明。設(shè)二頂點(diǎn)不連通，則它們必分屬兩個(gè)不同的連通分支，而對(duì)于每個(gè)連通分支，作為G的子圖只有一個(gè)奇度數(shù)頂點(diǎn)，余者均為偶度數(shù)頂點(diǎn)，與握手定理推論矛盾，因此，若圖中只有兩個(gè)奇度數(shù)頂點(diǎn)，則二頂點(diǎn)必連通。第十頁，共二十六頁，2022年，8月28日11

【例】在一次國際會(huì)議中，由七人組成的小組{a,b,c,d,e,f,g}中，a會(huì)英語、阿拉伯語；b會(huì)英語、西班牙語；c會(huì)漢語、俄語；d會(huì)日語、西班牙語；e會(huì)德語、漢語和法語；f會(huì)日語、俄語；g會(huì)英語、法語和德語。問：他們中間任何二人是否均可對(duì)話（必要時(shí)可通過別人翻譯）？第十一頁，共二十六頁，2022年，8月28日12解用頂點(diǎn)代表人，如果二人會(huì)同一種語言，則在代表二人的頂點(diǎn)間連邊，于是得到下圖。問題歸結(jié)為：在這個(gè)圖中，任何兩個(gè)頂點(diǎn)間是否都存在著通路？由于下圖是一個(gè)連通圖，因此，必要時(shí)通過別人翻譯，他們中間任何二人均可對(duì)話。第十二頁，共二十六頁，2022年，8月28日13定理在n階簡單圖G,如果對(duì)G的每對(duì)頂點(diǎn)u和v,deg(u)+deg(v)≥n–1,則G是連通圖。證明

假設(shè)G不連通,則G至少有兩個(gè)分圖。 設(shè)其中一個(gè)分圖含有q個(gè)頂點(diǎn),而其余各分圖共含有n–q個(gè)頂點(diǎn)。 在這兩部分中各取一個(gè)頂點(diǎn)u和v,則

0≤deg(u)≤q–1, 0≤deg(v)≤n–q–1,

因此deg(u)+deg(v)≤n–2,

這與題設(shè)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不連通,規(guī)定d(u,v)=∞.性質(zhì)：

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在實(shí)際問題中,除了考察一個(gè)圖是否連通外,往往還要研究一個(gè)圖連通的程度,作為某些系統(tǒng)的可靠性度量。圖的連通性在計(jì)算機(jī)網(wǎng)、通信網(wǎng)和電力網(wǎng)等方面有著重要的應(yīng)用。圖的連通性的應(yīng)用第十五頁，共二十六頁，2022年，8月28日162、有向圖的連通性對(duì)于有向圖，“圖中任意兩點(diǎn)都有通路相連”，這個(gè)要求很高，因?yàn)橛邢驁D雖然是連在一起的，但受到邊的方向的限制，任意兩點(diǎn)不一定有通路。以下分三種情況討論：第十六頁，共二十六頁，2022年，8月28日171）強(qiáng)連通圖：有向圖中，任意A、B是互為可達(dá)的。如圖(a)2）單向連通圖：在有向圖中，任意兩點(diǎn)A、B存在著A到B的通路或存在著B到A的通路。如圖(b)3）弱連通圖：在有向圖中，如果其底圖是無向連通圖。如圖(c)顯然：在有向圖中，如果有一條通過圖中所有點(diǎn)的回路，則此圖是強(qiáng)連通的。如果有一條通過圖中所有點(diǎn)的通路，則此圖是單向連通圖。(a)(b)(c)第十七頁，共二十六頁，2022年，8月28日18單向連通圖都是弱連通圖，但弱連通圖卻不一定是單向連通圖。在弱連通圖中，存在這樣的頂點(diǎn)A、B，從A到B不可達(dá)，且從B到A也不可達(dá)。強(qiáng)連通圖既是單向連通圖，又是弱連通圖。即強(qiáng)連通單向連通弱連通第十八頁，共二十六頁，2022年，8月28日19有向圖的連通性(續(xù))

定理(強(qiáng)連通判別法)

D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路定理(單向連通判別法)

D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路(1)(2)(3)例下圖(1)強(qiáng)連通,(2)單連通,(3)弱連通第十九頁，共二十六頁，2022年，8月28日20思考：判斷下列圖中哪些是強(qiáng)連通圖，哪些是單向連通圖，哪些是弱連通圖。(a)(b)(d)(c)答案:(a),(d)是強(qiáng)連通圖,(b)是單向連通圖,(c)是弱連通圖.第二十頁，共二十六頁，2022年，8月28日21有向圖的短程線與距離u到v的短程線:u到v長度最短的通路(u可達(dá)v)u與v之間的距離d<u,v>:u到v的短程線的長度若u不可達(dá)v,規(guī)定d<u,v>=∞.性質(zhì)：

d<u,v>0,且d<u,v>=0

u=vd<u,v>+d<v,w>d<u,w>

注意:沒有對(duì)稱性第二十一頁，共二十六頁，2022年，8月28日227.7設(shè)n階無向簡單圖G中，問應(yīng)為多少？解：由于，說明G中任何頂點(diǎn)v的度數(shù)而由于G為簡單圖，于是則有，因此說明G中每個(gè)頂點(diǎn)的度數(shù)都為n-1,于是有說明G為n-1階正則圖，即G為n階完全圖。第二十二頁，共二十六頁，2022年，8月28日237.8一個(gè)n(n≥2)階無向簡單圖G中，n為奇數(shù)，已知G中的r個(gè)奇數(shù)度頂點(diǎn)，問G的補(bǔ)圖有幾個(gè)奇數(shù)度頂點(diǎn)？解：由于而n為奇數(shù)，于是Kn中各頂點(diǎn)的度數(shù)n-1為偶數(shù)，對(duì)于，應(yīng)有，且由于n-1為偶數(shù)，所以同為奇數(shù)或同為偶數(shù)。因此G中的r個(gè)奇數(shù)度頂點(diǎn)，則也有r個(gè)奇數(shù)度頂點(diǎn)