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

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

在圖中，一條通路是頂點和邊的交替序列，以頂點

開始，以頂點結(jié)束。其中，第一條邊的終點與第二條邊的始點重合…...。第一條邊的始點稱為通路的始點，最后一條邊的終點稱為通路的終點。當(dāng)通路的終點和始點重合時，稱為回路。通路或回路中所含邊數(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、基本通路：如果通路中各個頂點和邊都不相同。4、基本回路(圈)：如果回路中各個頂點和邊都不相同。如基本通路：v1→v6→v3→v4長度為3如基本回路：v1→v6→v3→v2→v1顯然，基本通路（回路）一定是簡單通路（回路）。反之不然。第四頁，共二十六頁，2022年，8月28日5若通路(回路)中有邊重復(fù)出現(xiàn),則稱為復(fù)雜通路(回路).第五頁，共二十六頁，2022年，8月28日6關(guān)于通路與回路的幾點說明表示方法①用頂點和邊的交替序列(定義),如=v0e1v1e2…elvl②用邊的序列,如=e1e2…el③簡單圖中,用頂點的序列,如=v0v1…vl④非簡單圖中,可用混合表示法,如=v0v1e2v2e5v3v4v5環(huán)是長度為1的圈,兩條平行邊構(gòu)成長度為2的圈.第六頁，共二十六頁，2022年，8月28日7在圖G中，如果A到B存在一條通路，則稱A到B是可達的。1、無向圖的連通性如果無向圖中，任意兩點是可達的，圖為連通圖。否則為不連通圖。當(dāng)圖是不連通時，定是由幾個連通子圖構(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上的等價關(guān)系連通圖:平凡圖,任意兩點都連通的圖連通分支:V關(guān)于R的等價類的導(dǎo)出子圖設(shè)V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是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等價關(guān)系的關(guān)系圖為:

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

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

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

假設(shè)G不連通,則G至少有兩個分圖。 設(shè)其中一個分圖含有q個頂點,而其余各分圖共含有n–q個頂點。 在這兩部分中各取一個頂點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在實際問題中,除了考察一個圖是否連通外,往往還要研究一個圖連通的程度,作為某些系統(tǒng)的可靠性度量。圖的連通性在計算機網(wǎng)、通信網(wǎng)和電力網(wǎng)等方面有著重要的應(yīng)用。圖的連通性的應(yīng)用第十五頁，共二十六頁，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有向圖的連通性(續(xù))

定理(強連通判別法)

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

D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的通路(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,規(guī)定d<u,v>=∞.性質(zhì)：

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

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

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