chap14有向圖

1、1第十四章第十四章 有向圖有向圖214.1 有向圖的概念有向圖的概念3有向圖的定義有向圖的定義4定義定義14.1.1：一個有向圖：一個有向圖D是一個有序三元組是一個有序三元組 ,其中，其中，41)V(D)是非空頂點集合，簡記為是非空頂點集合，簡記為V ;42)A(D)是弧的集合，簡記為是弧的集合，簡記為A，AV= ;43) D是是A到到V V=|u , vV的一個映射，的一個映射，稱為關(guān)聯(lián)函數(shù)，簡記為稱為關(guān)聯(lián)函數(shù)，簡記為 .4為方便，有時將為方便，有時將簡記為簡記為uv . 易知，易知，uv = vu當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)u =v .注：有向圖可以簡單理解為注：有向圖可以簡單理解為“邊有方向的圖邊有

2、方向的圖”4一個有向圖一個有向圖4設(shè)設(shè)V=u ,v ,w, x, A= 1 , 2 , , 9, 定義如下：定義如下： ( 1) =uv , ( 2) =vv , ( 3) =vw , ( 4) =xw , ( 5) =vx , ( 6) =xv , ( 7) =xu , ( 8) =ux , ( 9) =xu .xuwv1589647325有向圖與無向圖有向圖與無向圖4無向圖與有向圖的區(qū)別：無向圖與有向圖的區(qū)別：無向圖中的無向圖中的 是將邊映是將邊映射為頂點的射為頂點的無序無序?qū)ε?，對偶，uv = vu。而。而有向圖中的有向圖中的映射映射 D是將邊映射為頂點的是將邊映射為頂點的有序有序?qū)ε迹?/p>

3、對偶，uvvu，故為有向故為有向。有向圖有向圖D不記弧的方向不記弧的方向D的的基礎(chǔ)圖基礎(chǔ)圖無向圖無向圖G規(guī)定邊的方向規(guī)定邊的方向G的定向圖的定向圖6有向圖中的弧（邊）有向圖中的?。ㄟ叄?弧的頭和尾弧的頭和尾：如果：如果 是有向圖是有向圖D的一條弧，且的一條弧，且 ( ) =uv , 則則稱稱u是是 的尾，的尾，v是是 的頭。的頭。4環(huán)環(huán)：有向圖中頭尾相同的弧。：有向圖中頭尾相同的弧。4多重弧多重?。簝蓷l或兩條以上的：兩條或兩條以上的頭尾相同頭尾相同的弧。的弧。4簡單有向圖簡單有向圖：無環(huán)，無多重：無環(huán)，無多重弧的有向圖?；〉挠邢驁D。uv多重弧非多重弧7有向圖中的度有向圖中的度4出度出度：在有向

4、圖中，以頂：在有向圖中，以頂點點u為尾的?。◤臑槲驳幕。◤膗射出的射出的?。┑臄?shù)目稱為?。┑臄?shù)目稱為u的出度，的出度，記為記為dD+(u) ;4入度入度：在有向圖中，以頂：在有向圖中，以頂點點u為頭的?。ㄉ淙霝轭^的?。ㄉ淙雞的?。┑幕。┑臄?shù)目稱為的數(shù)目稱為u的入度，記為的入度，記為dD (u) ;4度度：頂點：頂點u的入度與出度的的入度與出度的和為和為u的度的度,記為記為 dD(u)= dD+(u)+ dD (u) ;dD+(a)=2dD- (a)=1dD(a)=38有向圖中的途徑有向圖中的途徑4有向途徑有向途徑:有向圖中一個有向圖中一個頭尾相接頭尾相接的途徑，即：的途徑，即：w=v0 1v1

5、, kvk，viV(D), jA(D)且且 D( j)= vi-1 vi ( j的弧尾是的弧尾是vi-1 ，弧頭是，弧頭是vi )，i=0,1,k , j=1,k；4有向鏈有向鏈：弧不重復(fù)的有向途徑；：弧不重復(fù)的有向途徑；4有向通路有向通路：頂點不重復(fù)的有向途徑，：頂點不重復(fù)的有向途徑，u為起點，為起點，v為終點的有向通路記為為終點的有向通路記為(u,v)-通路；通路；4有向通路長度有向通路長度：通路上弧的數(shù)目；：通路上弧的數(shù)目；4有向回路有向回路：起點和終點重合的有向通路；：起點和終點重合的有向通路；4有向有向k-回路回路：長度為：長度為k的有向回路；的有向回路；注：以上概念與無向圖中相關(guān)概

