實用工程數(shù)學(xué)7圖論2課件

1、 無向圖的矩陣表示一 有向圖的矩陣表示二 7.3 圖的矩陣表示 第三節(jié) 圖的矩陣表示 7.3 圖的矩陣表示 圖可以用數(shù)學(xué)定義來描述，也可以用圖形表示，還可以用矩陣來表示.一、無向圖的矩陣表示1.無向圖的關(guān)聯(lián)矩陣 7.3 圖的矩陣表示無向圖的關(guān)聯(lián)矩陣中的元素 的確定 【例1】 已知圖，寫出圖的矩陣.【解】圖的矩陣表示為 7.3 圖的矩陣表示關(guān)聯(lián)矩陣的性質(zhì)： 7.3 圖的矩陣表示 顯然矩陣中的元素mij可能取值為0(vi與ej不關(guān)聯(lián))，1(vi與ej關(guān)聯(lián)1次)，2(vi與ej關(guān)聯(lián)2次，即ej是以vi為端點的環(huán)).v3v1e4v2v4v5e1e3e5e6e7v6e21 0 0 0 1 0 00 0

2、0 0 0 10 0 1 0 0 1 00 0 1 1 0 0 10 0 0 1 1 0 00 2 0 0 0 1 0v1 v2 v3 v4 v5 v6e1 e2 e3 e4 e5 e6 e7圖的關(guān)聯(lián)矩陣?yán)瑢懗鱿聢D的關(guān)聯(lián)矩陣 7.3 圖的矩陣表示習(xí)題7-3，4.求圖727的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣為 7.3 圖的矩陣表示例如，下圖的鄰接矩陣為A 【定義2】設(shè) 是無向簡單圖， ，令 其中矩陣中的元素 為兩點間的邊的條數(shù)，則稱矩陣 為的G鄰接矩陣，記作A(G)，簡記A. 7.3 圖的矩陣表示無向簡單圖的鄰接矩陣【問題】根據(jù)下圖，寫出其鄰接矩陣 ?【答案】其鄰接矩陣為： 7.3 圖的矩陣表示習(xí)題7-3，5

3、.求圖728的鄰接矩陣鄰接矩陣為 7.3 圖的矩陣表示二、有向圖的矩陣表示1.有向圖的關(guān)聯(lián)矩陣 例如，下圖的關(guān)聯(lián)矩陣是： 【定義3 】設(shè) 是無環(huán)有向圖， ， , 令 7.3 圖的矩陣表示有向圖的關(guān)聯(lián)矩陣的性質(zhì)例如，下有向圖的關(guān)聯(lián)矩陣為：-1 -1 1 1 0 0 00 1 -1 0 1 0 00 0 0 -1 0 1 -11 0 0 0 -1 -1 1 7.3 圖的矩陣表示2.有向圖的鄰接矩陣v1例如，下圖的鄰接矩陣是？鄰接矩陣中的元素為起點到終點的邊的條數(shù) 7.3 圖的矩陣表示鄰接矩陣的性質(zhì)若鄰接矩陣的元素全為零,則其對應(yīng)的圖是零圖若對角線元素為1,則表其對應(yīng)結(jié)點上有環(huán)若對角線元素為零，其余

4、元素全為1，則其對應(yīng)圖為完全圖矩陣某結(jié)點行的和為出度,列的和為入度矩陣所有元素之和為圖的邊的總數(shù)【問題】指出下圖的鄰接矩陣.v1v2v3v41 2 1 00 0 1 00 0 0 10 0 1 0 v1 v2 v3 v4v1 v2 v3 v4【答案】圖的鄰接矩陣： 7.3 圖的矩陣表示P151，習(xí)題7-3，4（1）寫出圖的鄰接矩陣 7.3 圖的矩陣表示 3.有向圖的可達矩陣?yán)纾聢D的可達矩陣P為 7.3 圖的矩陣表示v1v2v3v41 1 1 10 1 1 10 0 1 10 0 1 1P(D)= v1 v2 v3 v4v1 v2 v3 v4【問題】寫出下圖的可達矩陣.【答案】圖的可達矩陣為

