第三章樹

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

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

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

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

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

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

如果是圖的支撐子圖,而且又是一棵樹,則稱是的一棵支撐樹,或稱生成樹,又簡稱的樹。3.6Huffman樹定義3.6.1

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

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

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

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

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

Huffman樹定理3.6.1

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

Kruskal算法的描述如下：

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

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

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

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

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

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

最短樹定理

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

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

WhileU≠Vdobegin

ForvV-Udoend最短樹定理3.7.3

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

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