第十章樹(shù)與有序樹(shù)ppt課件

1、第十章 樹(shù)與有序樹(shù)10.1 樹(shù)的根本概念樹(shù)的根本概念10.2 連通圖的生成樹(shù)和帶權(quán)連通圖的連通圖的生成樹(shù)和帶權(quán)連通圖的最小生成樹(shù)最小生成樹(shù) 10.3 有序樹(shù)有序樹(shù)10.4 前綴碼和最優(yōu)二分樹(shù)前綴碼和最優(yōu)二分樹(shù) 例例 PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory樹(shù)的定義樹(shù)的定義 一個(gè)無(wú)向圖假設(shè)連通且不含圈，那么稱(chēng)它為一棵樹(shù)一個(gè)無(wú)向圖假設(shè)連通且不含圈，那么稱(chēng)它為一棵樹(shù)，記為，記為 T=(V,E)。 設(shè)設(shè)T是一棵樹(shù)，是一棵樹(shù)， T中度數(shù)為中度數(shù)為1的頂點(diǎn)稱(chēng)為樹(shù)葉，度數(shù)的頂點(diǎn)稱(chēng)為樹(shù)葉，度數(shù)大于大于1的頂點(diǎn)稱(chēng)為分枝點(diǎn)。的頂點(diǎn)稱(chēng)為

2、分枝點(diǎn)。例例 能否為樹(shù)能否為樹(shù)?例例1 畫(huà)出一切畫(huà)出一切5個(gè)頂點(diǎn)的樹(shù)個(gè)頂點(diǎn)的樹(shù)定理定理1 設(shè)設(shè) T=(V,E)是一棵樹(shù)，那么有是一棵樹(shù)，那么有 |E|=|V|-1。分析：對(duì)頂點(diǎn)數(shù)分析：對(duì)頂點(diǎn)數(shù)|V|進(jìn)展歸納法證明。進(jìn)展歸納法證明。當(dāng)當(dāng)|V|=1和和|V|=2時(shí)，定理顯然是成立的。時(shí)，定理顯然是成立的。歸納假設(shè)當(dāng)歸納假設(shè)當(dāng)|V|k時(shí)，定理成立。時(shí)，定理成立。 調(diào)查調(diào)查|V|=k+1時(shí)的情況。時(shí)的情況。 由于樹(shù)無(wú)圈，所以從由于樹(shù)無(wú)圈，所以從T中去掉任何一條邊，中去掉任何一條邊，都會(huì)使都會(huì)使T變成具有兩個(gè)連通分支的不連通圖。變成具有兩個(gè)連通分支的不連通圖。這兩個(gè)連通分支也必然是樹(shù)，譬如說(shuō)是這兩個(gè)連通

3、分支也必然是樹(shù)，譬如說(shuō)是T1=(V1,E1)和和T2=(V2,E2)。 顯然，顯然，|V1| k, |V2| k。根據(jù)歸納假設(shè)，有。根據(jù)歸納假設(shè)，有 |E1|=|V1|-1, |E2|=|V2|-1。而。而|V|=|V1|+|V2|, |E|=|E1|+|E2|+1, 所以所以|E|=|V|-1, 即定理得證。即定理得證。定理定理1的證明的證明證明：用對(duì)頂點(diǎn)集證明：用對(duì)頂點(diǎn)集V的元素個(gè)數(shù)歸納法來(lái)證。的元素個(gè)數(shù)歸納法來(lái)證。當(dāng)當(dāng)|V|=1時(shí)，時(shí)，T是一個(gè)僅有一個(gè)頂點(diǎn)且沒(méi)有邊的圖。顯是一個(gè)僅有一個(gè)頂點(diǎn)且沒(méi)有邊的圖。顯然，然，|E|=0， 命題成立。命題成立。歸納假設(shè)假設(shè)歸納假設(shè)假設(shè)|V|k時(shí)，命題成

4、立。調(diào)查時(shí)，命題成立。調(diào)查|V|=k+1時(shí)的時(shí)的情況。設(shè)情況。設(shè)u,v E ，我們擦去邊，我們擦去邊e, 得得T的一個(gè)子圖。的一個(gè)子圖。令令 V1=v V子圖中存在子圖中存在u到到v的通路的通路， V2=v V子圖中存在子圖中存在v到到v的通路的通路。 例例定理定理1的證明的證明(續(xù)續(xù))l 新圖分為兩個(gè)連通的子圖新圖分為兩個(gè)連通的子圖. 由于對(duì)于恣意的由于對(duì)于恣意的v V，原圖是連，原圖是連通的，所以在原圖中存在通的，所以在原圖中存在 v到到u的通路，也存在的通路，也存在v到到v的通路的通路，且都是初等通路。假設(shè)這兩條通路都經(jīng)過(guò)邊，且都是初等通路。假設(shè)這兩條通路都經(jīng)過(guò)邊e，那么原圖，那么原圖中