5、 第四節(jié) 歐拉圖與哈密頓圖 7.4 歐拉圖與哈密頓圖二 歐拉圖的應(yīng)用 歐拉圖一四 哈密頓圖的應(yīng)用 三哈密頓圖 哥尼斯堡七橋問題 如何不重復(fù)地走完七橋后回到起點？ 陸地 島嶼 島嶼 陸地 一、歐拉圖抽象轉(zhuǎn)化 7.4 歐拉圖與哈密頓圖 7.4 歐拉圖與哈密頓圖 4個圖中, 不能一筆畫出圖, , 而能一筆畫出圖, 且在中筆又能回到出發(fā)點。ABCD 筆不離開紙，不重復(fù)地走完所有的邊，(回到原處或不回到原處），就是所謂的一筆畫.下面哪些圖能一筆畫？找出能一筆畫的圖規(guī)律？ABCDEFGHJ1234567891011121314 7.4 歐拉圖與哈密頓圖 【定義1】 通過圖中每條邊恰好一次,且經(jīng)過所有頂點的

6、路稱為歐拉路. 通過圖中每條邊恰好一次且經(jīng)過所有頂點的回路稱為歐拉回路. 具有歐拉回路的圖稱為歐拉圖. 具有歐拉路而無歐拉回路的圖稱為半歐拉圖。存在歐拉回路，是歐拉圖.只存在歐拉路，無回路.不是歐拉圖，是半歐拉圖. 一、歐拉圖 7.4 歐拉圖與哈密頓圖 【例1】 下列各圖，哪些是歐拉圖，哪些是半歐拉圖?或者兩者都不是. 【解】圖（a）中有歐拉回路: abcdeca,所以圖（a）是歐拉圖. 圖（b）中存在歐拉路：abcdac，但不存在歐拉回路，所以圖（b）不是歐拉圖，但是半歐拉圖.(a)cacbde(b)cabcd(C) 圖（C）中不存在歐拉路，自然不存在歐拉回路，所以圖（b）兩者都不是.一個圖

7、滿足什么樣要的條件才存在歐拉回路呢？ 7.4 歐拉圖與哈密頓圖 一、歐拉圖 【定理1】(1) 無向連通圖具有歐拉回路的充要條件是：圖中所有結(jié)點的度數(shù)是偶數(shù) (2)無向連通圖具有歐拉路而無歐拉回路的充要條件是：圖中恰有兩個奇度結(jié)點（其余結(jié)點的度數(shù)全為偶數(shù)），并且這兩個奇度結(jié)點是歐拉路的兩個端點 ABCD 根據(jù)無向圖中，歐拉回路和歐拉路的判別準(zhǔn)則知，哥尼斯堡七橋問題有了準(zhǔn)確的答案. 由于 ,故不存在歐拉路，當(dāng)然也就不存在歐拉回路，因此一次走完所有的橋的路線是不存在的. 7.4 歐拉圖與哈密頓圖 【例2】據(jù)歐拉圖和歐拉路的判別準(zhǔn)則知，下圖中，由于圖、中每個結(jié)點的度數(shù)都是偶數(shù)，則存在歐拉回路，都是歐拉

8、圖，故可以一筆畫. 圖中，不是恰有兩個奇度結(jié)點，而是有四個奇度結(jié)點，則不存在歐拉通路，故不能一筆畫（2）（1）（3） 7.4 歐拉圖與哈密頓圖【問題】 考察下圖是否為歐拉圖 或存在歐拉通路？ 【答案】因 存在兩個奇度頂點A、B，故根據(jù)歐拉定理知，上圖不是歐拉圖，但存在一條歐拉路. 具體的歐拉路是？CADB 7.4 歐拉圖與哈密頓圖 【問題】 下列圖是否為歐拉圖或存在歐拉通路？ 【答案】 在圖(1)中, d(v1)= d(v2) =d(v3)3，有兩個以上的奇度頂點. 根據(jù)定理1知: 圖(1)中不存在歐拉通路，當(dāng)然不存在歐拉回路, 所以不是歐拉圖. 不能一筆畫出. 在圖(2)中,d(A)=2,

9、d(B) =d(C)= d(D)=4,d(E)=d(G)=3,恰有兩個奇度結(jié)點.根據(jù)定理1知,它不是歐拉圖，但存在一條歐拉通路, 如EDBEFCABCDF.E593 10 847612F,F10 932167485E.（1）（27.4 歐拉圖與哈密頓圖 【定理2 】(1) 連通的有向圖具有歐拉回路的充要條件是：圖中的所有結(jié)點的入度和出度相等.所有結(jié)點的入度和出度相等,故存在歐拉回路15432歐拉圖 7.4 歐拉圖與哈密頓圖 【定理2】 (2) 連通有向圖有歐拉通路、但無歐拉回路的充要條件是：除兩個結(jié)點外，其余結(jié)點的出度等于入度，在這兩個例外的結(jié)點中，一個結(jié)點的出度比入

10、度大1，另一個結(jié)點的出度比入度小1.有歐拉路無歐拉回路1543215432無歐拉路，更無歐拉回路。它不是歐拉圖 7.4 歐拉圖與哈密頓圖1e1e2e3e4e3e2e1e4e52e2e1e3e43 【問題】 判斷下列各圖是否存在歐拉路或歐拉回路或兩者都不是. 【答案】（1）歐拉回路。每個點的出度與入度相等.（2）歐拉通路.A點的出度比入度大1B點的出度比入度小1（3）沒有歐拉路.每個結(jié)點的出度與入度不相等.AB 7.4 歐拉圖與哈密頓圖 【例3】下圖（表示的是一個展覽館的平面圖館里各相鄰房間之間都有門（共16扇）一個參觀者來到展覽館門外，他想在參觀過程中，把館里所有的門都不重復(fù)地穿行一遍后出來，

11、這個想法能否實現(xiàn)？ 7.4 歐拉圖與哈密頓圖 【解】首先建立該問題的圖論模型將展覽館的5個房間和館外場地用6個結(jié)點表示，兩個結(jié)點之間的邊表示它們所在位置之間有一扇門，則得到下圖. 于是，判斷能否不重復(fù)地穿過展覽館的每扇門一次的問題就轉(zhuǎn)化為判別圖中是否存在歐拉路的問題由圖可以看出，圖中有4個奇度結(jié)點由定理1知，圖中不存在歐拉路，即參觀者的想法不能實現(xiàn) 7.4 歐拉圖與哈密頓圖 【練習(xí)1】利用Fluery(福勒里)算法或標(biāo)號法在默罕默德短彎刀（下圖）中找出一條歐拉回路. 7.4 歐拉圖與哈密頓圖二、歐拉圖及其應(yīng)用（1）歐拉路經(jīng)過圖中每條邊一次且僅一次并行遍圖中所有頂點的路（2）歐拉回路經(jīng)過圖中每條

12、邊一次且僅一次并行遍圖中所有頂點的回路（3）歐拉圖具有歐拉回路的圖。 7.4 歐拉圖與哈密頓圖ABCDE【思考】（1）下圖中存不存在從頂點A到B歐拉路？（3）下圖中存不存在歐拉回路？（2）下圖中還存不存在其他的歐拉路？二、歐拉圖及其應(yīng)用 7.4 歐拉圖與哈密頓圖半歐拉圖判定定理 一個無向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個奇度頂點。并且這兩個奇度結(jié)點，就是每條歐拉通路的端點。歐拉圖判定定理 一個無向圖G是歐拉圖當(dāng)且僅當(dāng)G連通且無奇頂點。 7.4 歐拉圖與哈密頓圖【案例1】下列各圖哪些是歐拉圖，哪些是半歐拉圖？e1e2e3e4e5e1e2e3e4e5e6歐拉圖半歐拉圖不是歐拉圖也不是半歐拉圖

13、e1e2e3e4e5 7.4 歐拉圖與哈密頓圖 【案例2】 街道比賽問題：甲、乙兩人分別處在圖G中的結(jié)點a,b處。甲提出同乙比賽：從它們所在結(jié)點出發(fā)，走過圖中所有邊最后到達結(jié)點c處。如果它們速度相同，問誰最先到達目的地？并分別找出它們的行走路線。 【解】圖中僅有兩個奇度結(jié)點（b和c），因而存在從b到c的歐拉通路，乙走到c只要走一條歐拉通路，即9條邊，而甲要想走完所有的邊到達c，至少要先走一條邊到達b，再走一條歐拉通路，因而要走10條邊才能到達c，所以乙必勝.c圖Ga(甲)b(乙) 7.4 歐拉圖與哈密頓圖 【案例3】 環(huán)衛(wèi)工人清掃街道，清掃路線如圖所示，是否存在清掃路線：使環(huán)衛(wèi)工人從A出發(fā)通過

14、所有路線而不重復(fù)且最后回到A。如果存在這樣的清掃路線，請找出一條具體路線。DACBEFGHIJKL1235478613121110914151617181920DACBEFGHIJKL先在每條邊標(biāo)上序號 7.4 歐拉圖與哈密頓圖 【案例3】 清掃路線的確定.DACBEFGHIJKL1235478613121110914151617181920 標(biāo)號法（歐拉路的尋找方法） 先將每條邊按順序標(biāo)上序號（1，2，3，），然后從某一點的某一邊開始，將其標(biāo)出的序號寫出，接著依次將相鄰的邊的序號寫出，全部邊的序號寫完后，得到的一串?dāng)?shù)字表示的路線就是一條歐拉回路。A,1,2,7,11,5,4,8,17,9,6