6、念類似，只是增注：以上概念與無向圖中相關(guān)概念類似，只是增加了方向性。加了方向性。9有向圖的連通性有向圖的連通性4定義定義14.1.2：設(shè)：設(shè)D是有向圖，是有向圖，若對若對D中任意頂點中任意頂點u、v，同時有，同時有(u, v)通通路和路和(v, u)通路存在，稱通路存在，稱D是雙向連通圖，或強是雙向連通圖，或強連通圖；連通圖；若對若對D中任意頂點中任意頂點u、v，或有，或有(u, v)通路，通路，或有或有(v, u)通路，稱通路，稱D是單連通圖是單連通圖; 若若D的基礎(chǔ)圖是連通圖，則稱的基礎(chǔ)圖是連通圖，則稱D是弱連通是弱連通圖。圖。4顯然，強連通圖顯然，強連通圖單連通圖單連通圖弱連通圖。弱連通

7、圖。有向圖的連通性有向圖的連通性(a)是強連通的是強連通的(b)是單連通的是單連通的(c)是弱連通的是弱連通的強連通圖的充要條件（補充）強連通圖的充要條件（補充）4定理：有向圖定理：有向圖D=(V,A)是強連通的，當(dāng)且是強連通的，當(dāng)且僅當(dāng)僅當(dāng)D中存在包含中存在包含D中所有頂點中所有頂點的有向閉的有向閉鏈。鏈。11v1v5v4v2v3v6Dv1v2v3v4v512強連通分支強連通分支4強連通分支強連通分支：有向圖：有向圖D的極大強連通子圖的極大強連通子圖.該圖有三個強連通分支,如圖所示（用紅、綠、藍(lán)三種顏色標(biāo)記）。1314.2 有向通路與有向回路有向通路與有向回路14有向通路的長度有向通路的長度

8、4有向圖中有向通路的長度與其基礎(chǔ)圖中有向圖中有向通路的長度與其基礎(chǔ)圖中的（無向）通路的長度無關(guān)。的（無向）通路的長度無關(guān)。4卻與圖的色數(shù)有關(guān)卻與圖的色數(shù)有關(guān) .最長有向通路長度最長有向通路長度=1色數(shù)色數(shù) (G)=215有向通路之長不短于色數(shù)減一有向通路之長不短于色數(shù)減一4定理定理14.2.1 ：有向圖：有向圖D中包含長度至少為中包含長度至少為 (G) 1的有向通路。其中，的有向通路。其中，G為為D的基礎(chǔ)圖。的基礎(chǔ)圖。4證明思路：證明思路：1.尋找有向圖尋找有向圖D的最長有向通路的最長有向通路k2.構(gòu)造一個構(gòu)造一個(k+1)點著色點著色3.證明證明是正常（是正常（k+1）著色）著色4.由圖色數(shù)

9、由圖色數(shù) (G)k+1得結(jié)論：得結(jié)論：k (G) 116v1v2v3Dv51(a).令令 A 是使是使D不含有向回路所需刪去的最小弧集不含有向回路所需刪去的最小弧集v4A=(v5v2)1(b).令令D =D A ，設(shè)，設(shè)D 中最長有向通路的中最長有向通路的長度為長度為k Dk=32(a).對對D 進(jìn)行點進(jìn)行點著色著色 ：若若D 中以中以v為起點的最為起點的最長有向通路之長為長有向通路之長為i-1，令令 (v)=i432122(b).這樣這樣就得到一就得到一個個 (k+1)著色著色 。下。下證證 是是G的正常的正常(k+1)著色。著色。17v1v2v3Dv53(a). D 中中任何一條有向任何一

