第三章樹(shù)3.1樹(shù)的有關(guān)定義

第三章樹(shù)

3.1樹(shù)的有關(guān)定義給定一個(gè)圖，如果它不含任何回路，我們就叫它是林，如果又是連通的，即這個(gè)林只有一個(gè)連通支，就稱它是樹(shù)。樹(shù)的有關(guān)定義定義3.1.1

一個(gè)不含任何回路的連通圖稱為樹(shù)，用表示。中的邊稱為樹(shù)支，度為1的節(jié)點(diǎn)稱為樹(shù)葉。樹(shù)的每條邊，都不會(huì)屬于任何回路。這樣的邊叫割邊。樹(shù)的有關(guān)定義定義3.1.2

設(shè)是的一條邊，若比的連通支樹(shù)連通支數(shù)增加，則稱是的一條割邊。顯然，圖刪去割邊之后，結(jié)點(diǎn)分屬于不同的分支。樹(shù)的有關(guān)定義定理3.1.1

是割邊，當(dāng)且僅當(dāng)不屬于的任何回路。證明：若屬于的某個(gè)回路，則中仍存在到的道路，故結(jié)點(diǎn)和屬于同一連通支，不是割邊。反之，若不是割邊，則與的連通支數(shù)一樣。于是和仍屬于同一連同支，故中存在道路就是的一個(gè)回路。樹(shù)的有關(guān)定義定理3.1.2

設(shè)是結(jié)點(diǎn)數(shù)為的樹(shù)，則下列性質(zhì)等價(jià)：連通且無(wú)回路連通且每條都是割邊連通且有條邊有條邊且無(wú)回路的任意兩結(jié)點(diǎn)間有唯一道路無(wú)回路,但在任兩結(jié)點(diǎn)間加上一條邊后恰有一個(gè)回路樹(shù)的有關(guān)定義定理3.1.3

樹(shù)中一定存在樹(shù)葉結(jié)點(diǎn)。證明：由于是連通圖，所以任一結(jié)點(diǎn)，都有。若無(wú)樹(shù)葉，則。這樣矛盾。定義3.1.3

如果是圖的支撐子圖,而且又是一棵樹(shù),則稱是的一棵支撐樹(shù),或稱生成樹(shù),又簡(jiǎn)稱的樹(shù)。3.6Huffman樹(shù)定義3.6.1

除樹(shù)葉外，其余結(jié)點(diǎn)的正度最多為2的外向樹(shù)稱為二叉樹(shù)。如果它們的正度都是2，稱為完全二叉樹(shù)。Huffman樹(shù)定義3.6.1

如果二叉樹(shù)T的每個(gè)樹(shù)葉結(jié)點(diǎn)vi都分別賦以一個(gè)正實(shí)數(shù)wi，則稱T是賦權(quán)二叉樹(shù)。從根v0到樹(shù)葉vi的路徑P(v0,vi)所包含的邊數(shù)計(jì)為該路徑的長(zhǎng)度li，這樣二叉樹(shù)的路徑總長(zhǎng)是

vi是樹(shù)葉如果給定了樹(shù)葉數(shù)目以及它們的權(quán)值，可以構(gòu)造許多不同的賦權(quán)二叉樹(shù)，在這些賦權(quán)二叉樹(shù)中，必定存在路徑總長(zhǎng)WPL最小的二叉樹(shù)，這樣的樹(shù)稱為最優(yōu)二叉樹(shù)。Huffman樹(shù)例3.6.1

已知英文字符串a(chǎn)dacatedecade。試用二進(jìn)制字符串代替某個(gè)字幕，并保證該英文字符串與二進(jìn)制串構(gòu)成一一對(duì)應(yīng)。解：該字符串中有字母a,d,e,c,t，它們分別出現(xiàn)4,3,3,2,1次。令每個(gè)字母對(duì)應(yīng)二叉樹(shù)的一個(gè)樹(shù)葉，根到樹(shù)葉的路徑是唯一的，而且這條路徑?jīng)Q不會(huì)是根到另一個(gè)樹(shù)葉路徑的一部分。這樣跟到樹(shù)葉的路徑與該字母構(gòu)成一一對(duì)應(yīng)。如果在樹(shù)T中令向左的邊為0，向右的邊為1，那么這些路徑又與二進(jìn)制串構(gòu)成了一一對(duì)應(yīng)。Huffman樹(shù)哈夫曼給出了一個(gè)計(jì)算Huffman樹(shù)算法：對(duì)個(gè)權(quán)值進(jìn)行排序，滿足計(jì)算作為中間結(jié)點(diǎn)的權(quán)，的左兒子是，右兒子是。在權(quán)序列中刪去和，加入。若，否則轉(zhuǎn)(1)。

Huffman樹(shù)Huffman樹(shù)算法的計(jì)算復(fù)雜度是O(nlogn)。

Huffman樹(shù)定理3.6.1

由Huffman算法得到的二叉樹(shù)是最優(yōu)二叉樹(shù)3.7最短樹(shù)3.7.1Kruskal算法

Kruskal算法的描述如下：

T←Φ，當(dāng)|T|<n–1且E≠Φ時(shí),begine←E中最短邊.E←E-e.若T+e無(wú)回路,則T←T+e.end

若|T|<n-1打印”非連通”,否則輸出最短樹(shù)最短樹(shù)定理3.7.1

是賦權(quán)連通圖的最短樹(shù)，當(dāng)且僅當(dāng)對(duì)任意的余樹(shù)邊，回路滿足其邊權(quán)

證明:必要性，如果存在一條余樹(shù)邊，滿足

,則得到新樹(shù)比更加短,與是最短樹(shù)矛盾。最短樹(shù)充分性，若存在比還短的樹(shù),則，設(shè)

則構(gòu)成唯一回路。如果對(duì)任意的關(guān)于的余樹(shù)邊，它與回路里的樹(shù)支邊都有，則，與假設(shè)矛盾.因此一定存在某邊，對(duì)于某條邊，滿足。

最短樹(shù)定理

3.7.2Kruskal算法的計(jì)算復(fù)雜性是，其中是迭代次數(shù)。最短樹(shù)3.7.2Prim算法

Prim算法的基本思想是：首先任選一結(jié)點(diǎn)構(gòu)成集合，然后不斷在中選一條到中某點(diǎn)(比如)最短的邊進(jìn)入樹(shù)，并且，直到。最短樹(shù)Prim算法的描述如下:

WhileU≠Vdobegin

ForvV-Udoend最短樹(shù)定理3.7.3

設(shè)是賦權(quán)連通圖的結(jié)點(diǎn)真子集，是二端點(diǎn)分跨在和的最短邊，則中一定存在包含的最短樹(shù)干。證明：設(shè)是的一棵最短樹(shù)，若，則構(gòu)成唯一回路。該回路一定包含和其中，。由以知條件，作得到的仍是最短樹(shù)。最短樹(shù)定理3.7.4

Prim算法的結(jié)果是一得到賦權(quán)連通圖的一棵最短樹(shù)。證明：首先證明它是一棵支撐樹(shù)。采用歸納法，初始，它是由導(dǎo)出的樹(shù)，設(shè)是導(dǎo)出的樹(shù)，則下一次迭代時(shí)，中增加一新結(jié)點(diǎn)中也加入一條與相連的邊，因是連通的，則有