15、,10,18,13,14,15,16,20,19,12,3,就是歐拉回路，即為清掃路線. 7.4 歐拉圖與哈密頓圖 【案例3】 環(huán)衛(wèi)工人清掃街道，清掃路線如圖所示，是否存在清掃路線：使環(huán)衛(wèi)工人從A出發(fā)通過所有路線而不重復(fù)且最后回到A。如果存在這樣的清掃路線，請找出一條具體路線.DACBEFGHIJKL1235478613121110914151617181920 7.4 歐拉圖與哈密頓圖 【問題解答】 由于圖中每個結(jié)點度數(shù)均為偶數(shù)，故由歐拉定理可知清掃路線圖是一個歐拉圖，從而這樣的一條清掃路線是存在的. （1）判斷是否存在清掃路線（2）利用Fleury算法尋找歐拉回路.DACBEFGHIJKL

16、 7.4 歐拉圖與哈密頓圖 【練習(xí)】 如圖所示的街區(qū)，試問甲、乙二人以同樣的速度分別從A.B處同時出發(fā)走遍所有街道而誰先到達C處?每個人至少要走多少條邊？并說明道理。 【解】圖中僅有兩個奇度結(jié)點（B和C），因而存在從B到C的歐拉通路，乙走到C只要走一條歐拉通路，即13條邊，而甲要想走完所有的邊到達C，至少要先走一條邊到達B，再走一條歐拉通路，因而要走14條邊才能到達C ，所以乙必勝。（甲）（乙） 7.4 歐拉圖與哈密頓圖 【練習(xí)2】 如圖所示的街區(qū)，試問甲、乙二人以同樣的速度分別從A.B處同時出發(fā)走遍所有街道而誰先到達C處?每個人至少要走多少條邊？并說明道理。 7.4 歐拉圖與哈密頓圖 問1：