10、條有向(u, v)-通路通路(uv)P均均滿足滿足 (u) (v)v43(b). D 中中的任何弧的任何弧(u,v) 的首尾不同色的首尾不同色D432124. 總之，基礎(chǔ)圖總之，基礎(chǔ)圖G的的任何兩個鄰接的頂任何兩個鄰接的頂點在點在 下均不同色，下均不同色，即即 是是G的正常的正常(k+1)著色著色。故故k (G) 118競賽圖競賽圖4競賽圖競賽圖：完全圖的定向圖稱為競賽圖。：完全圖的定向圖稱為競賽圖。4 n階競賽圖可用來表示階競賽圖可用來表示n個選手之間進(jìn)行個選手之間進(jìn)行循環(huán)賽的勝負(fù)狀態(tài)。循環(huán)賽的勝負(fù)狀態(tài)。有一人全勝，其余各勝一場：有一人全輸，其余各勝兩場：19競賽圖都含有向競賽圖都含有向H通

11、路通路4有向圖有向圖D的的有向有向H通路通路是指一條包含是指一條包含D的所有頂?shù)乃许旤c的有向通路（點的有向通路（有向有向哈密爾頓哈密爾頓通路通路）。）。4推論推論14.2.1：每個競賽圖都含有向：每個競賽圖都含有向H通路。通路。 證明：設(shè)證明：設(shè)D是競賽圖，是競賽圖， D的基礎(chǔ)圖的基礎(chǔ)圖G是完全圖，是完全圖，于是，于是， (G) = |V(D)| =p , 由定理由定理14.2.1知，知，D中含長為中含長為p1的有向通路，的有向通路，也就是說，該通路上包含了所有的也就是說，該通路上包含了所有的p個頂點，個頂點，即為有向即為有向H通路。通路。有向有向H圖的應(yīng)用圖的應(yīng)用4任務(wù)的最佳排序問題任務(wù)的

12、最佳排序問題：假設(shè)有任務(wù)：假設(shè)有任務(wù)t1, t2, tn需在需在同一設(shè)備上同一設(shè)備上串行串行執(zhí)行，從執(zhí)行，從任務(wù)任務(wù)ti轉(zhuǎn)到任務(wù)轉(zhuǎn)到任務(wù)tj所需的所需的設(shè)備調(diào)整時間是設(shè)備調(diào)整時間是aij，如何排任務(wù)執(zhí)行次序，使設(shè)，如何排任務(wù)執(zhí)行次序，使設(shè)備調(diào)整需時間最少？備調(diào)整需時間最少？41、建、建圖圖：建立建立有向圖有向圖D, 頂點對應(yīng)于要執(zhí)行的任務(wù)，頂點對應(yīng)于要執(zhí)行的任務(wù)，vivj A(D)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)aij aji。邊。邊vivj帶權(quán)帶權(quán)aij。42、分析：、分析：D必含競賽圖作為生成子圖必含競賽圖作為生成子圖(當(dāng)當(dāng)aij=aji時時底圖是多重圖底圖是多重圖)。因此。因此D中含有向中含有向哈密爾頓

13、哈密爾頓通路通路。43、求解：、求解：問題問題的解對應(yīng)于最小權(quán)的有向哈密爾頓的解對應(yīng)于最小權(quán)的有向哈密爾頓通路。通路。 21強連通競賽圖的性質(zhì)強連通競賽圖的性質(zhì)4定理定理14.2.3 ：頂點數(shù)頂點數(shù)p 3的強連通競賽圖的強連通競賽圖D的每個頂點都包含在一條有向的每個頂點都包含在一條有向k-回路中，其回路中，其中中3 k p .4推論推論14.2.3：任何強連通競賽圖都含有向：任何強連通競賽圖都含有向H回回路路 . 4定理定理14.2.4 若若D是簡單有向圖，并且是簡單有向圖，并且 min , + p/2 1 , 則則D中含有向中含有向H回路回路 . (推論推論8.2.1 G為簡單圖，若為簡單圖

14、，若 (G) p/2 , 則則G為為H圖圖 .)2214.3 有向樹及其應(yīng)用有向樹及其應(yīng)用23有向樹有向樹4定義定義14.3.1：若有向圖：若有向圖T的基礎(chǔ)圖是樹，則稱的基礎(chǔ)圖是樹，則稱T是有向樹。是有向樹。4下面是兩棵有向樹，請注意它們的不同：下面是兩棵有向樹，請注意它們的不同：24根樹根樹4定義定義14.3.2 設(shè)設(shè)T是一個有向樹，如果是一個有向樹，如果T中中恰有恰有一個頂點的入度為一個頂點的入度為0，其它頂點的入度均為，其它頂點的入度均為1，則稱則稱T為為根樹根樹。根樹。根樹T中入度為中入度為0的頂點稱為的頂點稱為T的的根根，記為，記為vr或或v0；根樹中出度為；根樹中出度為0的頂點稱為

