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

離散數(shù)學(xué)回路與圖的連通性21、簡(jiǎn)單通路:如果通路中各邊都不相同。如簡(jiǎn)單通路:v1→v2→v5→v6→v2→v3→v4長(zhǎng)度為6如簡(jiǎn)單回路:v1→v2→v3→v5→v2→v6→v1長(zhǎng)度為62、簡(jiǎn)單回路:如果回路中各邊都不相同。33、基本通路:如果通路中各個(gè)頂點(diǎn)與邊都不相同。4、基本回路(圈):如果回路中各個(gè)頂點(diǎn)與邊都不相同。如基本通路:v1→v6→v3→v4長(zhǎng)度為3如基本回路:v1→v6→v3→v2→v1顯然,基本通路(回路)一定就是簡(jiǎn)單通路(回路)。反之不然。4若通路(回路)中有邊重復(fù)出現(xiàn),則稱為復(fù)雜通路(回路)、5關(guān)于通路與回路得幾點(diǎn)說(shuō)明表示方法①用頂點(diǎn)與邊得交替序列(定義),如

=v0e1v1e2…elvl②用邊得序列,如

=e1e2…el③簡(jiǎn)單圖中,用頂點(diǎn)得序列,如

=v0v1…vl④非簡(jiǎn)單圖中,可用混合表示法,如

=v0v1e2v2e5v3v4v5環(huán)就是長(zhǎng)度為1得圈,兩條平行邊構(gòu)成長(zhǎng)度為2得圈、6在圖G中,如果A到B存在一條通路,則稱A到B就是可達(dá)得。1、無(wú)向圖得連通性如果無(wú)向圖中,任意兩點(diǎn)就是可達(dá)得,圖為連通圖。否則為不連通圖。當(dāng)圖就是不連通時(shí),定就是由幾個(gè)連通子圖構(gòu)成。稱這樣得連通圖就是連通分支。二、圖得連通性:

7無(wú)向圖得連通性設(shè)無(wú)向圖G=<V,E>,u與v連通:若u與v之間有通路、規(guī)定u與自身總連通、連通關(guān)系R={<u,v>|u,v

V且u

v}就是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階無(wú)向圖中,n階零圖就是連通分支最多得其分支數(shù)為n、8設(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)系,不同部分得圖無(wú)關(guān)系。9

【例】求證:若圖中只有兩個(gè)奇度數(shù)頂點(diǎn),則二頂點(diǎn)必連通。證明用反證法來(lái)證明。設(shè)二頂點(diǎn)不連通,則她們必分屬兩個(gè)不同得連通分支,而對(duì)于每個(gè)連通分支,作為G得子圖只有一個(gè)奇度數(shù)頂點(diǎn),余者均為偶度數(shù)頂點(diǎn),與握手定理推論矛盾,因此,若圖中只有兩個(gè)奇度數(shù)頂點(diǎn),則二頂點(diǎn)必連通。10