17、歐拉圖和半歐拉圖之間的區(qū)別？ 問2：將半歐拉圖的兩個奇頂點之間加一條線，是否變成歐拉圖？ 答：歐拉圖中無奇頂點，半歐拉圖中有且僅有兩個奇頂點。 答：將半歐拉圖中的兩個奇頂點之間連上一條線，新圖中無奇度頂點，故是歐拉圖。ABCDE 接下來我們將進一步探討歐拉圖與非歐拉圖之間的轉(zhuǎn)化問題。【問題解答】 7.4 歐拉圖與哈密頓圖 歐拉圖和半歐拉圖都具有很好的性質(zhì)，利用歐拉圖和半歐拉圖的性質(zhì)可以解決很多的現(xiàn)實問題。但是，也有許多現(xiàn)實問題可能是非（半）歐拉圖。 請看下面的案例。 7.4 歐拉圖與哈密頓圖起點終點 【案例4】 設(shè)計區(qū)間公交車路線 運輸管理部門在設(shè)計一個新的區(qū)間公交系統(tǒng)，來運送城市商業(yè)區(qū)的顧客

18、，具體地圖如圖所示，如果有可能，他們希望能夠設(shè)計這樣一個路線，它恰好通過區(qū)域的每一條道路，并且最終回到初始位置。如果不可能，他們希望盡量使重復(fù)走過的街道數(shù)減至最少。 7.4 歐拉圖與哈密頓圖 【問題解答】 我們將地圖模擬： 每一個十字路口表示成一個點，連接兩個十字路口的道路表示成邊。如下圖所示。 判定 圖中存在8個奇頂點，從而既不是歐拉圖，也不是半歐拉圖。 思考 能否把它轉(zhuǎn)化成歐拉圖？ 7.4 歐拉圖與哈密頓圖 為了使這幅圖稱為歐拉圖，我們必須把奇頂點轉(zhuǎn)化成偶頂點。 方法 重復(fù)一些邊，使奇頂點變成偶頂點。 注意：當(dāng)將非歐拉圖歐拉化時，僅能夠重復(fù)那些在圖中已經(jīng)存在的邊。 至此，我們已經(jīng)將一個非歐

19、拉圖歐拉化了，接下來要做的事情就是利用Fleury算法尋找歐拉回路。 7.4 歐拉圖與哈密頓圖 先將各條邊標(biāo)上序號，再將各邊上的序號按相鄰順序?qū)懗?，將所有邊的序號寫完好后就得到公交線路運行路線。12345697108111312141519171816212220ABCDFEDG2725262423 7.4 歐拉圖與哈密頓圖 【實訓(xùn)】 在下圖中加入一些邊使其成為歐拉圖。AJHIGFEDCB 7.4 歐拉圖與哈密頓圖 所謂哈密頓圖,起源于一種游戲,是英國數(shù)學(xué)家哈密頓(Hamilton)于1859年提出, 這種游戲叫周游世界游戲,用一個正十二面體的20個頂點代表20個大城市,(如左下圖)這個正十二

20、面體同構(gòu)于一個平面圖(如右下圖),要求沿著正十二面體的棱尋找一條旅行路線，通過每個城市恰好一次又回到出發(fā)城市。這便是Hamilton回路問題。 三、哈密頓圖轉(zhuǎn)化 7.4 歐拉圖與哈密頓圖 【定義2 】 經(jīng)過圖中每個結(jié)點一次且僅一次的通路（或回路），稱為哈密頓路（或哈密頓回路）。 具有哈密頓回路的圖稱為哈密頓圖。 具有哈密頓路，但沒有哈密頓回路的圖稱為半哈密頓圖 【思考】引例給出的圖是不是哈密頓圖？ 7.4 歐拉圖與哈密頓圖（1）（2）（3） 【答案】在圖（1）中，不存在哈密頓回路，故它不是哈密頓圖。但存存在哈密頓通路。在圖（2）中，存在哈密頓回路，故它是哈密頓圖。在圖（3）中，既無哈密頓回路，

