1、最小支撐樹,我們稱一個(gè)有k個(gè)連通分支且無(wú)圈的圖為k-樹或森林. 1-樹又簡(jiǎn)稱為樹，樹是一個(gè)連通的無(wú)圈圖. 樹的應(yīng)用：通訊網(wǎng)絡(luò)、市政管道、交通網(wǎng)絡(luò)等. 定理1. 設(shè)圖G=(V，E)是一個(gè)樹，|V|2，則G中至少有兩個(gè)點(diǎn)的度為1（懸掛點(diǎn)）.,證明:令 是G中含邊數(shù)最多的一條路，因|V|2，并且G是連通的，故v1與vk是不同的.則有d(v1)= d(vk)= 1. 否則有d(v1)2，則存在邊v1 ,vh使h2. 那么將出現(xiàn)G有圈或p不是最長(zhǎng)路. 同理可證d(vk)=1.,定理2：設(shè)G=(V,E)是一個(gè)圖，則下列命題等價(jià) G是樹； G是無(wú)環(huán)圖且G的任意兩個(gè)頂點(diǎn)之間有唯一的一條路； G是無(wú)圈圖且有|V

2、|-1條邊； G是連通圖且有|V|-1條邊； G是連通圖且每一條邊都是割邊； G是無(wú)圈圖，但在任意一對(duì)頂點(diǎn)間加上一條邊后恰有一個(gè)圈.,設(shè)T是圖G的一個(gè)支撐子圖，若T是樹，則稱T為G的支撐樹. 定理3：G有支撐樹T當(dāng)且僅當(dāng)G為連通圖. 尋找支撐樹的兩種方法：避圈法、破圈法.,給定圖G=(V，E)，對(duì)G中的每一條邊vi, vj，相應(yīng)地有一個(gè)數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊vi, vj上的權(quán). 最小支撐樹：給定網(wǎng)絡(luò) ，設(shè) 為N的一個(gè)支撐樹，記 ，稱之為T的權(quán)或樹的長(zhǎng). 我們希望找出所有支撐樹中權(quán)最小的支撐樹，即 .,1956年Kruskal給出了求解最小支撐樹的避圈法，又稱貪婪算法.

3、Kruskal算法思想：在構(gòu)造支撐樹的過程中每一步都避開圈，同時(shí)要求所選擇加入的邊的權(quán)最小.,用Kruskal算法求下圖所示網(wǎng)絡(luò)的最小支撐樹.,Kruskal算法： 把G中的邊按權(quán)重從小到大排序，并令 ，i=0,j=1. 若 含有圈，轉(zhuǎn)3；否則轉(zhuǎn)4. 令j=j+1,若 ，轉(zhuǎn)2；否則停止，G中不存在支撐樹. 令 ，并置i=i+1. 若i=n-1，則結(jié)束，這時(shí)GS即為所求；否則轉(zhuǎn)3.,證明Kruskal算法的正確性. 若在3結(jié)束，im，顯然沒有支撐樹. 若在6結(jié)束，i=n-1，得到的就是支撐樹. 支撐樹必定最小.,1959年Dijkstra提出另外一個(gè)算法. Dijkstra算法思想： 從一個(gè)頂點(diǎn)

4、出發(fā)，不斷的擴(kuò)大連通部分，每次都選擇連通成本最小，直到所有頂點(diǎn)都連通.,用Dijkstra算法求下圖所示網(wǎng)絡(luò)的最小支撐樹.,Dijkstra算法： 令 選取 ，若 ，停止，G中不存在支撐樹；否則置 若 ，則停止，T是最小支撐樹；否則對(duì)一切 ，置 ，轉(zhuǎn)2.,證明Dijkstra算法的正確性. 若在2結(jié)束，原圖不連通，顯然沒有支撐樹. 若在3結(jié)束，得到的就是支撐樹. 支撐樹必定最小.,破圈法 任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊(如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條)。在余下的圖中，重復(fù)這個(gè)步驟，直至得到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小支撐樹.,破圈法： 令 若 則G中不存在支撐樹，停止. 若T不含圈，則T就是最小支撐樹，停止. 選取T的一個(gè)圈C，記 轉(zhuǎn)2.,證明破圈法的正確性. 若在2結(jié)束，原圖不連通，顯然沒有支撐樹