【例】在一次國(guó)際會(huì)議中,由七人組成得小組{a,b,c,d,e,f,g}中,a會(huì)英語(yǔ)、阿拉伯語(yǔ);b會(huì)英語(yǔ)、西班牙語(yǔ);c會(huì)漢語(yǔ)、俄語(yǔ);d會(huì)日語(yǔ)、西班牙語(yǔ);e會(huì)德語(yǔ)、漢語(yǔ)與法語(yǔ);f會(huì)日語(yǔ)、俄語(yǔ);g會(huì)英語(yǔ)、法語(yǔ)與德語(yǔ)。問(wèn):她們中間任何二人就是否均可對(duì)話(必要時(shí)可通過(guò)別人翻譯)？11解用頂點(diǎn)代表人,如果二人會(huì)同一種語(yǔ)言,則在代表二人得頂點(diǎn)間連邊,于就是得到下圖。問(wèn)題歸結(jié)為:在這個(gè)圖中,任何兩個(gè)頂點(diǎn)間就是否都存在著通路？由于下圖就是一個(gè)連通圖,因此,必要時(shí)通過(guò)別人翻譯,她們中間任何二人均可對(duì)話。大家學(xué)習(xí)辛苦了，還是要堅(jiān)持繼續(xù)保持安靜13定理在n階簡(jiǎ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矛盾。14無(wú)向圖得短程線與距離u與v之間得短程線:u與v之間長(zhǎng)度最短得通路

(u與v連通)u與v之間得距離d(u,v):u與v之間短程線得長(zhǎng)度若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)15在實(shí)際問(wèn)題中,除了考察一個(gè)圖就是否連通外,往往還要研究一個(gè)圖連通得程度,作為某些系統(tǒng)得可靠性度量。圖得連通性在計(jì)算機(jī)網(wǎng)、通信網(wǎng)與電力網(wǎng)等方面有著重要得應(yīng)用。圖得連通性得應(yīng)用162、有向圖得連通性對(duì)于有向圖,“圖中任意兩點(diǎn)都有通路相連”,這個(gè)要求很高,因?yàn)橛邢驁D雖然就是連在一起得,但受到邊得方向得限制,任意兩點(diǎn)不一定有通路。以下分三種情況討論:171)強(qiáng)連通圖:有向圖中,任意A、B就是互為可達(dá)得。如圖(a)2)單向連通圖:在有向圖中,任意兩點(diǎn)A、B存在著A到B得通路或存在著B(niǎo)到A得通路。如圖(b)3)弱連通圖:在有向圖中,如果其底圖就是無(wú)向連通圖。如圖(c)顯然:在有向圖中,如果有一條通過(guò)圖中所有點(diǎn)得回路,則此圖就是強(qiáng)連通得。如果有一條通過(guò)圖中所有點(diǎn)得通路,則此圖就是單向連通圖。(a)(b)(c)18單向連通圖都就是弱連通圖,但弱連通圖卻不一定就是單向連通圖。在弱連通圖中,存在這樣得頂點(diǎn)A、B,從A到B不可達(dá),且從B到A也不可達(dá)。強(qiáng)連通圖既就是單向連通圖,又就是弱連通圖。即強(qiáng)連通

單向連通

弱連通19有向圖得連通性(續(xù))

定理(強(qiáng)連通判別法)D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次得回路定理(單向連通判別法)D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次得通路(1)(2)(3)例下圖(1)強(qiáng)連通,(2)單連通,(3)弱連通20思考:判斷下列圖中哪些就是強(qiáng)連通圖,哪些就是單向連通圖,哪些就是弱連通圖。(a)(b)(d)(c)答案:(a),(d)就是強(qiáng)連通圖,(b)就是單向連通圖,(c)就是弱連通圖、21有向圖得短程線與距離u到v得短程線:u到v長(zhǎng)度最短得通路(u可達(dá)v)u與v之間得距離d<u,v>:u到v得短程線得長(zhǎng)度若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>

注意:沒(méi)有對(duì)稱性227、7設(shè)n階無(wú)向簡(jiǎn)單圖G中,問(wèn)應(yīng)為多少？解：由于，說(shuō)明G中任何頂點(diǎn)v的度數(shù)而由于G為簡(jiǎn)單圖，于是則有，因此說(shuō)明G中每個(gè)頂點(diǎn)得度數(shù)都為n-1,于就是有說(shuō)明G為n-1階正則圖,即G為n階完全圖。237、8一個(gè)n(n≥2)階無(wú)向簡(jiǎn)單圖G中,n為奇數(shù),已知G中得r個(gè)奇數(shù)度頂點(diǎn),問(wèn)G得補(bǔ)圖有幾個(gè)奇數(shù)度頂點(diǎn)？解:由于而n為奇數(shù),于就是Kn中各頂點(diǎn)得度數(shù)n-1為偶數(shù),對(duì)于，應(yīng)有，且由于n-1為偶數(shù)，所以