21、也無哈密頓通路?！締栴}】下列圖中哪些是哈密頓圖？哪些不是？三、哈密頓圖 7.4 歐拉圖與哈密頓圖 【例1】（1）指出下列各圖是否哈密頓圖,有無哈密頓通路, 回路？ 【解】 (1) 容易判斷, 存在哈密頓回路, 故是哈密頓圖. (2) 只有哈密頓通路, 無哈密頓回路, 故不是哈密頓圖. (3) 不是連通圖，無哈密頓通路和哈密頓回路. 但有回路。(1)(2)(3) 7.4 歐拉圖與哈密頓圖 7.4 歐拉圖與哈密頓圖 【實訓(xùn)】下圖是否是哈密頓圖，若是請給出一條從點1出發(fā)的哈密頓回路。 【答案】從1出發(fā)的哈密頓回路是：1，17，18，19，20，10，11，12，13,14,15,16,3,4,5,6

22、,7,8,9.2,1.20 7.4 歐拉圖與哈密頓圖 # 例 畫出具有下列條件的有5個結(jié)點的無向連通圖 (1)不是哈密頓圖，也不是歐拉圖； (2) 有哈密頓回路，沒有歐拉回路； (3) 沒有哈密頓回路，有歐拉回路； (4) 是哈密頓圖，也是歐拉圖. 解 作圖如下(不唯一).(2)(3)(4)(1) 7.4 歐拉圖與哈密頓圖 【定理 3】 充分條件 【注意】這里只是充分條件。如果圖G不滿足條件，則圖G也有可能是哈密頓圖?，F(xiàn)在只能根據(jù)定義判斷一個圖是否是哈密頓圖，只在一些特殊情況下才有判別法。 (2)設(shè)圖G為n(n 3)階無向簡單圖，若G中任意兩個（不相鄰的）頂點u,v的度數(shù)之和大于等于n ，即

23、d(u)+d(v)n ，則G中存在哈密頓回路（即G為哈密頓圖）。 (1)設(shè)圖G 是 n (n3)階無向簡單圖，若G中任意兩個（不相鄰的）頂點 u，v的度數(shù)之和大于等于n-1，即 d(u)+d(v)n-1 ，則圖G中存在哈密頓通路.（n為所有頂點的個數(shù)） 7.4 歐拉圖與哈密頓圖 【定理 5】 在 n (n2)階有向圖 D=中，如果所有有向邊去掉方向后，所得無向圖中含生成子圖Kn ，則有向圖 D 中存在哈密頓通路. 【推論】 n(n 3)階有向完全圖G為哈密頓圖。 7.4 歐拉圖與哈密頓圖 【例5】 某次會議有20人參加，其中每人都至少有10個朋友這20個人圍一圓桌入席，要想使每個人相鄰的兩位都

