最小枝杈樹問題

基本內容

樹：一個有k個連通分支且無圈的圖為k-樹或森林。即兩個要求：第一是連通的，第二是不含圈的。這樣的圖很像一棵樹，我們就形象地稱之為“樹”。例如圖1所示。

樹的性質：樹的邊數等於其頂點數減1；樹的任意兩個頂點之間恰有一條初級鏈相連線；在樹中任意去掉一條邊後，便得到一個不連通的圖；在樹中任意兩個頂點之間添加一條新邊，所得新圖恰有一個初級圈。

枝杈樹：若圖 G 的生成子圖 H 是樹，則稱 H 為 G 的枝杈樹或支撐樹。

最小枝杈樹：設G=[V,E]是一個無向圖，對每一條邊

∈E有一個長度C(

) ≥0,G的任意支撐樹T各條邊的長度之和稱為樹T的長度，記為C（T）。長度最小的支撐樹稱為最小樹。

1.連通圖的生成樹一定存在。

證明：給定連通圖 G，若 G 無圈，則 G 本身就是自己的生成樹。若 G 有圈，則任取 G 中一個圈C，記刪去 C 中一條邊後所得之圖為 G。顯然 G中圈 C 已經不存在，但 G仍然連通。若 G中還有圈，再重複以上過程，直到得到一個無圈的連通圖 H。易知 H 是 G 的生成樹。

2.設G=(V,E)是一個圖，則下列命題等價於：

①G是樹；
②G是無環圖且G的任意兩個頂點之間有唯一的一條路；
③G是無圈圖且有|V|-1條邊；
④G是連通圖且有|V|-1條邊；
⑤G是連通圖且每一條邊都是割邊；
⑥G是無圈圖，但在任意一對頂點間加上一條邊後恰有一個圈。

3.設圖G=(V，E)是一個樹，|V|≥2，則G中至少有兩個點的度為1（懸掛點）。

證明:令p=(

) 是G中含邊數最多的一條路，因|V|≥2，並且G是連通的，故

與

是不同的。則有d(

)= d(

)= 1。否則有d(

)≥2，則存在邊{

}使h≠2. 那么將出現G有圈或p不是最長路。同理可證d(

)=1。

一個簡單連通圖只要不是樹，其生成樹就不唯一，而且非常多。一般地，n 個頂點地完全圖，其不同地生成樹個數為

。因而，尋求一個給定賦權圖的最小生成樹，一般是不能用窮舉法的。例如，30 個頂點的完全圖有

個生成樹，

有 42 位，即使用最現代的計算機，在我們的有生之年也是無法窮舉的。所以，窮舉法求最小生成樹是無效的算法，必須尋求有效的算法。在求最小生成樹的有效算法中，最著名的兩個是 Kruskal（克羅斯克爾）算法和 Prim（普瑞姆）算法，其疊代過程都是基於貪婪法來設計的。

Kruskal算法思想

在構造支撐樹的過程中每一步都避開圈，同時要求所選擇加入的邊的權最小。

Kruskal 算法的直觀描述

假設

是賦權圖 G 的最小生成樹，

中的邊和頂點均塗成紅色，初始時 G 中的邊均為白色。
① 將所有頂點塗成紅色；
② 在白色邊中挑選一條權值最小的邊，使其與紅色邊不形成圈，將該白色邊塗紅；
③ 重複②直到有 n-1 條紅色邊，這 n-1 條紅色邊便構成最小生成樹

的邊集合。