第8章+圖論-8(樹)

1、1返回 結(jié)束第八章 圖論-28.2.1 樹的概念和基本性質(zhì)8.2.2 幾類常用樹根樹有序樹 最優(yōu)二叉樹8.2.3 生成樹2返回 結(jié)束 樹的術(shù)語起源于植物學(xué)和家譜學(xué)。早在1857年，英國數(shù)學(xué)Arthur Cayley(18211895)就發(fā)現(xiàn)了樹，當(dāng)時他正在試圖列舉形為CnH2n+2的化合物的同分異構(gòu)體。樹具有廣泛的應(yīng)用，特別在計算機科學(xué)與管理科學(xué)中。如用樹構(gòu)造存儲和傳輸數(shù)據(jù)的有效編碼，用樹構(gòu)造最便宜的電話線連接分布式計算機網(wǎng)絡(luò)，用樹模擬一系列決策完成的過程等。 3返回 結(jié)束v在圖論中： 1、連通的無環(huán)圖稱為樹樹。2、除根之外， 度1的頂點稱為葉子葉子，度1的頂點稱為分支分支點點或者內(nèi)點內(nèi)點。葉

2、子葉子分支點分支點根根4返回 結(jié)束3、多個樹稱為森林森林；4、孤立頂點叫做平凡樹平凡樹 。123456789101512131114平凡樹平凡樹5返回 結(jié)束v 定理定理 T=(V, E) 是結(jié)點數(shù)是結(jié)點數(shù) n=|V| 1 的樹，則下述命的樹，則下述命題等價：題等價：（1） T是無回路的連通圖；是無回路的連通圖；（2）T是連通的，且有是連通的，且有n 1條邊；條邊；（3）T有有n 1條邊，且條邊，且T中無回路；中無回路；（4）T的任意兩點間有且只有唯一的通路；的任意兩點間有且只有唯一的通路；（5）T中無回路，但若在中無回路，但若在T的任一對不相鄰的頂點之的任一對不相鄰的頂點之間增加一條邊，則構(gòu)成

3、間增加一條邊，則構(gòu)成T中的唯一回路。中的唯一回路。6返回 結(jié)束有向樹有向樹 一個弱連通有向圖，若去掉方向后得到一一個弱連通有向圖，若去掉方向后得到一棵樹，則稱此有向圖為一棵有向樹，記為棵樹，則稱此有向圖為一棵有向樹，記為T。根樹根樹 一棵有向樹一棵有向樹T，若其中有且僅有一個結(jié)點，若其中有且僅有一個結(jié)點v0的入度為的入度為0，其余結(jié)點的入度為，其余結(jié)點的入度為1，則稱，則稱T是一棵以是一棵以v0為根的根樹或為根的根樹或外向樹外向樹。其中出度為。其中出度為0的結(jié)點稱為的結(jié)點稱為有根樹的葉子。有根樹的葉子。把外向樹之定向反過來，得到的有向樹叫內(nèi)向樹內(nèi)向樹。 v0v07返回 結(jié)束v根樹通常畫成倒長的

4、；v一個 結(jié)點的子結(jié)點畫在它的v下一層，邊的方向省略；v“同輩兄弟”畫在同一層。8返回 結(jié)束樹的高度樹的高度 設(shè)有根樹設(shè)有根樹 T=( (V, A) )，v0為樹根。為樹根。u V的深度是從的深度是從v0 開始到達開始到達u的有向路的長度，的有向路的長度，T的高度是從的高度是從v0到到T的葉子的最長路的長度。的葉子的最長路的長度。根結(jié)點深度為根結(jié)點深度為0，稱為第，稱為第0層；層；深度同為深度同為i 的結(jié)點構(gòu)成樹的第的結(jié)點構(gòu)成樹的第i 層；層；具有最大深度的結(jié)點的深度稱為樹的深度具有最大深度的結(jié)點的深度稱為樹的深度（高度）。（高度）。9返回 結(jié)束AHGFEDCBL evel: 0L evel:

