離散數(shù)學圖論樹

離散數(shù)學圖論樹第一頁，共四十三頁，編輯于2023年，星期一8.2

樹樹的術(shù)語起源于植物學和家譜學。早在1857年，英國數(shù)學ArthurCayley(1821—1895)就發(fā)現(xiàn)了樹，當時他正在試圖列舉形為CnH2n+2的化合物的同分異構(gòu)體。樹具有廣泛的應用，特別在計算機科學與管理科學中。如用樹構(gòu)造存儲和傳輸數(shù)據(jù)的有效編碼，用樹構(gòu)造最便宜的電話線連接分布式計算機網(wǎng)絡，用樹模擬一系列決策完成的過程等。第二頁，共四十三頁，編輯于2023年，星期一8.2.1樹的概念和基本性質(zhì)在圖論中：

1、連通的無環(huán)圖稱為樹。2、除根之外，度＝1的頂點稱為葉子，度＞1的頂點稱為分支點或者內(nèi)點。葉子分支點根第三頁，共四十三頁，編輯于2023年，星期一8.2.1樹的概念和基本性質(zhì)3、多個樹稱為森林；4、孤立頂點叫做平凡樹。123456789101512131114平凡樹第四頁，共四十三頁，編輯于2023年，星期一8.2.1樹的概念和基本性質(zhì)

[定理]T=(V,E)是結(jié)點數(shù)n=|V|1的樹，則下述命題等價：（1）T是無回路的連通圖；（2）T是連通的，且有n1條邊；（3）T有n1條邊，且T中無回路；（4）T的任意兩點間有且只有唯一的通路；（5）T中無回路，但若在T的任一對不相鄰的頂點之間增加一條邊，則構(gòu)成T中的唯一回路。第五頁，共四十三頁，編輯于2023年，星期一根樹8.2.2幾類常用樹[有向樹]

一個弱連通有向圖，若去掉方向后得到一棵樹，則稱此有向圖為一棵有向樹，記為T。[根樹]

一棵有向樹T，若其中有且僅有一個結(jié)點v0的入度為0，其余結(jié)點的入度為1，則稱T是一棵以v0為根的根樹或外向樹。其中出度為0的結(jié)點稱為有根樹的葉子。把外向樹之定向反過來，得到的有向樹叫內(nèi)向樹。

v0v0第六頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹根樹通常畫成倒長的；一個結(jié)點的子結(jié)點畫在它的下一層，邊的方向省略；“同輩兄弟”畫在同一層。第七頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹[樹的高度]

設有根樹T=(V,A)，v0為樹根。u

V的深度是從v0

開始到達u的有向路的長度，T的高度是從v0到T的葉子的最長路的長度。根結(jié)點深度為0，稱為第0層；深度同為i的結(jié)點構(gòu)成樹的第i層；具有最大深度的結(jié)點的深度稱為樹的深度（高度）。第八頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹TreeNodeLevelandPathLength第九頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹有序樹[定義]

對有向樹T=(V,A)，若u,vV且<u,v>A，則稱u為v的父親，v為u的兒子。若從u到v存在有向道路，則稱u是v的祖先，v是u的后代（子孫）[有序樹]

將各樹的每個結(jié)點的所有兒子按次序排列，稱這樣的根樹為有序樹。有序樹的每個結(jié)點的出度小于或等于m時，稱為m叉有序樹。有序樹的每個結(jié)點的出度只為0或m

時，稱為m叉正則有序樹。第十頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹例設有4個銀幣，已知其中3個一定是真的，真假的區(qū)別在于銀幣的重量，現(xiàn)用一天平設法找出假幣。解：用a、b、c、d分別表示銀幣，a:b表示在天平上作比較。a:b＜＞＝a:cc重c輕＜＞＝a:dd重全真d輕＜＞＝a:ca輕b重＜＝a:cb輕a重＞＝第十一頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹容易看出，上例中方法并不唯一。a,b:c,d＜＞＝a:c＜＞＝d:cc輕a重＞＝a:c＝＜全真d:cb重d輕＜＞＝a輕c重＜＝a:b＝a:bb輕d重＜第十二頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹三、最優(yōu)二叉樹[二叉樹]

