基本內容
圖1樹：一個有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算法思想
在構造支撐樹的過程中每一步都避開圈，同時要求所選擇加入的邊的權最小。
Kruskal 算法的直觀描述
最小枝杈樹問題 最小枝杈樹問題 最小枝杈樹問題假設
是賦權圖 G 的最小生成樹，中的邊和頂點均塗成紅色，初始時 G 中的邊均為白色。① 將所有頂點塗成紅色；
② 在白色邊中挑選一條權值最小的邊，使其與紅色邊不形成圈，將該白色邊塗紅；
③ 重複②直到有 n-1 條紅色邊，這 n-1 條紅色邊便構成最小生成樹的邊集合。
Prim 算法
最小枝杈樹問題 最小枝杈樹問題 最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題 最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題Prim 算法的思想
設
最小枝杈樹問題 最小枝杈樹問題Prim 算法的直觀描述
假設
Prim和Kruskal的貪心策略是一樣的，都是選取耗費最小的邊，只不過選取的範圍不同：對於Prim，其選取的邊(u,v)必有一個頂點已經被覆蓋，另一個頂點未被覆蓋。而對於Kruskal,其選取的邊(u,v)任意，只要這個邊的加入不能使被覆蓋的頂點構成迴路 。
破圈法
破圈法思想：將圖的全部邊按照邊權的大小從大到小排序，在原圖的基礎上，從前到後考察這些邊，每考察一邊，驗證是否存在包含該邊在內的初級圈。若有，將該邊從邊集中刪除，否則保留。直到剩餘子圖為一樹（可以以剩餘的邊數作為檢驗條件），否則在考察下一條邊 。
破圈法的直觀描述
任取一個圈，從圈中去掉一條權最大的邊(如果有兩條或兩條以上的邊都是權最大的邊，則任意去掉其中一條)。在餘下的圖中，重複這個步驟，直至得到一個不含圈的圖為止，這時的圖便是最小枝杈樹 。
套用
在工農業生產、交通運輸、通訊和電力領域經常都能看到許多網路，如管道網、公路網、計算機通訊網、輸電線網等。還有許多看不見的網路，如各種關係網、事物的相互衝突關係等等，這些網路都可歸結為網路最最佳化問題 。常見的套用有電信網路（計算機網路、電話專用線網路、有線電視網路等等）的設計、低負荷運輸網路的設計，使得網路中提供連結的部分（如鐵路、公路 等）的總成本最小、高壓輸電線路網路的設計電器設備線路網路（如數字計算機系統）的設計、連線多個場所的管道網路設計等。
現實生活中有許多類似在城鎮間架設的電話線、鋪設管道、修築道路的問題，通常在一些早期的發展階段，由於技術或財力的局限，人們總是從節省材料或資金的角度，試圖設計一個網路能夠使得不同城鎮均能被直接或間接的連線起來，使其總長度最短。例如：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小枝杈樹。