5、 1L evel: 2L evel: 310返回 結(jié)束定義定義 對有向樹對有向樹 T=(V, A)，若，若 u ,v V且且 A，則稱，則稱 u為為v的父親，的父親，v為為u的兒子。若從的兒子。若從u到到v存在有向道路，存在有向道路，則稱則稱u是是v的祖先，的祖先，v是是u的后代（子孫）的后代（子孫）有序樹有序樹 將各樹的每個結(jié)點的所有兒子按次序排列，將各樹的每個結(jié)點的所有兒子按次序排列，稱這樣的根樹為有序樹。稱這樣的根樹為有序樹。有序樹的每個結(jié)點的出度小于或等于有序樹的每個結(jié)點的出度小于或等于m時，稱為時，稱為m叉叉有序樹。有序樹。有序樹的每個結(jié)點的出度只為有序樹的每個結(jié)點的出度只為 0或或

6、 m 時，稱為時，稱為m叉叉正則有序樹。正則有序樹。11返回 結(jié)束v例 設(shè)有4個銀幣，已知其中3個一定是真的，真假的區(qū)別在于銀幣的重量，現(xiàn)用一天平設(shè)法找出假幣。解：用a、b、c、d分別表示銀幣，a:b表示在天平上作比較。a:ba:cc重c輕a:dd重全真d輕a:ca輕b重a:cb輕a重12返回 結(jié)束容易看出，上例中方法并不唯一。a,b:c,da:cd:cc輕a重a:c全真d:cb重d輕a輕c重a:ba:bb輕d重13返回 結(jié)束二叉樹二叉樹 除樹葉外，每個結(jié)點的最多有兩個子結(jié)點，分別稱為除樹葉外，每個結(jié)點的最多有兩個子結(jié)點，分別稱為左子結(jié)點和右子結(jié)點的根樹稱為二叉樹左子結(jié)點和右子結(jié)點的根樹稱為二

7、叉樹二叉樹的另外一個定義：二叉樹或者是空樹，或者有一個二叉樹的另外一個定義：二叉樹或者是空樹，或者有一個根結(jié)點和兩個分別稱為左右子樹的二叉樹構(gòu)成。根結(jié)點和兩個分別稱為左右子樹的二叉樹構(gòu)成。二叉樹的性質(zhì)二叉樹的性質(zhì)第第i 層的結(jié)點數(shù)最多為層的結(jié)點數(shù)最多為2i；深度為深度為k的二叉樹最多有的二叉樹最多有2k+1- -1個結(jié)點；個結(jié)點；記二叉樹出度為記二叉樹出度為2的結(jié)點數(shù)目為的結(jié)點數(shù)目為n2，葉子數(shù)目為，葉子數(shù)目為n0，則有：，則有： n0=n2+11)多元樹與二叉樹的對應(yīng)關(guān)系：以結(jié)點的最左兒子為對應(yīng)二叉樹中多元樹與二叉樹的對應(yīng)關(guān)系：以結(jié)點的最左兒子為對應(yīng)二叉樹中該結(jié)點的左兒子；以結(jié)點的右兄弟為對

8、應(yīng)二叉樹中該結(jié)點的右兒該結(jié)點的左兒子；以結(jié)點的右兄弟為對應(yīng)二叉樹中該結(jié)點的右兒子。子。14返回 結(jié)束滿二叉樹滿二叉樹 二叉樹的每個結(jié)點的出度或者是二叉樹的每個結(jié)點的出度或者是0或者是或者是2 。滿二叉樹也稱正則二叉樹。滿二叉樹也稱正則二叉樹完美二叉樹完美二叉樹 滿二叉樹且所有結(jié)點在同一層。滿二叉樹且所有結(jié)點在同一層。對完美二叉樹對完美二叉樹 的結(jié)點按從上到下，同層結(jié)點從左的結(jié)點按從上到下，同層結(jié)點從左到右的原則編號，得到結(jié)點從到右的原則編號，得到結(jié)點從12k+1- -1 的編號序列。的編號序列。得到上述結(jié)點編號的二叉樹稱為編號二叉樹。得到上述結(jié)點編號的二叉樹稱為編號二叉樹。完全二叉樹完全二叉樹