除樹葉外，每個結(jié)點的最多有兩個子結(jié)點，分別稱為左子結(jié)點和右子結(jié)點的根樹稱為二叉樹二叉樹的另外一個定義：二叉樹或者是空樹，或者有一個根結(jié)點和兩個分別稱為左右子樹的二叉樹構(gòu)成。[二叉樹的性質(zhì)]第i層的結(jié)點數(shù)最多為2i；深度為k的二叉樹最多有2k+1-1個結(jié)點；記二叉樹出度為2的結(jié)點數(shù)目為n2，葉子數(shù)目為n0，則有：n0=n2+1多元樹與二叉樹的對應關系：以結(jié)點的最左兒子為對應二叉樹中該結(jié)點的左兒子；以結(jié)點的右兄弟為對應二叉樹中該結(jié)點的右兒子。第十三頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹[滿二叉樹]

二叉樹的每個結(jié)點的出度或者是0或者是2。滿二叉樹也稱正則二叉樹[完美二叉樹]

滿二叉樹且所有結(jié)點在同一層。對完美二叉樹的結(jié)點按從上到下，同層結(jié)點從左到右的原則編號，得到結(jié)點從1~2k+1-1的編號序列。得到上述結(jié)點編號的二叉樹稱為編號二叉樹。[完全二叉樹]若設二叉樹的高度為h，除第h層外，其它各層(1～h-1)的結(jié)點數(shù)都達到最大個數(shù)，第h層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。

。第十四頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹高度為k的完全二叉樹，其k-1層以上結(jié)點構(gòu)成一棵高度為k-1的完美二叉樹。完全二叉樹的葉結(jié)點或者在同一層或者在相鄰的兩層。1671213141511109584231211109876543211671415958423滿二叉樹完美二叉樹完全二叉樹第十五頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹三、最優(yōu)二叉樹[定義]設T是有t片葉子的二叉樹，其中t片葉子分別帶有非負實權(quán)，則稱T為加權(quán)二叉樹。稱W(T)＝為二叉樹T的權(quán)，其中hi為帶權(quán)wi的樹葉vi的層數(shù)。在所有的帶權(quán)的二叉樹中，帶權(quán)最小的二叉樹稱為最優(yōu)二叉樹(哈夫曼樹)第十六頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹【例】給定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)==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)二叉樹(哈夫曼樹)。第十七頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹Huffman樹[Huffman算法]

給定t個非負實數(shù)，構(gòu)造以它們?yōu)槿~子帶權(quán)且具有最小M(T)的最優(yōu)二叉樹。it；若i=1結(jié)束；將i個非負實數(shù)權(quán)由小到大排列成序，以最小的兩個數(shù)作為左右兒子，構(gòu)造其父親結(jié)點，并以此左右兒子的權(quán)值之和作為新構(gòu)造的父親結(jié)點的權(quán)值。在權(quán)序列中刪去此左右兒子對應的權(quán)值，增加新構(gòu)造的父親結(jié)點的權(quán)值。

i

i-1，轉(zhuǎn)(2)。第十八頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹例：有4個權(quán)值{7,5,2,4}，試構(gòu)造一棵有4個葉子結(jié)點的哈夫曼樹。第十九頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹[Huffman樹]