5、一定有圈，故中一定有圈，故V=V1V2 。假設(shè)存在。假設(shè)存在v V1V2，那么原圖，那么原圖中存在中存在 v到到u、v到到v的兩條不經(jīng)過(guò)邊的兩條不經(jīng)過(guò)邊e的初等通路，加上邊的初等通路，加上邊e后后, 原圖中一定有圈，故原圖中一定有圈，故V1V2 =。l 新圖分為兩棵不相交的樹(shù)新圖分為兩棵不相交的樹(shù). 原圖無(wú)圈，子圖也不會(huì)有圈，即原圖無(wú)圈，子圖也不會(huì)有圈，即為兩棵不相交的樹(shù)為兩棵不相交的樹(shù)(頂點(diǎn)的交集為空集頂點(diǎn)的交集為空集)。l 設(shè)設(shè)T1=(V1,E1)，T2=(V2,E2)，由歸納假定有，由歸納假定有l(wèi) |V1|-1=|E1|，|V2|-1=|E2|。l 又又|V|=|V1|+|V2|，|E|

6、=|E1|+|E2|+1。所以有定理得證。所以有定理得證。定理定理1的推論的推論任何一棵至少含有兩個(gè)頂點(diǎn)的樹(shù)至少有兩片樹(shù)葉。任何一棵至少含有兩個(gè)頂點(diǎn)的樹(shù)至少有兩片樹(shù)葉。證明：設(shè)證明：設(shè) T=(V,E)是一棵樹(shù)，假設(shè)是一棵樹(shù)，假設(shè)T中最多只需一片樹(shù)中最多只需一片樹(shù)葉，那么有葉，那么有d(v) 1+2(|V|-1)=2|E|+1, 這與結(jié)論這與結(jié)論 d(v) =2|E| 矛盾矛盾! 矛盾闡明矛盾闡明 T 不止一片樹(shù)葉。不止一片樹(shù)葉。v Vv V例例 設(shè)設(shè)T為樹(shù)，最大度為樹(shù)，最大度k，這里，這里k1，證明證明T至少有至少有k片樹(shù)葉。片樹(shù)葉。 證明：假設(shè)T有s片樹(shù)葉，sk。 記T的頂點(diǎn)數(shù)為n，那么 T

7、有1個(gè)度頂點(diǎn)，有s片樹(shù)葉， 還有(n-s-1)個(gè)不少于2度的頂點(diǎn)。 由握手定理可知： 2(n-1) 2(n-s-1)+k+s 可以解出 sk，這與假設(shè)sk矛盾。例2知一棵樹(shù)有知一棵樹(shù)有5個(gè)個(gè)4度頂點(diǎn)，度頂點(diǎn)，3個(gè)個(gè)3度頂點(diǎn)，度頂點(diǎn)，3個(gè)個(gè)2度頂點(diǎn)，問(wèn)有幾個(gè)一度頂點(diǎn)？度頂點(diǎn)，問(wèn)有幾個(gè)一度頂點(diǎn)？解：設(shè)有解：設(shè)有 x個(gè)個(gè)1度頂點(diǎn)，那么依題意有方程：度頂點(diǎn)，那么依題意有方程：54+33+32+1x = d(v) =2|E| =2(|V|-1) =2(5+3+3+ x1) x=15定理2T=(V,E)是一個(gè)簡(jiǎn)單圖，以下三條等價(jià)。是一個(gè)簡(jiǎn)單圖，以下三條等價(jià)。 T是一棵樹(shù)。是一棵樹(shù)。 T連通連通, 且且 |

8、V| 1=|E|。 T中無(wú)圈中無(wú)圈, 且且 |V| 1=|E|。證明：由證明：由 推出，由推出，由 推出推出 ，再由，再由 推出推出 ，以完成整個(gè)定理的證明。以完成整個(gè)定理的證明。 T是一棵樹(shù)，即是一棵樹(shù)，即T連通且無(wú)圈，連通且無(wú)圈， 由定理由定理1知，有知，有 |V|1 = |E| 。定理2的證明 知知T連通且連通且 |V|1=|E| 。假設(shè)。假設(shè) T中有圈，拿去圈中的中有圈，拿去圈中的一條邊，一條邊， T仍連通。我們繼續(xù)這樣的任務(wù)，直到仍連通。我們繼續(xù)這樣的任務(wù)，直到 T中中無(wú)圈。由于頂點(diǎn)與邊都是有限集，上面的任務(wù)一定可無(wú)圈。由于頂點(diǎn)與邊都是有限集，上面的任務(wù)一定可以在有限步內(nèi)終止。以在有