24、是朋友是否可能？ 【解】 有可能 每個人用一個點表示，則20人用20個點表示。若二人是朋友，則在表示它們的點間連一條邊這樣可以構(gòu)成一個連通圖 將20人圍一圓桌入席，使每個人相鄰的兩位都是朋友即在圖中找哈密頓回路 根據(jù)已知條件，每人至少有10個朋友，也就是圖中每個結(jié)點的度數(shù)大于等于10，這樣任何兩個不相鄰的結(jié)點的度數(shù)之和大于或等于20(頂點的個數(shù)），由定理3知，圖是一個哈密頓圖，從而存在哈密頓回路 7.4 歐拉圖與哈密頓圖 【例 6】已知有關(guān)人員a, b, c, d, e, f, g 的有關(guān)信息。 a：說英語；b：說英語和西班牙語； c；說英語，意大利語和俄語； d：說日語和西班牙語 e：說德語

25、和意大利語； f：說法語、日語和俄語； g：說法語和德語. 試問：上述7人中是否任意兩人都能交談？ (可借助其余5人中組成的譯員鏈幫助) 7.4 歐拉圖與哈密頓圖abcdefg 【解】 設(shè)7個人為7個結(jié)點, 將兩個懂同一語言的人之間連一條邊(即他們能直接交談), 這樣就得到一個簡單圖G, 問題就轉(zhuǎn)化為G是否存在哈密頓回路. 如圖所示, 可出哈密頓回路。 哈密頓回路為acegfdba或abdfgeca, 按照這樣的回路安排座位后的7個人，它們中的任意兩個人都能交談.【例6】 已知條件a：說英語；b：說英語和西班牙語；C: 說英語,意大利語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法

26、語、日語和俄語；g：說法語和德語. 7.4 歐拉圖與哈密頓圖 如果題目改為：試問這7個人應(yīng)如何安排座位, 才能使每個人都能與他身邊的人交談？ 【解】用結(jié)點表示人，用邊表示連接的兩個人能說同一種語言，故能夠構(gòu)造出哈密頓圖（如右上圖所示）?！纠?】 已知條件a：說英語；b：說英語或西班牙語；c；說英語，意大利 語和俄語；d：說日語和西班牙語e：說德語和意大利語；f：說法語、日語和俄語；g：說法語和德語. abcdefg英英西日法德意 第五節(jié) 樹 7.5 樹二 根樹及其應(yīng)用 無向樹一 三關(guān)于Huffman編碼 7.5 樹 【引入】 請根據(jù)下圖回答如下問題： （1）無向圖G是不是連通圖？ （2）圖中存

27、不存在回路？G 7.5 樹 一、無向樹 【定義1】連通且無回路的無向圖稱為無向樹,簡稱樹,常用T表示樹.僅有一個結(jié)點的樹稱為平凡樹. 在樹中，度數(shù)等于1的頂點稱為樹葉，度數(shù)大于1的頂點稱為分支點. 【定義2】若無向圖G至少有兩個連通分支,且每個連通分支均為樹，則稱G為森林.（這表明，森林是至少由兩顆樹組成的無向圖） 7.5 樹V1V4V8V7V6V5V2V3樹T的結(jié)點是分支點，結(jié)點 是樹葉。 【例1】(1) 請判斷右圖是否是樹？如果是樹，請說明哪些結(jié)點是分支點，哪些結(jié)點是樹葉？【解】因為圖連通且無回路，所以是樹。 7.5 樹 【例1】(2) 判斷下列哪些圖是樹？v1v2v3v4v5(a)v1v

28、2v3v4v5(b)v1v2v4v3v5(c) 【解】圖(a)是樹, 因為它連通又不包含回路。圖(b), (c)不是樹, 因為圖(b)雖連通但有回路, 圖(c)雖無回路但不連通. 在圖(a)中, 頂點v1、 v4、 v5為均為樹葉，頂 點v2、 v3均為分支點. 7.5 樹 【定理 1】 設(shè)G=,則以下關(guān)于樹的定義是等價的：（1）G連通而不含回路（G是樹）.（2）G中每對頂點之間有且僅有一條路.（3）G中無回路且 m = n-1.（4）G是連通的且 m = n-1 . (5) G中沒有回路，但在任何兩個不同的頂點之間增加一條新 邊，則在所得的圖中得到唯一的一個含新邊的回路. (6) G是連通的

29、，且G中任何邊均為橋. 或 G是連通的,但刪除任何一條邊后，就不連通了. 其中n為G中頂點數(shù)，m為邊數(shù).樹的性質(zhì) 7.5 樹 以上兩個定理給出了無向樹的主要性質(zhì)，利用這些性質(zhì)和握手定理，可以畫出階數(shù)n比較小的所有非同構(gòu)的無向樹. 【定理2】設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉. 【證】 因為T是非平凡樹,所以T中每個頂點的度數(shù)都大于等于1, 設(shè)T有k片樹葉, 則有(n-k)個頂點度數(shù)大于等于2,由握手定理及定理1可知 2m =d(vi) k+2(n-k)， 由定理1可知：m = n-1,將此結(jié)果代入上式后，解得 k 2. 7.5 樹 【例2】 已知無向樹T中有1個3度頂點，2個2度頂

30、點，其余頂點全是樹葉，試求樹葉數(shù). 【解】 設(shè)有x片樹葉，于是樹T中所有的頂點數(shù)滿足 n = 1+2+x = 3+x, 由樹的性質(zhì)有， m = (n1)， 再由握手定理得 ： 2m =13+22+x .即 2(2+x) = 13+22+x . 解得 x = 3，故T有3片樹葉.(n = 6, m=5).【分析】本題利用樹的性質(zhì) m=n1和握手定理來求解. 7.5 樹 圖中，紅色邊表示生成樹，黑色邊組成余樹?？梢?，余樹可能不連通，也可能含回路. 【定義3】設(shè)T是無向圖G的生成子圖并且為樹，則稱T為G的生成樹. G在T中的邊稱為T的樹枝，G不在T中的邊稱為T的弦. T的所有弦的集合的導(dǎo)出子圖稱為T

31、的余樹. 【注意】余樹不一定是樹. 7.5 樹 【例3】指出圖（1）的生成樹和余樹. 【解】圖 (2)為(1)的一棵生成樹T，圖(3)為T的余樹. 一個無向連通圖，如果它本身不是樹，它的生成樹是不唯一的.但所有的連通圖都具有生成樹. 事實上，若G是連通圖，又G中無回路，則G本身就是樹.abcdeabcdeabcd(1)(2)(3)生成樹余樹 7.5 樹生成樹的求法：破圈法 在圖G中尋找回路，在此回路中去掉一條邊，如此做下去，直到恰好把所有的回路都破壞掉，圖G中剩余的邊就是生成樹. 【定理3】 無向圖G具有生成樹T G是連通圖.【推論1】 設(shè)G是n階m條邊的無向連通圖，則m n-1.【推論2】

32、設(shè)G是n階m條邊的無向連通圖，T為G的生成樹， 則T的余樹 中含有m-n+1邊(即 有m-n+1條弦). 7.5 樹【例5 】求下圖的一棵生成樹.G的生成樹G【答案】 7.5 樹 【定義3(2)】無向圖或有向圖的每一條邊e附加一個實數(shù)w(e), 稱作邊e的權(quán). 圖連同附加在邊上的權(quán)稱作帶權(quán)圖, 記作G=. 設(shè)無向連通帶權(quán)圖G=,T是G的一棵生成樹，T的所有邊的權(quán)的和稱為T的權(quán)，記作W(T). 帶權(quán)圖中權(quán)最小的生成樹稱為圖G的最小生成樹. 7.5 樹 最小生成樹的求法 方法一：選取權(quán)數(shù)最大的邊所在的回路，去掉其中權(quán)數(shù)最大的邊，如此做下去，直到求出生成樹為止。這樣求出的生成樹一定是最小生成樹. 方

33、法二：克魯斯特爾算法。先去掉所有的邊，然后從權(quán)數(shù)最小的邊的開始，從小到大逐步選取，如果所選取的邊和已選取的邊構(gòu)成了回路，則不選取這條邊而重新選取，直到連接完所有的結(jié)點.這樣求出的樹就是最小生成樹. 7.5 樹 【例6】 求右圖的最小生成樹。 分析：將各個回路中的最大邊刪去。 【解】選取含最大邊(c,d)的回路cdec，刪去其中權(quán)數(shù)最大的邊(c,d)，然后再選取含最大邊(a,b)的回路abea，刪去其中權(quán)數(shù)最大的邊(a,b)，再選取含最大邊(c,e)的回路bceb，刪去其中權(quán)數(shù)最大的邊(c,e)，再選取含最大邊(a,d)的回路adea，刪去其中權(quán)數(shù)最大的邊(a,d)，即得最小生成樹。 T=。 最

34、小生成樹的權(quán)為：W(T)=1+2+3+1=7. 7.5 樹 【解法二】 用克魯斯特爾算法做， 先去掉所有的邊。從最小邊(d,e)開始選取，再選取(d,a)，再選取(e,a)和(b,c)，但(e,a)構(gòu)成回路，所以應(yīng)去掉，再選取(c,a)，這時已連接了所有的結(jié)點，最小生成樹求出。T=。W=4+5+6+7=22. 7.5 樹 【例6】（2） 用避圈法求下圖所示的最小生成樹.abcdef5555136642 【解 】 W(T)=1+2+3+4+5=15. 【注意】最小生成樹的結(jié)點數(shù)與原圖的結(jié)點數(shù)相等，但邊的數(shù)目比原圖少. 7.5 樹bacd762fe81443472356321hg 【實訓(xùn)1】鋪設(shè)一

35、個連接七個城市的光纖通信網(wǎng)絡(luò)，預(yù)算費用如圖所示（單位：萬元）。請畫圖給出一個鋪設(shè)方案，并計算出所需最小費用是多少？ 7.5 樹febacd546036388404820452815383062251210hg 【實訓(xùn)1】鋪設(shè)一個連接七個城市的光纖通信網(wǎng)絡(luò)，預(yù)算費用如圖所示（單位：萬元）。請畫圖給出一個鋪設(shè)方案，并計算出所需最小費用是多少？ 7.5 樹2121343151131。OK! 【實訓(xùn)2】用Kruskal（克魯斯特爾）算法求下圖的最小生成樹. 7.5 樹。214515545332 【例10】用Kruskal算法求下圖的最小生成樹。214515545332W(T)=1+1+2+3+2+5

36、=14W(T)=1+1+2+3+2+5 =14 7.5 樹 前面我們討論的樹，都是一個無向圖，下面我們討論有向圖的樹。 【定義4】如果一個有向圖在不考慮邊的方向時是一棵樹，那么，這個有向圖稱為有向樹。（a）（b）二、根樹及其應(yīng)用 7.5 樹 【定義2】 一棵有向樹，如果恰有一個結(jié)點的入度為0，其余所有結(jié)點的入度都為1，則稱為根樹。入度為0的結(jié)點稱為樹根，出度為0的結(jié)點稱為樹葉，入度為1, 出度大于0的頂點稱為內(nèi)點，樹根與內(nèi)點的稱為分支點?！纠?】 判斷下圖是否是根樹？有向樹但不是根樹根樹如右圖所示 a是樹根 b,e,f,h,i是樹葉 c,d,g是內(nèi)點 a,c,d,g是分支點 a為0層;1層有b

37、,c; 2層有d,e,f; 3層有g(shù),h; 4層有i. 樹高為4 7.5 樹根樹的畫法：樹根放上方,省去所有有向邊上的箭頭。 結(jié)點V的層數(shù)：從樹根到v的通路長度 樹高：樹中結(jié)點的最大層數(shù) 7.5 樹 【實訓(xùn)3】指出下圖中的樹根、樹葉、內(nèi)點、分支點、各結(jié)點的層數(shù)及樹高。 【答案】右圖中結(jié)點v2, v3 , v4都在樹的第一層. 結(jié)點v5, v6 , v7 , v8 , v9都在樹的第二層. 結(jié)點v10, v11 , v12 都在樹的第三層. 此根樹的樹高為3.家族樹 【定義】 把根樹看作一棵家族樹: (1) 若頂點 a 鄰接到頂點 b, 則稱 b 是 a 的兒子, a 是 b 的父親; (2)

38、若b和c為同一個頂點的兒子, 則稱b和c是兄弟; (3) 若ab且a可達b, 則稱a是b的祖先, b是a的后代. 設(shè)v為根樹的一個頂點且不是樹根, 稱v及其所有后代的導(dǎo)出子圖為以v為根的根子樹. 7.5 樹 7.5 樹【定義6】(1) 如果將根樹的每一層的結(jié)點都規(guī)定次序，則根樹稱為有序樹 有序樹的次序可以排在頂點處，也可以排在邊上，次序常常是從左向右，不一定是連續(xù)的。122231221111C 由于在根樹數(shù)中有向邊的方向均一致（向下），故可省略掉方向。如上圖（b）可用圖（c）代替。 7.5 樹 【定義6】(2) 在根樹中，若每一個結(jié)點的出度小于等于m，則稱這棵樹為m元樹。當(dāng)m=2時稱為二元樹。

39、二元樹三元樹 7.5 樹 【例2】 M 和E兩人進行網(wǎng)球比賽，如果一人連勝兩盤或共勝三盤就獲勝，比賽結(jié)束。表示出比賽的各種可能情況。 【解】可以用根樹表示如下. 從根到樹葉的每條路表示一種情況。如路EMM表示E勝第一盤后，M連勝兩盤。 共有10片樹葉，所以共有10種比賽情況。如EE，EMEE，EMEME， 最優(yōu)2元樹 7.5 樹 【定義】 設(shè)2元樹T有t片樹葉v1, v2, , vt, 樹葉的權(quán)分別為w1, w2, , wt , 稱 為T的權(quán), 記作W(T), 其中l(wèi)(vi)是vi的層數(shù). 即在所有有t片樹葉, 帶權(quán)w1, w2, , wt 的 2元樹中, 權(quán)最小的2元樹稱為最優(yōu)2元樹. 7.

40、5 樹 如圖所示的2顆樹，都是帶權(quán)1,3,4,5,6的二元樹。1543615436 7.5 樹用此算法求上例的最優(yōu)二元樹：給定實數(shù)w1,w2, ,wt , 且w1 w2 wt ,（1）連接權(quán)為w1,w2的兩片樹葉, 得一個分支點其權(quán) 為w1+w2 。（2）在w1+w2 ,w3, ,wt中選出兩個最小的權(quán), 連接 它們對應(yīng)的頂點(不一定是樹葉), 得新分支點及 所帶的權(quán)。（3）重復(fù) ( 2 ), 直到形成t-1個分支點, t片樹葉為止。Huffman算法 一種求最優(yōu)二元樹的算法 W(T)等于所有分支點的權(quán)之和. 7.5 樹。437(1)【例3】 求帶權(quán) 3,4,5,6,12的最優(yōu)二元樹?！窘狻抗?/p>

41、分為四個步驟：6(2)347511654371118(4)3456711181230(3) 7.5 樹 【例4】 求帶權(quán)為1, 1, 2, 3, 4, 5的最優(yōu)樹. 【解】解題過程由下圖給出.W(T)=2+4+7+16+9 = 38 。 7.5 樹 最優(yōu)二叉樹在通信編碼中的應(yīng)用 【定義8】 設(shè)=12 n-1n為長為n的符號串, 稱其子串 1 , 12 , , 12 n-1分別為該符號串的長度為1,2, ， n-1的前綴. 設(shè)B=1 ,2 , ,m 為一個符號串集合，若對于任意的i , j B, i j, i , j 互不為前綴, 則稱B為前綴碼, 若符號串中i (i=1,2, , m)只出現(xiàn)0, 1兩個符號, 則稱B為二元前綴碼。 7.5 樹 試問：00, 01, 100, 1010, 1011, 11111， abc, cba, bca, b