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

離散數(shù)學回路與圖的連通性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若通路(回路)中有邊重復出現(xiàn),則稱為復雜通路(回路)、5關于通路與回路得幾點說明表示方法①用頂點與邊得交替序列(定義),如

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

=e1e2…el③簡單圖中,用頂點得序列,如

=v0v1…vl④非簡單圖中,可用混合表示法,如

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

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

V且u

v}就是V上得等價關系連通圖:平凡圖,任意兩點都連通得圖連通分支:V關于R得等價類得導出子圖設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、8設A={1,2,…,8},

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

上述關系圖被分成三個互不連通得部分,每部分中得數(shù)兩兩都有關系,不同部分得圖無關系。9

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

【例】在一次國際會議中,由七人組成得小組{a,b,c,d,e,f,g}中,a會英語、阿拉伯語;b會英語、西班牙語;c會漢語、俄語;d會日語、西班牙語;e會德語、漢語與法語;f會日語、俄語;g會英語、法語與德語。問:她們中間任何二人就是否均可對話(必要時可通過別人翻譯)？11解用頂點代表人,如果二人會同一種語言,則在代表二人得頂點間連邊,于就是得到下圖。問題歸結為:在這個圖中,任何兩個頂點間就是否都存在著通路？由于下圖就是一個連通圖,因此,必要時通過別人翻譯,她們中間任何二人均可對話。大家學習辛苦了，還是要堅持繼續(xù)保持安靜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不連通,規(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在實際問題中,除了考察一個圖就是否連通外,往往還要研究一個圖連通得程度,作為某些系統(tǒng)得可靠性度量。圖得連通性在計算機網(wǎng)、通信網(wǎng)與電力網(wǎng)等方面有著重要得應用。圖得連通性得應用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有向圖得連通性(續(xù))

定理(強連通判別法)D強連通當且僅當D中存在經(jīng)過每個頂點至少一次得回路定理(單向連通判別法)D單向連通當且僅當D中存在經(jīng)過每個頂點至少一次得通路(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,規(guī)定d<u,v>=∞、性質(zhì):

d<u,v>

0,且d<u,v>=0

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

d<u,w>

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