9、限步內(nèi)終止。設(shè)設(shè)T中共拿走中共拿走L條邊，由于每次拿去的邊都是圈中的邊條邊，由于每次拿去的邊都是圈中的邊，不影響，不影響 T的連通性，所以剩下的子圖的連通性，所以剩下的子圖T是連通且無(wú)是連通且無(wú)圈的圖，即圈的圖，即T是一棵樹(shù)。由定理是一棵樹(shù)。由定理1知，知， |V|1=|E|，其中其中V，E分別是分別是T的頂點(diǎn)和邊集。由的頂點(diǎn)和邊集。由T的產(chǎn)生方法，的產(chǎn)生方法，有有|V|=|V|，|E|=|E| L。所以。所以|V|1 =|E|L。由。由于于|V|1=|E|，所以，所以 |E|=|E|L，即，即L=0，原圖無(wú)圈。，原圖無(wú)圈。定理2的證明 知知T中無(wú)圈且中無(wú)圈且|V|1=|E|。假設(shè)假設(shè)T不連通

10、，設(shè)不連通，設(shè) T有有 k個(gè)連通分枝：個(gè)連通分枝： T1，T2，Tk，Ti=(Vi, Ei ), 1ik。對(duì)于每一個(gè)。對(duì)于每一個(gè)i (1ik), Ti是連通的且無(wú)圈，故是連通的且無(wú)圈，故Ti是樹(shù)。由定理是樹(shù)。由定理1知，知， |Vi|1=|Ei|，1ik。又又 所以所以|V|k=|E|，而知，而知|V|1=|E|，即有即有|V|k=|V|1，故，故 k=1，即，即T是連通圖。是連通圖。|Vi|=|V|， |Ei|=|E|i=1ni=1n例 設(shè)G為n階無(wú)向簡(jiǎn)單連通圖，n5， 證明G或G的補(bǔ)圖不是樹(shù)。 證明： 假設(shè)G或G的補(bǔ)圖都是樹(shù)，那么 它們的邊數(shù)都是 n-1。 于是 (n-1)+(n-1)=n

11、(n-1)/2 可以解出n=4，與知條件矛盾。 例例 畫(huà)出具有畫(huà)出具有7個(gè)頂點(diǎn)的一切非同構(gòu)的樹(shù)個(gè)頂點(diǎn)的一切非同構(gòu)的樹(shù)解：所畫(huà)出的樹(shù)有解：所畫(huà)出的樹(shù)有6條邊，因此條邊，因此7個(gè)頂點(diǎn)的度數(shù)之和應(yīng)為個(gè)頂點(diǎn)的度數(shù)之和應(yīng)為12。由于每個(gè)頂點(diǎn)的度數(shù)均大于等于。由于每個(gè)頂點(diǎn)的度數(shù)均大于等于1，因此可以，因此可以產(chǎn)生一下產(chǎn)生一下7種度數(shù)序列：種度數(shù)序列： 1 1 1 1 1 1 6, 產(chǎn)生產(chǎn)生1棵非同構(gòu)的樹(shù)棵非同構(gòu)的樹(shù)T1 1 1 1 1 1 2 5, 產(chǎn)生產(chǎn)生1棵非同構(gòu)的樹(shù)棵非同構(gòu)的樹(shù)T2 1 1 1 1 1 3 4, 產(chǎn)生產(chǎn)生1棵非同構(gòu)的樹(shù)棵非同構(gòu)的樹(shù)T3 1 1 1 1 2 2 4, 產(chǎn)生產(chǎn)生2棵非同構(gòu)的樹(shù)棵非同構(gòu)的樹(shù)T4、T5 1 1 1 1 2 3 3, 產(chǎn)生產(chǎn)生2棵非同構(gòu)的樹(shù)棵非同構(gòu)的樹(shù)T6、T7 1 1 1 2 2 2 3, 產(chǎn)生產(chǎn)生3棵非同構(gòu)的樹(shù)棵非同構(gòu)的樹(shù)T8、T9、T10 1 1 2 2 2 2 2, 產(chǎn)生產(chǎn)生1棵非同構(gòu)的樹(shù)棵非同構(gòu)的樹(shù)T11T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 例 7階無(wú)向圖有3片樹(shù)葉和1個(gè)3度頂點(diǎn)，其他3個(gè)頂點(diǎn)的度數(shù)均無(wú)1和3.試畫(huà)出滿(mǎn)足要求的一切非同構(gòu)的無(wú)向樹(shù)。解： 頂點(diǎn)數(shù)為7