9、若設(shè)二叉樹的高度為若設(shè)二叉樹的高度為h，除第，除第 h 層層外，其它各層外，其它各層 (1h-1) 的結(jié)點數(shù)都達到最大的結(jié)點數(shù)都達到最大個數(shù)，第個數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點，這層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。就是完全二叉樹。 。15返回 結(jié)束高度為高度為k的完全二叉樹，其的完全二叉樹，其k- -1層以上結(jié)點構(gòu)成一棵高度層以上結(jié)點構(gòu)成一棵高度為為k- -1 的完美二叉樹。的完美二叉樹。完全二叉樹的葉結(jié)點或者在同一層或者完全二叉樹的葉結(jié)點或者在同一層或者 在相鄰的兩層。在相鄰的兩層。滿二叉樹完美二叉樹完全二叉樹16返回 結(jié)束定義定義設(shè)設(shè)T是有是有t片葉子的二叉樹，其中片葉子的

10、二叉樹，其中t片葉子分別帶有片葉子分別帶有非負實權(quán)非負實權(quán) ，則稱，則稱T為為加權(quán)二叉樹加權(quán)二叉樹。稱。稱W(T) 為二叉樹為二叉樹T的權(quán)，其中的權(quán)，其中hi為帶權(quán)為帶權(quán)wi的的樹葉樹葉vi的層數(shù)。在所有的帶權(quán)的層數(shù)。在所有的帶權(quán) 的二叉的二叉樹中，帶權(quán)最小的二叉樹稱為樹中，帶權(quán)最小的二叉樹稱為最優(yōu)二叉樹最優(yōu)二叉樹(哈夫曼哈夫曼樹樹 )twww,21t1iiihtwww,2117返回 結(jié)束v【例】給定4個葉子結(jié)點a，b，c和d，分別帶權(quán)7，5，2和4。構(gòu)造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權(quán)路徑長度分別為：(a) W(T)=7*2+5*2+2*2+4*2=36(b) W(T)= =

11、7*3+5*3+2*1+4*2=46(c) W(T)= =7*1+5*2+2*3+4*3=35其中(c)樹的W最小，它就是最優(yōu)二叉樹最優(yōu)二叉樹(哈夫曼哈夫曼樹樹 )。 18返回 結(jié)束vHuffmanHuffman樹樹Huffman 算法算法 給定給定t個非負實數(shù)，構(gòu)造以它們?yōu)槿~子帶權(quán)且具有最小個非負實數(shù)，構(gòu)造以它們?yōu)槿~子帶權(quán)且具有最小M(T) 的最優(yōu)二叉樹。的最優(yōu)二叉樹。i t；若若 i =1 結(jié)束；結(jié)束；將將 i 個非負實數(shù)權(quán)由小到大排列成序，以最小的兩個個非負實數(shù)權(quán)由小到大排列成序，以最小的兩個數(shù)作為左右兒子，構(gòu)造其父親結(jié)點，并以此左右兒子數(shù)作為左右兒子，構(gòu)造其父親結(jié)點，并以此左右兒子的權(quán)