由Huffman算法構(gòu)造的二叉樹稱為相對于非負實數(shù)權(quán)wi(i=1,2,…,t)的Huffman樹。[定理]Huffman樹是一棵相對于非負實數(shù)權(quán)wi(i=1,2,…,t)的最優(yōu)二叉樹。第二十頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹定義：有一個序列的集合，如果在這個集合中。任何序列都不是另一個序列的前綴，則稱這個集合為前綴碼。例如，001是001011的前綴，集合{000,001,01,10,11}是前綴碼，而{1,00,01,000,0001}不是前綴碼。[二元前綴碼]前綴碼A={1,2,…,m

}中的i只由兩種符號（如0、1）組成時，稱A為一個二元前綴碼。第二十一頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹對有序二叉樹的頂點編碼如下：(1)根不標碼；(2)兄弟有序，左為兄，標0，右為弟，標1；(3)從根始到葉上的道路依次抄出各點之碼，寫在葉下方，稱該葉的前綴；(4)全樹的葉從左到有把它們的前綴依次抄出，叫做該樹的前綴碼，每個葉子的前綴后加逗號，最后一個葉子前綴后加句號。顯然有序二叉樹與前綴碼一一對應。第二十二頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹例如，0000，0001，001，010，011，100，101，11這一前綴碼對應的有序二叉樹如下圖所示：v0011010100101010000000100101001110010111第二十三頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹[Huffman編碼]

以各個源碼符號在源碼電文中出現(xiàn)的頻率為權(quán)值，構(gòu)造以源碼符號為葉子的Huffman樹，得到關于源碼符號集的一個二叉前綴碼，稱為其Huffman編碼。[定理]Huffman編碼是關于該源碼符號集的最短二叉前綴碼。[證明]

略第二十四頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹實現(xiàn)譯文長度最短的二叉前綴碼設計過程：字頻統(tǒng)計等概率假設Huffman樹構(gòu)造Huffman編碼方案確定[例]

設一段電文含有x1,x2,x3,x4,x5,x6,x7共7個符號，它們出現(xiàn)的頻率分別是：x1:35%x2:20%x3:15%x4:10x5:10%x6:5%x7:5%。試為這7個符號設計一套最短二叉前綴編碼方案。第二十五頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹例第二十六頁，共四十三頁，編輯于2023年，星期一8.2.2幾類常用樹Huffman樹的用途很廣：分支程序的判斷流程：如果出現(xiàn)概率越大的分枝（條件語句）離根越近，那么所需執(zhí)行的判斷語句就越少，這樣便可提高程序的執(zhí)行效率；文件的壓縮：根據(jù)文件中字符出現(xiàn)的頻率，建成一棵Huffman樹，出現(xiàn)次數(shù)越多的字符的Huffman編碼越短，這樣可以達到文件的壓縮。第二十七頁，共四十三頁，編輯于2023年，星期一8.2.3生成樹[生成樹]如果一棵樹T是圖G的子圖，則樹T稱為圖G的生成樹或支撐樹；G－E(T)稱為樹T的余樹，記作：T’；T’中的邊稱為圖G的弦，也是樹T的弦。1234567812345678余樹弦第二十八頁，共四十三頁，編輯于2023年，星期一8.2.3生成樹[定理]

任何連通圖至少有一棵生成樹。證明略[定理]

若連通圖G=(V,E)，n=|V|，則圖的生成樹有n－1條邊。用歸納法易證明。第二十九頁，共四十三頁，編輯于2023年，星期一8.3平面圖

圖的平面性問題，除了它的理論意義外，有許多實際應用。例如，單面印刷電路板和集成電路的布線問題。近年來，大規(guī)模集成電路的發(fā)展促進了圖的平面性的研究。第三十頁，共四十三頁，編輯于2023年，星期一8.3.1平面圖的定義

[可平面性]一個圖G=(V,E)，若能將其畫在平面上，且任意兩條邊的交點只能是G的頂點，則稱G可嵌入平面，或稱G是可平面的?？善矫鎴D在平面上的一個嵌入稱為一個平面圖。樹是一類重要的平面圖。應用舉例：印刷電路版、集成電路設計。(a)(b)(c)(a)是可平面圖，(b),(c)是(a)的平面嵌入，是平面圖。第三十一頁，共四十三頁，編輯于2023年，星期一8.3.1平面圖的定義[例]K5和K3,3是不可平面的。K5K3,3K5K3,3第三十二頁，共四十三頁，編輯于2023年，星期一8.3.1平面圖的定義[區(qū)域]