15、的頂點稱為葉；葉；根樹中出度不為根樹中出度不為0的頂點稱為的頂點稱為分枝點分枝點。4注意：注意：根樹是一種特殊的有向樹，并非所有的根樹是一種特殊的有向樹，并非所有的有向樹都是根樹。有向樹都是根樹。圖論圖論中中“樹樹”的概念要的概念要比比數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中的中的“樹樹”的概念廣泛的多。的概念廣泛的多。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中的中的“樹樹”僅僅是這里的根樹。僅僅是這里的根樹。25根樹的表示根樹的表示4對根樹，我們一般將根畫在最上面，即對根樹，我們一般將根畫在最上面，即根在第根在第0層，其它頂點層，其它頂點u按根到按根到u的唯一有的唯一有向通路的長度由上至下依次畫出，即將向通路的長度由上至下依次畫出，即將

16、長度為長度為i的頂點畫在第的頂點畫在第i層。并規(guī)定弧的方層。并規(guī)定弧的方向一律朝下，于是箭頭可以省略不畫；向一律朝下，于是箭頭可以省略不畫；4樹的高度：從根出發(fā)最長的有向通路之樹的高度：從根出發(fā)最長的有向通路之長稱為長稱為T的的高度高度（深度）深度）。26子樹子樹4T是一個樹，是一個樹，v是是T的一個分枝結(jié)點，由以的一個分枝結(jié)點，由以v以以及及T中從中從v出發(fā)可達(dá)到的所有頂點連同所經(jīng)過的出發(fā)可達(dá)到的所有頂點連同所經(jīng)過的弧構(gòu)成以弧構(gòu)成以v為根的為根的T的一個子樹的一個子樹.4右邊樹中紅色的部分是不右邊樹中紅色的部分是不是一個子樹呢？是一個子樹呢？4注意：注意：右邊樹中紅色的部右邊樹中紅色的部分不

17、是一個子樹！分不是一個子樹！27根樹中的術(shù)語及其示例根樹中的術(shù)語及其示例T的的高度高度為為3 ;v0v1v2v3v4v5v6v7v8v9v10T:v2為v6 , v7 , v8的 父結(jié)點 ;v6 , v7 , v8為v2的 子結(jié)點 ;v4 , v5 互為兄弟結(jié)點 ;v9 , v10為v0 , v2的 后裔 ;v0 , v2 為v9 , v10的 祖先 ;T中的藍(lán)色結(jié)點及弧構(gòu)成T的一個以v2為根的子樹. 28有序樹有序樹4定義定義14.3.3：若對一個樹：若對一個樹T的結(jié)點的結(jié)點(弧弧)從從上至下，同一層結(jié)點上至下，同一層結(jié)點(弧弧)從左至右規(guī)定了從左至右規(guī)定了一個次序，則稱一個次序，則稱T為有

18、序樹。為有序樹。 4有序樹的編號：有序樹的編號：v0v1v2v3v21v22v31v211v212v21329m元元(有序有序)樹樹4定義定義14.3.4：設(shè)：設(shè)T是是(有序有序)樹，樹，m 1。若對若對T的每個結(jié)點的每個結(jié)點v，均有，均有d+(v) m，則稱，則稱T為為m元元(有序有序)樹樹 ;若對若對T的每個結(jié)點的每個結(jié)點v，均有，均有d+(v) = m或或d+(v) = 0，則稱則稱T為完全為完全m元元(有序有序)樹；樹；若完全若完全m元元(有序有序)樹的所有葉結(jié)點都在同一層，樹的所有葉結(jié)點都在同一層，則稱則稱T為正則為正則m元元(有序有序)樹樹 ;4當(dāng)當(dāng)m=2時，分別稱之為二叉樹；完全