12、值之和作為新構(gòu)造的父親結(jié)點的權(quán)值。在權(quán)序列的權(quán)值之和作為新構(gòu)造的父親結(jié)點的權(quán)值。在權(quán)序列中刪去此左右兒子對應(yīng)的權(quán)值，增加新構(gòu)造的父親結(jié)中刪去此左右兒子對應(yīng)的權(quán)值，增加新構(gòu)造的父親結(jié)點的權(quán)值。點的權(quán)值。 i i-1 ，轉(zhuǎn)轉(zhuǎn) (2)。19返回 結(jié)束v例：有例：有4個權(quán)值個權(quán)值7,5,2,4，試構(gòu)造一棵有，試構(gòu)造一棵有4個個葉子結(jié)點的哈夫曼樹。葉子結(jié)點的哈夫曼樹。20返回 結(jié)束Huffman樹樹 由由Huffman算法構(gòu)造的二叉樹稱算法構(gòu)造的二叉樹稱為相對于非負實數(shù)權(quán)為相對于非負實數(shù)權(quán) wi (i=1,2, t) 的的Huffman樹。樹。定理定理 Huffman樹是一棵相對于非負實數(shù)權(quán)樹是一棵相對

13、于非負實數(shù)權(quán) wi (i=1,2, t) 的最優(yōu)二叉樹。的最優(yōu)二叉樹。21返回 結(jié)束定義定義： 有一個序列的集合，如果在這個集合中。任何序列都不是另一個序列的前綴，則稱這個集合為前綴碼前綴碼。v例如，001是001011的前綴，集合000,001,01,10,11是前綴碼，而1,00,01,000,0001不是前綴碼。二元前綴碼二元前綴碼前綴碼前綴碼A= 1, 2, , m 中的中的 i 只由兩種符號（如只由兩種符號（如0、1）組成時，稱）組成時，稱A為一為一個二元個二元前綴碼。前綴碼。22返回 結(jié)束v對有序二叉樹的頂點編碼如下：(1)根不標碼；(2)兄弟有序，左為兄，標0，右為弟，標1；(3

14、)從根始到葉上的道路依次抄出各點之碼，寫在葉下方，稱該葉的前綴該葉的前綴；(4)全樹的葉從左到有把它們的前綴依次抄出，叫做該樹的前綴碼該樹的前綴碼，每個葉子的前綴后加逗號，最后一個葉子前綴后加句號。顯然有序二叉樹與前綴碼一一對應(yīng)。23返回 結(jié)束v例如，0000，0001，001，010，011，100，101，11這一前綴碼對應(yīng)的有序二叉樹如下圖所示：v001101010010101000000010010100111001011124返回 結(jié)束Huffman編碼編碼 以各個源碼符號在源碼電文中以各個源碼符號在源碼電文中出現(xiàn)的頻率為權(quán)值，構(gòu)造以源碼符號為葉子出現(xiàn)的頻率為權(quán)值，構(gòu)造以源碼符號為葉

15、子的的Huffman樹，得到關(guān)于源碼符號集的一個樹，得到關(guān)于源碼符號集的一個二叉前綴碼，稱為其二叉前綴碼，稱為其Huffman編碼。編碼。定理定理 Huffman編碼是關(guān)于該源碼符號集的最編碼是關(guān)于該源碼符號集的最短二叉前綴碼。短二叉前綴碼。證明證明 略略25返回 結(jié)束實現(xiàn)譯文長度最短的二叉前綴碼設(shè)計過程：實現(xiàn)譯文長度最短的二叉前綴碼設(shè)計過程：q字頻統(tǒng)計字頻統(tǒng)計q等概率假設(shè)等概率假設(shè)qHuffman樹構(gòu)造樹構(gòu)造qHuffman編碼方案確定編碼方案確定例例 設(shè)一段電文含有設(shè)一段電文含有x1,x2,x3,x4,x5,x6,x7共共7個符號，個符號，它們出現(xiàn)的頻率分別是：它們出現(xiàn)的頻率分別是：x1:

16、 35% x2: 20% x3: 15% x4:10 x5: 10% x6:5% x7:5%。試為這。試為這7個符個符號設(shè)計一套最短二叉前綴編碼方案。號設(shè)計一套最短二叉前綴編碼方案。26返回 結(jié)束27返回 結(jié)束Huffman樹的用途很廣：如果出現(xiàn)概率越大的分枝（條件語句）離根越近，那么所需執(zhí)行的判斷語句就越少，這樣便可提高程序的執(zhí)行效率；：根據(jù)文件中字符出現(xiàn)的頻率，建成一棵Huffman樹，出現(xiàn)次數(shù)越多的字符的Huffman編碼越短，這樣可以達到文件的壓縮。28返回 結(jié)束生成樹生成樹如果一棵樹T是圖G的子圖，則樹T稱為圖G的生成樹生成樹或支撐樹支撐樹；GE(T)稱為樹T的余樹余樹，記作：T；T