由平面圖的邊包圍而成，其中不含圖的頂點。也稱為面。包圍域R的所有邊組成的回路稱為該域的邊界，回路長度稱為該域的度，記為deg(R)。v2R1R2R0v1v3v4v5v6v7各域的邊界：R0:v1v2v4v5v7v7v4v3v1R1:v1v2v4v3v1R2:v4v5v7v4v6v4R3:v7v7[例]deg(R0)=8,deg(R1)=4,deg(R2)=5,deg(R3)=1R3第三十三頁，共四十三頁，編輯于2023年，星期一8.3.1平面圖的定義[內(nèi)部面和外部面]由平面圖的邊包圍且無窮大的域稱為外部面。（如上例的域R0為外部面）一個平面圖有且只有一個外部面。[曲面嵌入]一個圖可嵌入平面當且僅當它可嵌入曲面。[定理5-1-1]平面圖G的所有域的度之和等于其邊數(shù)m的2倍，即：第三十四頁，共四十三頁，編輯于2023年，星期一8.3.1平面圖的定義顯然：可平面圖的子圖仍然是可平面圖；包含不可平面圖的圖是不可平面圖；容易發(fā)現(xiàn)，平面圖G每增加1條邊，圖G總的邊數(shù)和面數(shù)都增加1。邊界面第三十五頁，共四十三頁，編輯于2023年，星期一8.3.2歐拉公式

[定理歐拉公式]

（必要條件）

設平面連通圖G有n個頂點，m條邊，d個域，則有n-m+d=2。[證明]對m作歸納。m=0,m=1時成立。假定對于m=k成立:nk-mk+dk=2。當m=k+1時，考慮刪除一條邊后仍然連通的情況。(1)如果G有回路，則刪除回路上一條邊后的圖邊數(shù)減少一，面數(shù)減少一，故公式對G成立：nk-(mk+1)+(dk+1)=2.(2)G沒有回路，只有割邊，必有度數(shù)為一的結(jié)點，刪除相應割邊的一度頂點后，結(jié)點數(shù)和邊數(shù)分別減少一，面數(shù)不變，故仍然有(nk+1)-(mk+1)+dk=2.歐拉公式對非簡單圖仍然成立。第三十六頁，共四十三頁，編輯于2023年，星期一8.3.2歐拉公式對于n個頂點，m條棱，d個面的凸多面體，n-m+d=2.[推論]

設平面圖G的連通分支數(shù)為k，并有n個頂點，m條邊，d個域，則有n-m+d=k+1。[證明]

對每個連通分支使用歐拉公式，注意它們共同擁有一個無窮面。[定理]

若圖G是簡單的平面圖，則圖G至少有一個頂點的度小于6。第三十七頁，共四十三頁，編輯于2023年，星期一8.3.3極大平面圖[極大平面圖]

設G=(V,E)為簡單平面圖，|V|3，若對任意vi,vjV，且(vi,vj)E，有G=(V,E{(vi,vj)})為非平面圖，則稱G為一個極大平面圖?！皹O大性”乃針對固定頂點數(shù)的圖的邊的數(shù)目而言。第三十八頁，共四十三頁，編輯于2023年，星期一8.3.3極大平面圖[極大平面圖的性質(zhì)]極大平面圖是連通圖。極大平面圖的每個面都由3條邊組成。極大平面圖有3d=2m（d為面數(shù)目，m

為邊數(shù)目）。[定理]

設極大平面圖G有n個頂點，m條邊，d個域，則有m=3n-6，d=2n-4。[證明]

將3d=2m代入歐拉公式。[推論]

簡單平面圖G有m

3n-6，d

2n-4。[定理]

簡單平面圖至少有一個頂點的度小于6。[證明]

設任一點的度6，得m3n，矛盾。第三十九頁，共四十三頁，編輯于2023年，星期一8.3.4