19、二叉樹；時，分別稱之為二叉樹；完全二叉樹； 正則二叉樹。正則二叉樹。30完全完全m元樹上的數(shù)量關(guān)系元樹上的數(shù)量關(guān)系4定理定理14.3.1 設(shè)設(shè)T是一個完全是一個完全m元樹，其中有元樹，其中有t個個葉結(jié)點，葉結(jié)點，i個分枝結(jié)點，于是個分枝結(jié)點，于是4 (m1) i = t14證明：將證明：將m元樹看成是每局有元樹看成是每局有m位選手參加比位選手參加比賽的單淘汰賽計劃表，樹葉表示選手，分枝點賽的單淘汰賽計劃表，樹葉表示選手，分枝點i表示每局表示每局(分組賽分組賽)的冠軍，根表示最后的冠軍。的冠軍，根表示最后的冠軍。 因為每局要淘汰因為每局要淘汰(m1)個人，因此，個人，因此，i局比賽共局比賽共淘汰

20、淘汰(m1) i個人，最后剩下一位冠軍。故有個人，最后剩下一位冠軍。故有(m1) i +1 = t ，整理得證，整理得證.31應(yīng)用舉例應(yīng)用舉例4某機房有某機房有42臺臺PC，公用一個電源插座，若每，公用一個電源插座，若每臺臺PC只需一個插座，需要多少個只需一個插座，需要多少個4插座的接線插座的接線板？板？4解：一個有解：一個有4插座的接線板可以連接插座的接線板可以連接4個接線板個接線板因此就構(gòu)成了一個因此就構(gòu)成了一個4元樹。即接線板看成分枝元樹。即接線板看成分枝結(jié)點，結(jié)點， PC看成樹葉。于是根據(jù)定理看成樹葉。于是根據(jù)定理14.3.1有：有：i=(t 1)/(m 1)。4將將t=42，m=4，

21、代入上式可得，代入上式可得i=(42 1)/(4 1) = 13.66 144答：需要答：需要14個個4插座的接線板。插座的接線板。32二叉樹的應(yīng)用二叉樹的應(yīng)用4遠(yuǎn)程通訊中的編碼問題：用遠(yuǎn)程通訊中的編碼問題：用01序列作為英文序列作為英文字母的傳送信息。字母的傳送信息。 (1)序列與字母如何對應(yīng)？序列與字母如何對應(yīng)？ (2)如何譯碼？如何譯碼？4編碼應(yīng)注意的事項：編碼應(yīng)注意的事項： (1)使用頻率越高的字母對應(yīng)的碼序列越短使用頻率越高的字母對應(yīng)的碼序列越短; (2)避免某一個字母對應(yīng)的碼是另一個字母所避免某一個字母對應(yīng)的碼是另一個字母所對應(yīng)的碼的前綴對應(yīng)的碼的前綴 .33前綴碼前綴碼4定義定義14.3.5：設(shè)：設(shè) =b1b2bn，bi0, 1是是一個一個0-1序列序列(符號串符號串)。序列。序列 = b1b2bi (1 i n)稱為稱為 的前綴。的前綴。4例如例如,設(shè)設(shè) =010 , 則則, 0 , 01 ,010都是都是 的前的前綴綴.4前綴碼前綴碼: 設(shè)設(shè)Q = 1, 2, , m是一個是一個01序列集合序列集合 . 如果如果Q中沒有一個序列是另一中沒有一個序列是另一個序列的前綴個序列的前綴 , 則稱則稱Q為前綴碼為前綴碼.34二叉樹對應(yīng)前綴碼二叉樹對應(yīng)前綴碼4定理定理14.3.2：任何一個二叉樹的葉子可以對應(yīng)：任何一個二叉樹的葉子可以對應(yīng)一