17、中的邊稱為圖G的弦弦，也是樹T的弦。1234567812345678余樹余樹弦弦29返回 結(jié)束定理定理 任何連通圖至少有一棵生成樹。任何連通圖至少有一棵生成樹。 證明略證明略定理定理 若連通圖G=(V,E)，n=|V|，則圖的生成生成樹樹有n1條邊。用歸納法易證明。30返回 結(jié)束 圖的平面性問題，除了它的理論意義外，有許多實際應(yīng)用。例如，單面印刷電路板和集成電路的布線問題。近年來，大規(guī)模集成電路的發(fā)展促進了圖的平面性的研究。 31返回 結(jié)束 可平面性可平面性 一個圖一個圖 G=(V,E) ，若能將其畫在平面上，若能將其畫在平面上，且任意兩條邊的交點只能是且任意兩條邊的交點只能是G的頂點，則稱的

18、頂點，則稱G可嵌入可嵌入平面，或稱平面，或稱G是可平面的。可平面圖在平面上的一個是可平面的?？善矫鎴D在平面上的一個嵌入稱為一個平面圖。嵌入稱為一個平面圖。樹是一類重要的平面圖。樹是一類重要的平面圖。應(yīng)用舉例：印刷電路版、集成電路設(shè)計。應(yīng)用舉例：印刷電路版、集成電路設(shè)計。(a)(b)(c)(a)是可平面圖，(b),(c) 是(a)的平面嵌入，是平面圖。32返回 結(jié)束 例例 K5 和和K3,3 是不可平面的。是不可平面的。K5K3,3K5K3,333返回 結(jié)束 區(qū)域區(qū)域 由平面圖的邊包圍而成，其中不含圖的由平面圖的邊包圍而成，其中不含圖的頂點。也稱為頂點。也稱為面面。包圍域。包圍域R的所有邊組成的

19、的所有邊組成的回路稱為該域的邊界，回路長度稱為該域的回路稱為該域的邊界，回路長度稱為該域的度，記為度，記為deg(R)。v2R1R2R0v1v3v4v5v6v7各域的邊界：各域的邊界：R0: v1 v2 v4 v5 v7 v7 v4 v3 v1R1: v1 v2 v4 v3 v1R2: v4 v5 v7 v4 v6 v4R3: v7 v7 例例deg(R0)=8, deg(R1)=4, deg(R2)=5, deg(R3)=1R334返回 結(jié)束 內(nèi)部面和外部面內(nèi)部面和外部面 由平面圖的邊包圍且無窮大的域稱為由平面圖的邊包圍且無窮大的域稱為外部面。（如上例的域外部面。（如上例的域R0為外部面）為

20、外部面）一個平面圖有且只有一個外部面。一個平面圖有且只有一個外部面。 曲面嵌入曲面嵌入 一個圖可嵌入平面當(dāng)且僅當(dāng)它可嵌入曲一個圖可嵌入平面當(dāng)且僅當(dāng)它可嵌入曲面。面。定理定理5-1-1 平面圖平面圖G的所有域的度之和等于其邊的所有域的度之和等于其邊數(shù)數(shù)m的的2倍，即：倍，即：1deg()2riiRm35返回 結(jié)束v顯然：可平面圖的子圖仍然是可平面圖；包含不可平面圖的圖是不可平面圖；v容易發(fā)現(xiàn)，平面圖G每增加1條邊，圖G總的邊數(shù)和面數(shù)都增加1。邊界面36返回 結(jié)束 定理定理 歐拉公式歐拉公式 （必要條件必要條件） 設(shè)平面連通圖設(shè)平面連通圖G有有n個頂點，個頂點，m條邊，條邊，d個域，則有個域，則有

21、 n- -m+d = 2。證明證明 對對m作歸納。作歸納。m=0, m=1時成立。假定對于時成立。假定對于m=k成立成立: nk-mk+dk = 2 。當(dāng)。當(dāng)m=k+1時，考慮刪除一條邊后仍然連通的時，考慮刪除一條邊后仍然連通的情況。情況。(1) 如果如果G有回路，則刪除回路上一條邊后的圖邊數(shù)減少一，面有回路，則刪除回路上一條邊后的圖邊數(shù)減少一，面數(shù)減少一，故公式對數(shù)減少一，故公式對G成立：成立：nk-(mk+1)+(dk+1) = 2. (2) G沒有回路，只有割邊，必有度數(shù)為一的結(jié)點，刪除相應(yīng)割沒有回路，只有割邊，必有度數(shù)為一的結(jié)點，刪除相應(yīng)割邊的一度頂點后，結(jié)點數(shù)和邊數(shù)分別減少一，面數(shù)不

22、變，邊的一度頂點后，結(jié)點數(shù)和邊數(shù)分別減少一，面數(shù)不變，故仍然有故仍然有 ( nk +1)-(mk+1)+dk = 2. 歐拉公式對非簡單圖仍然成立。歐拉公式對非簡單圖仍然成立。37返回 結(jié)束對于對于n個頂點，個頂點，m條棱，條棱，d個面的凸多面體，個面的凸多面體，n-m+d=2. 推論推論 設(shè)平面圖設(shè)平面圖G的連通分支數(shù)為的連通分支數(shù)為k，并有，并有n個個頂點，頂點，m條邊，條邊，d個域，則有個域，則有 n- -m+d = k+1。證明證明 對每個連通分支使用歐拉公式，注意它對每個連通分支使用歐拉公式，注意它們共同擁有一個無窮面。們共同擁有一個無窮面。定理 若圖G是簡單的平面圖，則圖G至少有一

23、個頂點的度小于小于6。38返回 結(jié)束 極大平面圖極大平面圖 設(shè)設(shè)G=(V,E)為簡單平面圖，為簡單平面圖，|V| 3，若對任意若對任意vi ,vj V，且，且 (vi ,vj) E，有，有G =(V, E (vi ,vj)為非平面圖，則稱為非平面圖，則稱G為一個極大為一個極大平面圖。平面圖?！皹O大性極大性”乃針對固定頂點數(shù)的圖的邊的數(shù)乃針對固定頂點數(shù)的圖的邊的數(shù)目而言。目而言。39返回 結(jié)束v極大平面圖的性質(zhì)極大平面圖的性質(zhì)極大平面圖是連通圖。極大平面圖是連通圖。極大平面圖的每個面都由極大平面圖的每個面都由3條邊組成。條邊組成。極大平面圖有極大平面圖有3d=2m（d為面數(shù)目，為面數(shù)目，m 為邊數(shù)目）。為邊數(shù)目）。 定理定理 設(shè)極大平面圖設(shè)極大平面圖G有有n個頂點，個頂點，m條邊，條邊，d個域，個域，則有則有m=3n- -6，d=2n- -4。證明證明 將將3d=2m代入歐拉公式。代入歐拉公式。 推論推論 簡單平面圖簡單平面圖G有有 m 3n- -6，d 2n- -4。 定理定理 簡單平面圖至少有一個頂點的度小于簡單平面圖至少有一個頂點的度小于6。 證明證明 設(shè)任一點的度設(shè)任一點的度 6，得，得 m 3n，矛盾。，矛盾。40返回 結(jié)束 例例 K3,3K5K3,3K5 是不可平面的。是不可平面的。證明證明 如果如果G是平面圖，是平面圖，則有則有