網(wǎng)絡(luò)優(yōu)化-第2章_最小樹及最小樹形圖

1、1網(wǎng)網(wǎng) 絡(luò)絡(luò) 優(yōu)優(yōu) 化化 第第2 2章章 最小樹與最小樹形圖最小樹與最小樹形圖 （第（第1 1講）講）Network Optimization清華大學(xué)數(shù)學(xué)科學(xué)系 謝金星辦公室：理科樓2206# （電話Email: http:/ 公路連接問題公路連接問題某一地區(qū)有某一地區(qū)有n個主要城市，現(xiàn)準備修建高速公路把這些城市個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，連接起來， 使得從其中任何一個城市都可以經(jīng)高速公路直接使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市或間接到達另一個城市. 假定已經(jīng)知道了任意兩個城市假定已經(jīng)知道了任意兩個城市i和和j之之間修

2、建高速公路的成本（費用）間修建高速公路的成本（費用）wij (0), 那么應(yīng)任何決定在那么應(yīng)任何決定在哪些城市間修建高速公路，使得總成本最??？哪些城市間修建高速公路，使得總成本最小？ 高速公路網(wǎng)正好構(gòu)成這個完全圖G的一個連通的支撐子圖T. 為了使得總建設(shè)成本最小, 該子圖必須是無圈的 無圈連通圖稱為樹，上面這樣一類問題稱為最小樹問題. 32.12.1樹的基本概念樹的基本概念 定定義義定義定義2.1 2.1 無圈連通圖稱為樹（無圈連通圖稱為樹（treetree）. . 無圈圖（即無圈圖（即若干棵樹的并）稱為森林或者簡稱林（若干棵樹的并）稱為森林或者簡稱林（forestforest）. . 如果一

3、個圖的支撐子圖是一棵樹，則稱這棵樹為該圖如果一個圖的支撐子圖是一棵樹，則稱這棵樹為該圖的支撐樹或者生成樹的支撐樹或者生成樹(spanning tree)(spanning tree)，并稱支撐樹，并稱支撐樹中的弧為樹?。ㄖ械幕闃浠。╰ree arctree arc），而不屬于支撐樹中的?。?，而不屬于支撐樹中的弧為非樹?。榉菢浠。╪ontree arcnontree arc）. . 樹是一類既簡單而又非常重要的圖形，在計算機科學(xué)、樹是一類既簡單而又非常重要的圖形，在計算機科學(xué)、有機化學(xué)、電網(wǎng)絡(luò)分析、最短連接及渠道設(shè)計等領(lǐng)域有機化學(xué)、電網(wǎng)絡(luò)分析、最短連接及渠道設(shè)計等領(lǐng)域都有廣泛的應(yīng)用都有廣泛的

4、應(yīng)用. . 在本節(jié)及下一節(jié)中，我們假設(shè)所討論的圖與網(wǎng)在本節(jié)及下一節(jié)中，我們假設(shè)所討論的圖與網(wǎng)絡(luò)都是無向的絡(luò)都是無向的. . 42.12.1樹的基本概念樹的基本概念 例例例例2.1 2.1 含含6 6個頂點的樹個頂點的樹 ( (非同構(gòu)的非同構(gòu)的) )：共有共有6 6種種 弧的條數(shù)弧的條數(shù) = = 節(jié)點數(shù)節(jié)點數(shù) - 1- 1 任何兩個頂點之間存在唯一的一條路任何兩個頂點之間存在唯一的一條路52.12.1樹的基本概念樹的基本概念 - - 樹的等價定義樹的等價定義引理引理2.1 G=(N, E)為一個圖，為一個圖，|N|=n，則下列命題等價，則下列命題等價:G是一棵樹；是一棵樹；G連通，且連通，且|E

5、|=n-1；G無圈，且無圈，且|E|=n-1；G的任何兩個頂點之間存在的任何兩個頂點之間存在唯一唯一的一條路；的一條路；1) G連通，且將連通，且將G的任何一條弧刪去之后，該圖成為非連通圖；的任何一條弧刪去之后，該圖成為非連通圖； 6) G無圈，且在無圈，且在G的任何兩個不相鄰頂點之間加入一條弧之后，的任何兩個不相鄰頂點之間加入一條弧之后，該圖正好含有一個圈該圖正好含有一個圈. 62.12.1樹的基本概念樹的基本概念 - - 最小樹的定義最小樹的定義定義定義2.2 G=（N，E，W）為一個無向網(wǎng)絡(luò)，）為一個無向網(wǎng)絡(luò)，W為權(quán)函數(shù)為權(quán)函數(shù), 即即W: ER （這里（這里R表示實數(shù)集合）表示實數(shù)集合

6、）. G中權(quán)最?。ù螅┑幕》Q中權(quán)最?。ù螅┑幕》Q為最?。ù螅┗樽钚。ù螅┗? 如果如果H=（N1，E1）為）為G的一個子圖，子圖的一個子圖，子圖H的權(quán)定義為的權(quán)定義為H所包含所包含的所有弧的權(quán)之和，記為的所有弧的權(quán)之和，記為W(H)，即，即W（H）= . 1)(EeeW弧弧e =(i，j) )上的權(quán)常記為上的權(quán)常記為W( (e),),We 或或w( (e) )，wij等等 如果如果T*是是G的一棵生成樹，且對的一棵生成樹，且對G的任何一棵生成樹的任何一棵生成樹T都有都有 W（ T* ）W（T），則），則T*稱為網(wǎng)絡(luò)稱為網(wǎng)絡(luò)G的最小支撐樹或者最小生的最小支撐樹或者最小生成樹（成樹（MST：mi

7、nimum spanning tree），或者簡稱最小樹），或者簡稱最小樹.圖的最小樹一般不唯一圖的最小樹一般不唯一72.12.1樹的基本概念樹的基本概念 - - 最小樹的應(yīng)用一例最小樹的應(yīng)用一例例例2.2 2.2 二維矩陣二維矩陣數(shù)據(jù)存貯問題數(shù)據(jù)存貯問題某些蛋白質(zhì)的氨基酸序列差異不多，如果用二維矩陣的每一行記錄一種蛋白某些蛋白質(zhì)的氨基酸序列差異不多，如果用二維矩陣的每一行記錄一種蛋白質(zhì)氨基酸序列，行與行之間的差異很小質(zhì)氨基酸序列，行與行之間的差異很小. . 其中一種方法是只存貯其中一行作其中一種方法是只存貯其中一行作為參照行，再存貯行與行之間的一部分差異信息，使得我們可以在需要時根為參照行，

8、再存貯行與行之間的一部分差異信息，使得我們可以在需要時根據(jù)參照行生成所有其它行的元素據(jù)參照行生成所有其它行的元素. . R1R3R2R4C13C12C24一般地，給定差異信息一般地，給定差異信息c cijij，如何確定存貯哪些行之間的差異元素，如何確定存貯哪些行之間的差異元素, , 使得存使得存貯空間盡可能少呢？這一問題可以用最小樹問題來描述貯空間盡可能少呢？這一問題可以用最小樹問題來描述: : 我們把矩陣每行作我們把矩陣每行作為一個節(jié)點構(gòu)成一個完全圖為一個節(jié)點構(gòu)成一個完全圖, , 第第i i個節(jié)點對應(yīng)于矩陣第個節(jié)點對應(yīng)于矩陣第i i行，并令弧行，并令弧( (i i, ,j j) )上上的權(quán)為

9、的權(quán)為c cijij. . 對于存貯問題對于存貯問題, , 實際上只需要存貯一行的元素實際上只需要存貯一行的元素, , 以及由該完全以及由該完全圖的一棵支撐樹所對應(yīng)的差異元素圖的一棵支撐樹所對應(yīng)的差異元素. . 最小樹就對應(yīng)于最優(yōu)的存貯方案最小樹就對應(yīng)于最優(yōu)的存貯方案. .82.12.1樹的基本概念樹的基本概念 - -觀察：支撐樹刪去一條樹弧后形成兩棵子樹，圖中兩個端點分觀察：支撐樹刪去一條樹弧后形成兩棵子樹，圖中兩個端點分屬于兩棵子樹的弧形成一個割屬于兩棵子樹的弧形成一個割. . 定理定理2.1 2.1 生成樹生成樹T*是最小樹的充要條件是：對是最小樹的充要條件是：對T*中的任何一條中的任何

10、一條弧，將該弧從弧，將該弧從T*中刪除后形成的割中，該弧為最小弧中刪除后形成的割中，該弧為最小弧. .最小樹的最小樹的“割最優(yōu)條件割最優(yōu)條件”T* 必要性：很容易用反證法證明。必要性：很容易用反證法證明。ee設(shè)設(shè)w(e) w( (e),令令T = = T* - e + e，則w(T* ) w( (T)9T*e2.12.1樹的基本概念樹的基本概念 - - 充分性充分性.設(shè)設(shè)T*是生成樹并滿足定理中的條件但不是最小樹，是生成樹并滿足定理中的條件但不是最小樹，設(shè)最小樹為設(shè)最小樹為T0. 記記e T* T0, 將將e從從T*中刪除后產(chǎn)生一個割中刪除后產(chǎn)生一個割. . 將將e加入加入T0后必然產(chǎn)生一個圈

11、，該圈必然包括割中一條與后必然產(chǎn)生一個圈，該圈必然包括割中一條與e不同不同的弧的弧e，由假設(shè)，由假設(shè)，w(e) w( (e).最小樹的最小樹的“割最優(yōu)條件割最優(yōu)條件”重復(fù)這一過程，最后可以得到T*也是最小樹 e由由T0為最小樹為最小樹，w(e) w( (e), 則w(e) = w( (e) ，因此， T1 = = T0 - e + e也是最小樹，與 T*有更多的公共弧 102.12.1樹的基本概念樹的基本概念 - -觀察：支撐樹加上一條非樹弧后包含一個唯一的圈觀察：支撐樹加上一條非樹弧后包含一個唯一的圈 T*定理定理2.1 2.1 生成樹生成樹T*是最小樹的充要條件是：對屬于是最小樹的充要條件

12、是：對屬于G但不屬于但不屬于T*的任何一條弧，將該弧加入的任何一條弧，將該弧加入T*后形成的圈中，該弧為最大弧后形成的圈中，該弧為最大弧. . 必要性：很容易用反證法證明。必要性：很容易用反證法證明。ee若若w(e) w( (T)，矛盾。最小樹的最小樹的“圈最優(yōu)條件圈最優(yōu)條件”112.12.1樹的基本概念樹的基本概念 - -T* 充分性充分性. . 設(shè)設(shè)T*是生成樹并滿足定理是生成樹并滿足定理2.22.2中的條件，我們中的條件，我們來證明它也滿足定理來證明它也滿足定理2.12.1中的條件。中的條件。最小樹的最小樹的“圈最優(yōu)條件圈最優(yōu)條件” ” 對對T*中的任何一條弧中的任何一條弧e，將該弧從，

13、將該弧從T*中刪除后形成的割中，考中刪除后形成的割中，考慮任何一條與慮任何一條與e不同的弧不同的弧e. .由定理由定理2.22.2中的條件假設(shè)中的條件假設(shè)w(e) w( (e)，即弧即弧e為最小弧為最小弧. .ee所以，滿足定理所以，滿足定理2.12.1中的條件。證畢。中的條件。證畢。122.2 2.2 最小樹算法最小樹算法 - -可以計算最小樹可以計算最小樹, , 自然也可以計算連通圖的生成樹自然也可以計算連通圖的生成樹. . 算法開始時假設(shè)某支撐子圖算法開始時假設(shè)某支撐子圖T T 的弧集合為空集的弧集合為空集; ; 算法運行過程中不斷將一些弧加入到子圖中算法運行過程中不斷將一些弧加入到子圖

14、中, , 并并且每次加入且每次加入T T 中的弧就會成為最后找到的最小樹的一中的弧就會成為最后找到的最小樹的一員，而不會再從員，而不會再從T T 中退出中退出. . 貪婪算法的共性貪婪算法的共性最直接的算法最直接的算法: “: “破圈法破圈法” ” 復(fù)雜度高，實施不復(fù)雜度高，實施不易易 理論基礎(chǔ)理論基礎(chǔ) - “- “割最優(yōu)條件割最優(yōu)條件”和和“圈最優(yōu)條件圈最優(yōu)條件”. . 如果算法結(jié)束時無法得到支撐樹如果算法結(jié)束時無法得到支撐樹, , 則說明圖不連通則說明圖不連通, , 因為連通圖一定有支撐樹因為連通圖一定有支撐樹. . 可以計算最小樹可以計算最小樹, , 變形后可以計算最大樹。變形后可以計算

15、最大樹。貪婪算法貪婪算法(Greedy Algorithm): (Greedy Algorithm): 132.2 2.2 最小樹算法最小樹算法基本思想：每次將一條權(quán)最小的弧加入子圖基本思想：每次將一條權(quán)最小的弧加入子圖T T 中，并中，并保證不形成圈保證不形成圈. . （避圈法）（避圈法）如果當(dāng)前弧加入后不形成圈如果當(dāng)前弧加入后不形成圈, , 則加入這條弧則加入這條弧, , 如果當(dāng)如果當(dāng)前弧加入后會形成圈前弧加入后會形成圈, , 則不加入這條弧則不加入這條弧, , 并考慮下一并考慮下一條弧條弧. . STEP0.STEP0. 令令i=1, j=0, T= =. .把把G的邊按照權(quán)由小到大排列

16、，即的邊按照權(quán)由小到大排列，即 ; ;2.2.1 Kruskal 算法(1956) )()()(21mewewewSTEP1.STEP1. 判斷判斷T T ei 是否含圈是否含圈. . 若含圈若含圈, , 轉(zhuǎn)轉(zhuǎn)STEP2, STEP2, 否則轉(zhuǎn)否則轉(zhuǎn)STEP3. STEP3. STEP2.STEP2. 令令i=i+1. . 若若i m, ,轉(zhuǎn)轉(zhuǎn)STEP1;STEP1;否則結(jié)束否則結(jié)束, ,此時此時G不連通不連通, ,所以沒有最小樹所以沒有最小樹. . STEP3.STEP3. 令令T=T T=T ei , j , j = =j j+1.+1.若若 j=n-1, , 結(jié)束，結(jié)束，T T是最小樹是

17、最小樹; ; 否則轉(zhuǎn)否則轉(zhuǎn)STEP1. STEP1. 正確性正確性：圈最優(yōu)條件圈最優(yōu)條件142.2 2.2 最小樹算法最小樹算法例例2.3 2.3 用用KruskalKruskal算法計算最小樹：算法計算最小樹：2.2.1 Kruskal 算法(1956) 113254638524711325435215Kruskal 算法的算法的計算復(fù)雜性計算復(fù)雜性對對m條弧進行排序條弧進行排序, , 其復(fù)雜度為其復(fù)雜度為 判斷加入一條弧到判斷加入一條弧到T T中時是否形成圈中時是否形成圈, , 其復(fù)雜度依賴于算法其復(fù)雜度依賴于算法的具體實現(xiàn)方法的具體實現(xiàn)方法. . 在算法的計算過程中, T是一個森林. 如

18、果該森林的每一棵子樹中的節(jié)點用一個單向鏈表表示，則可以方便地判斷圈. 當(dāng)考慮弧(i,j)時，如果其端點屬于同一單向鏈表，則加入T后會形成圈；如果其端點分屬于兩個不同的單向鏈表，則加入T后不會形成圈，因此將這兩個鏈表合并成一個鏈表. )log()log(nmOmmO由于處理每一條弧所需要的時間為O（n） ，因此這種實現(xiàn)方法的復(fù)雜度為O（nm）. )()log(mnOmnnmO)(3nO16Kruskal 算法的算法的計算復(fù)雜性計算復(fù)雜性改進改進算法實現(xiàn)算法實現(xiàn)改進：利用三個數(shù)組改進：利用三個數(shù)組 size - 用來記錄每個鏈表中所含節(jié)點的個數(shù)(鏈表規(guī)模)；last - 用來記錄每個鏈表中最后的節(jié)

19、點編號first - 用來記錄每個節(jié)點所在鏈表的第一個節(jié)點.如果鏈表L=1，2，4，5 ，則size(L)=|L|=4, last(L)=5, first(1)= first(2)= first(4) = first(5)=1. 考慮?。紤]?。╥ i，j j）時，只需判斷）時，只需判斷first(i)與與 first(j)是否相是否相等等,相等則端點屬于同一單向鏈表；否則合并鏈表相等則端點屬于同一單向鏈表；否則合并鏈表. 因此所有這些判斷所需要的計算時間為因此所有這些判斷所需要的計算時間為O(m). 合并時合并時, 我們總是把節(jié)點數(shù)較多的鏈表我們總是把節(jié)點數(shù)較多的鏈表L 放在前面放在前面,

20、而把節(jié)點而把節(jié)點數(shù)較少的鏈表數(shù)較少的鏈表L追加在后面追加在后面. 17Kruskal 算法的算法的計算復(fù)雜性計算復(fù)雜性合并后合并后, 對于對于size和和last的修改非常容易的修改非常容易,可以在常數(shù)時間內(nèi)完成可以在常數(shù)時間內(nèi)完成; 但對但對 first的的修改必須對鏈表修改必須對鏈表L中的每個元素中的每個元素(節(jié)點節(jié)點)進行進行, 復(fù)雜度為復(fù)雜度為 O(h)，h=size(L) . 只需要證明獲得一個規(guī)模為n的鏈表的計算時間（操作次數(shù)）不超過 p2nlogn (這里p2p1為常數(shù)）. 這種合并最多進行這種合并最多進行( (n-1)1)次次, , 對對 first 進行修改的總的復(fù)雜度為進行

21、修改的總的復(fù)雜度為 記鏈表L追加在鏈表L（ , ) 后面而合并成一個鏈表時的計算時間（操作次數(shù)）不超過 p1h（這里p1為常數(shù)） 數(shù)學(xué)歸納法: 當(dāng)n=1時不需要進行任何合并操作, 因此結(jié)論成立. 當(dāng)當(dāng)n n11時時, , 我們假設(shè)結(jié)論對規(guī)模小于我們假設(shè)結(jié)論對規(guī)模小于n n 的鏈表均成立的鏈表均成立. . )log(nnO)(,)(hLsizehLsizehh 設(shè)規(guī)模為設(shè)規(guī)模為n n的鏈表由的鏈表由L追加在L 后面合并而成后面合并而成, , 則則h n/2, h=n-h. p2hlogh+p2(n-h)log(n-h)+p1h p2hlog(n/2)+p2(n-h)logn+p2h = p2nl

22、ogn. 算法最后復(fù)雜度：算法最后復(fù)雜度： O(mlogn) 排序排序 O（mlogn）；其他其他O（m+nlogn）.18Kruskal 算法算法( (改進的實現(xiàn)）改進的實現(xiàn)） - - 例例首先考慮?。ㄊ紫瓤紤]?。? 1，2 2），將），將L L1 1，L L2 2合并成一個鏈表（如合并成一個鏈表（如L L1 1）：）：L L1 1=1=1，22，sizesize（L L1 1）=2=2， lastlast（L L1 1）=2=2，firstfirst（1 1）= = firstfirst（2 2）=1. =1. 1132546385247L L1 1=1=1，sizesize（L L1 1

23、）=1=1， lastlast（L L1 1）=1=1，firstfirst（1 1）=1=1；L L2 2=2=2，sizesize（L L2 2）=1=1， lastlast（L L2 2）=2=2，firstfirst（2 2）=2=2；L L3 3=3=3，sizesize（L L3 3）=1=1， lastlast（L L3 3）=3=3，firstfirst（3 3）=3=3；L L4 4=4=4，sizesize（L L4 4）=1=1， lastlast（L L4 4）=4=4，firstfirst（4 4）=4=4；L L5 5=5=5，sizesize（L L5 5）=1=

24、1， lastlast（L L5 5）=5=5，firstfirst（5 5）=5.=5. 19Kruskal 算法算法( (改進的實現(xiàn)）改進的實現(xiàn)） - - 例例下一步考慮弧（下一步考慮?。? 1，4 4），將），將L L1 1，L L4 4合并成一個鏈表（如合并成一個鏈表（如L L1 1）：）：L L1 1=1=1，2 2，4 4，55，sizesize（L L1 1）=4=4， lastlast（L L1 1）=5=5，firstfirst（1 1）= = firstfirst（2 2）= = first first（4 4）= = firstfirst（5 5）=1. =1. 下一步考

25、慮?。ㄏ乱徊娇紤]弧（4 4，5 5），將），將L L4 4，L L5 5合并成一個鏈表（如合并成一個鏈表（如L L4 4）：）：L L4 4=4=4，55，sizesize（L L4 4）=2=2， lastlast（L L4 4）=5=5，firstfirst（4 4）= = firstfirst（5 5）=4. =4. 1132546385247下一步考慮?。ㄏ乱徊娇紤]?。? 2，5 5），由于），由于firstfirst(2)(2)=first=first(5)(5)，因此繼續(xù)考慮下一條弧，因此繼續(xù)考慮下一條?。? 3，5 5），將），將L L1 1，L L3 3合并成一個鏈表合并成一個

26、鏈表L L1 1 ：L L1 1=1=1，2 2，4 4，5 5，33，sizesize（L L1 1）=5=5， lastlast（L L1 1）=3=3，firstfirst（1 1）= = firstfirst（2 2）= = first first（4 4）= = firstfirst（5 5）= = firstfirst（3 3）=1. =1. 11325435220KruskalKruskal算法的計算復(fù)雜性算法的計算復(fù)雜性Kruskal算法目前有更有效的實現(xiàn)方法，除了對算法目前有更有效的實現(xiàn)方法，除了對m條弧進行排條弧進行排序所需的時間外序所需的時間外, 其計算復(fù)雜性為其計算復(fù)雜

27、性為 O(m (n，m)，其中其中 （n，m）是用）是用Ackerman函數(shù)（一種隨函數(shù)（一種隨m，n快速增長的快速增長的函數(shù)）定義的某種函數(shù)）定義的某種“反函數(shù)反函數(shù)”，它隨，它隨m，n的增長非常非常緩的增長非常非常緩慢，實用中通常可以認為它小于慢，實用中通?？梢哉J為它小于6（如當(dāng)（如當(dāng)n=65536時，時， (n, m)不超過不超過3 ）.212.2.2 Prim 2.2.2 Prim 算法（算法（19571957）基本思想：不斷擴展一棵子樹基本思想：不斷擴展一棵子樹T=（S，E0），直到），直到S包包括原網(wǎng)絡(luò)的全部頂點，得到最小樹括原網(wǎng)絡(luò)的全部頂點，得到最小樹 T. （邊割法）（邊割法）

28、每次增加一條弧，使得這條弧是由當(dāng)前子樹節(jié)點集每次增加一條弧，使得這條弧是由當(dāng)前子樹節(jié)點集S S及及其補集所形成的邊割的最小弧其補集所形成的邊割的最小弧. . STEP0.STEP0. 設(shè)設(shè)v為為N的任意一個頂點，令的任意一個頂點，令S=v，E0= 。STEP1.STEP1. 若若S=NS=N，結(jié)束，結(jié)束，T T= =（S S，E E0 0）為最小樹；否則轉(zhuǎn)）為最小樹；否則轉(zhuǎn)STEP2. STEP2. STEP2.STEP2. 若若 = = ，則，則G不連通，結(jié)束；否則不連通，結(jié)束；否則 ，設(shè)，設(shè)其中其中 令令 轉(zhuǎn)轉(zhuǎn)STEP1.STEP1.正確性正確性：割最優(yōu)條件割最優(yōu)條件,SS),(min)(

29、,*ewewSSeSvSvvve2,1),2, 1(*,00,2*eEEvSS222.2 2.2 最小樹算法最小樹算法例例2.4 2.4 用用PrimPrim算法計算最小樹：算法計算最小樹：2.2.2 Prim 算法（1957） 113254638524711325435223距離標(biāo)號距離標(biāo)號d d（v v），記錄的是頂點），記錄的是頂點v v到集合到集合S S的的“距離距離”( (邊割邊割 中以中以v v為端點的最小弧的費用）為端點的最小弧的費用）; ;前趨標(biāo)號前趨標(biāo)號p p（v v），記錄的是邊割中該最小弧的另一個端點），記錄的是邊割中該最小弧的另一個端點. . Prim算法的算法的計算復(fù)

30、雜性計算復(fù)雜性該算法的主要計算量在于該算法的主要計算量在于STEP2STEP2（尋找邊割中的最小?。▽ふ疫吀钪械淖钚』。? . 如果通過對每條弧進行檢查尋找邊割中的最小弧，則該步的計算復(fù)雜度為O（m）. 因為STEP2最多執(zhí)行n-1步，所以該算法的復(fù)雜度為O（mn）. 特殊形式的PRIM算法 - DIJKSTRA算法（1959年） ,SS24利用各種形式的堆（利用各種形式的堆（HeapHeap），可以得到），可以得到PRIMPRIM或或DIJKSTRADIJKSTRA算法更有效的實現(xiàn)方法。復(fù)雜度為算法更有效的實現(xiàn)方法。復(fù)雜度為 或或DIJKSTRA算法（1959年）STEP0STEP0 設(shè)設(shè)

31、N N=1=1，2 2，,n,n. . 令令S S=1=1，E E0=0=， dj= =w1j ， pj=1.=1.STEP1選取 若找不到這樣的節(jié)點使最小值有限，則G不連通，結(jié)束；否則令 STEP2 若S=N，結(jié)束，T=（S，E0）為最小樹；否則令 ，并修改相應(yīng)的pj ,轉(zhuǎn)STEP1. 復(fù)雜度：復(fù)雜度：STEP1STEP1： (n-2)+(n-3)+1 = O(n(n-2)+(n-3)+1 = O(n2 2) (STEP2) (STEP2同理）同理） )(2nO)log(),log(nnmOnmO)loglog(CmOSjjdMinj: )(arg*),(00,*jpEEjSSjSjwdMi

32、ndjjjj,*25基本思想：基本思想：前面介紹的兩種算法的綜合。前面介紹的兩種算法的綜合。每次迭代同每次迭代同時擴展多棵子樹，直到得到最小樹時擴展多棵子樹，直到得到最小樹 T. STEP0.STEP0. 對對N中任意一個頂點中任意一個頂點i，定義，定義Ni=i. 令令T= 。STEP1.STEP1. 如果如果T 中已有中已有n-1條弧，則條弧，則T為為G的最小樹；否則，對的最小樹；否則，對T 中的所有子樹中的所有子樹節(jié)點集合節(jié)點集合Nk，計算邊割，計算邊割 中的最小弧，即計算中的最小弧，即計算其中其中 . 然后繼續(xù)然后繼續(xù)STEP2. STEP2. STEP2STEP2對對T T中的所有子樹

33、節(jié)點集合中的所有子樹節(jié)點集合Nk及最小弧及最小弧 ，將該子樹與，將該子樹與jk所在的子樹合并成一棵子樹，并將該最小弧納入所在的子樹合并成一棵子樹，并將該最小弧納入T 中中. . 然后轉(zhuǎn)然后轉(zhuǎn)STEP1. STEP1. 正確性正確性：割最優(yōu)條件割最優(yōu)條件2.2.3 SOLLIN 算法 （1961）,kkNN),(min)(,*ewewkkNNekkkkkkkkNjNijie,),(*),(*kkkjie 該算法的主要計算量在于以下循環(huán)交替迭代：該算法的主要計算量在于以下循環(huán)交替迭代：STEP1STEP1（尋找邊割中的最小?。▽ふ疫吀钪械淖钚』。㏒TEP2STEP2（子樹合并）（子樹合并）26S

34、OLLIN 算法算法 - - 例例下一步：下一步：合并合并N1， N2，即，即N1 =N2 =1，2； 合并合并N3， N5，即，即N3 =N5 =3，5； 合并合并N4， N5，即，即N3 =N4 =N5 =3，4，5開始時開始時Ni=i. 檢查知：對于檢查知：對于N1， N2，最小弧都是（，最小弧都是（1，2）；）； 對于對于N3， 最小弧是（最小弧是（3，5）；）； 對于對于N4， N5，最小弧都是（，最小弧都是（4，5）；）；1132546385247檢查知：對于檢查知：對于N1， N3，最小弧都是（，最小弧都是（1，4）；）；113254352下一步：下一步：合并合并N1， N3，即

35、，即N3 =N4 =N5 =1，2，3，4，5 結(jié)束結(jié)束27STEP1:STEP1:SollinSollin算法的算法的計算復(fù)雜性計算復(fù)雜性該算法的主要計算量在于該算法的主要計算量在于STEP1STEP1和和STEP2STEP2的循環(huán)交替迭代的循環(huán)交替迭代. . 對網(wǎng)絡(luò)中的每個節(jié)點賦予一個標(biāo)號，使得當(dāng)且僅當(dāng)兩個節(jié)點屬于同一棵子樹時，它們的標(biāo)號相同（開始時節(jié)點i賦予標(biāo)號i），此時可以方便地判斷兩個節(jié)點是否屬于同一子樹. 由于每次循環(huán)迭代時，每棵樹都會合并成一棵較大的子樹，因此每次循環(huán)迭代都會使子樹的數(shù)量至少減少一半. 所以，循環(huán)迭代的總次數(shù)為O（logn） .每次循環(huán)迭代所需要的計算時間： Nk

36、A( (i) )kNiiA| )(| kNimiAk2| )(|28STEP1:STEP1:把每一棵子樹中的所有節(jié)點存貯為一個雙向循環(huán)鏈表，此時從把每一棵子樹中的所有節(jié)點存貯為一個雙向循環(huán)鏈表，此時從該子樹的任何一個節(jié)點開始，可以方便地訪問它的所有節(jié)點該子樹的任何一個節(jié)點開始，可以方便地訪問它的所有節(jié)點. . 因此，因此，STEP1STEP1最多對每條弧進行兩次檢查最多對每條弧進行兩次檢查，復(fù)雜度為，復(fù)雜度為O（m）. SollinSollin算法的算法的計算復(fù)雜性計算復(fù)雜性該算法的主要計算量在于該算法的主要計算量在于STEP1STEP1和和STEP2STEP2的循環(huán)交替迭代的循環(huán)交替迭代.

37、. STEP2:在STEP2中，只需要根據(jù)STEP1找到的最小弧進行鏈表合并，并修改節(jié)點的標(biāo)號，復(fù)雜度為O（n）. 所以，算法總的復(fù)雜度為O(n+m) logn) = O(m logn ). 29布 置 作 業(yè)目的掌握樹與最小樹的基本概念掌握最小樹的幾種常用算法及其復(fù)雜性分析方法內(nèi)容網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化第第77-78頁頁 6; 7; 10; 11改錯：改錯： 5、“最小樹最小樹”指指“包含指定弧的權(quán)最小的支撐包含指定弧的權(quán)最小的支撐樹樹”30網(wǎng)網(wǎng) 絡(luò)絡(luò) 優(yōu)優(yōu) 化化 Network Optimization清華大學(xué)數(shù)學(xué)科學(xué)系 謝金星辦公室：理科樓2206# （電話Emai

38、l: http:/ 2章章 最小樹與最小樹形圖最小樹與最小樹形圖 （第（第2 2講）講）（最小樹形圖、最大分枝）31“直接方式直接方式”：總經(jīng)理直接傳達；：總經(jīng)理直接傳達；“接力方式接力方式”：總經(jīng)理只給某些部門經(jīng)理打電話，而讓這：總經(jīng)理只給某些部門經(jīng)理打電話，而讓這些得到信息的部門經(jīng)理打電話將信息進一步傳達給其他某些些得到信息的部門經(jīng)理打電話將信息進一步傳達給其他某些部門經(jīng)理，依此類推，最后將信息傳達到所有部門經(jīng)理部門經(jīng)理，依此類推，最后將信息傳達到所有部門經(jīng)理. 如何決定傳達信息的途徑？如何決定傳達信息的途徑？ 信息傳播是有向的，有一個信息傳播是有向的，有一個“根根”。 信息傳播途徑（忽略

39、方向時）是一棵樹。信息傳播途徑（忽略方向時）是一棵樹。以上結(jié)構(gòu)稱為樹形圖，上面這樣一類問題稱為最小樹形圖問題. 例例2.6 信息傳播信息傳播2.3 最小樹形圖 例32定義定義2.3 有向圖有向圖G=（V，A）若滿足：）若滿足：（1）不包含有向圈；）不包含有向圈；（2）存在一個頂點）存在一個頂點i使得使得d - (i)=0（即頂點（即頂點i沒有入?。?，而對其沒有入?。鴮ζ溆囗旤c余頂點j有有d - (j)=1（即頂點（即頂點j有且只有一條入?。?；有且只有一條入?。?；則稱則稱G為以為以i為根（為根（Root）的樹形圖（）的樹形圖（Arborescence），也稱有），也稱有根樹（根樹（Roote

40、d Tree）或外向樹（）或外向樹（Out-Tree）. 定義定義2.4 如果一個有向圖的支撐子圖是一個樹形圖，則稱該樹如果一個有向圖的支撐子圖是一個樹形圖，則稱該樹形圖為該有向圖的支撐樹形圖形圖為該有向圖的支撐樹形圖( (或生成樹形圖或生成樹形圖). ). 有向網(wǎng)絡(luò)中權(quán)有向網(wǎng)絡(luò)中權(quán)最小的支撐樹形圖稱為該網(wǎng)絡(luò)的最小樹形圖最小的支撐樹形圖稱為該網(wǎng)絡(luò)的最小樹形圖. . 2.32.3最小樹形圖最小樹形圖 定定義義33定義定義2.5 設(shè)設(shè)v是網(wǎng)絡(luò)是網(wǎng)絡(luò)N的任意一個節(jié)點，在所有指向的任意一個節(jié)點，在所有指向v的入弧中，的入弧中，權(quán)最小的弧稱為權(quán)最小的弧稱為v的最小入弧的最小入弧. 由最小入弧組成的有向圈

41、稱為由最小入弧組成的有向圈稱為最小入弧圈最小入弧圈. 若網(wǎng)絡(luò)若網(wǎng)絡(luò)N的每個節(jié)點取最小入弧組成的子圖是支撐樹的每個節(jié)點取最小入弧組成的子圖是支撐樹形圖，則它就是最小樹形圖形圖，則它就是最小樹形圖. (書上說法有誤書上說法有誤)如果在網(wǎng)絡(luò)如果在網(wǎng)絡(luò)N中，從每個節(jié)點取一條最小入弧，組成中，從每個節(jié)點取一條最小入弧，組成的子圖是否就是最小樹形圖？的子圖是否就是最小樹形圖？ 2.32.3最小樹形圖最小樹形圖 v 從樹形圖的根到每一個節(jié)點有且僅有一條有向路，這條路的從樹形圖的根到每一個節(jié)點有且僅有一條有向路，這條路的長度稱為該節(jié)點的代（即該節(jié)點關(guān)于根節(jié)點的層數(shù)）長度稱為該節(jié)點的代（即該節(jié)點關(guān)于根節(jié)點的層數(shù)

42、）. . v 樹形圖在去掉每條弧的方向后，得到的無向基本圖是一棵樹，樹形圖在去掉每條弧的方向后，得到的無向基本圖是一棵樹，因此具有因此具有n個節(jié)點的樹形圖包含個節(jié)點的樹形圖包含n-1 1條弧條弧. . 34引理引理2.2 網(wǎng)絡(luò)網(wǎng)絡(luò)N每個節(jié)點取一最小入弧，組成的圖記為每個節(jié)點取一最小入弧，組成的圖記為H，則，則（1）若）若|H|n-1，（2）若）若|H|=n-1 ，（3）若若|H|=n ，2.32.3最小樹形圖最小樹形圖 引引理理證明證明(略略)Ha最小樹形圖是否一定是最小樹形圖是否一定是，或或去掉一條??？去掉一條??？則則N沒有支撐樹形圖；沒有支撐樹形圖；且且H不含有向圈，則不含有向圈，則H是是

43、N的最小樹形圖的最小樹形圖;設(shè)設(shè)a是是H中權(quán)最大的弧，且中權(quán)最大的弧，且Ha不含有向圈，不含有向圈，則則Ha是是N的最小樹形圖的最小樹形圖.35),(kkkvva 定理定理2.3 設(shè)設(shè)C是網(wǎng)絡(luò)是網(wǎng)絡(luò)N的最小入弧圈，如果的最小入弧圈，如果N存在支撐樹形圖，則存在支撐樹形圖，則存在存在N的最小樹形圖的最小樹形圖T滿足滿足| C T |=1. 證明證明 假設(shè)定理不成立，在假設(shè)定理不成立，在N的最小樹形圖中找一棵的最小樹形圖中找一棵T使得使得| C T | 最小最小. . 2.32.3最小樹形圖最小樹形圖 定理定理由于樹形圖不含有向圈，由于樹形圖不含有向圈，因此因此| C T |= .記記C中不在中不

44、在T上的弧依次為上的弧依次為, , 則則C中余下的弧組成的有向路中余下的弧組成的有向路, , 都屬于都屬于T. ),(111vva ),(222vva ),(kkkvva ),(21vvP),(32vvP),(1vvPk不妨設(shè)不妨設(shè) v1是所有是所有k個節(jié)點個節(jié)點 v1 , ,v2 , , ,vk 在在T T 中代數(shù)最小的節(jié)點，則中代數(shù)最小的節(jié)點，則 v1在在T T 中不會是中不會是 v2的后代的后代),(111vva ),(222vva ),(21vvP),(32vvP),(1vvPk但由于但由于v2在在T T 中是中是v1的后代，所以的后代，所以 v2在在T T 中不會是中不會是 v2的后

45、代的后代. . C36v2在在T T 中一定有入弧中一定有入弧( (記為記為 a1 ) )，則，則 T = = T+ +a2 - -a1 也是也是N N 的支撐樹形圖的支撐樹形圖. . 2.32.3最小樹形圖最小樹形圖 定理定理 因為因為 W(W(a2 ) ) W(W( a1 ) ) 所以所以因此因此T 也是也是N N 的最小樹形圖，的最小樹形圖，且且|CT |=|CT|-1這與這與T 的取法矛盾的取法矛盾. . 故定理得證故定理得證. . ),(111vva ),(222vva ),(kkkvva ),(21vvP),(32vvP),(1vvPka1)()()()()(12TWaWaWTWT

46、W即即: :最小入弧圈中除一條弧外最小入弧圈中除一條弧外, ,包含在某個最小樹形圖中包含在某個最小樹形圖中. .37關(guān)鍵關(guān)鍵: : 如果最小樹形圖的根節(jié)點在圈上，只需去掉圈上的一條如果最小樹形圖的根節(jié)點在圈上，只需去掉圈上的一條弧弧( (根節(jié)點的入弧根節(jié)點的入弧) )即可：即可：記記C C中的最大弧為中的最大弧為a* *，則權(quán)和為，則權(quán)和為W(W(C )-W()-W(a* * ) )2.32.3最小樹形圖最小樹形圖 定理的意義定理的意義如果根節(jié)點在圈外呢如果根節(jié)點在圈外呢? ?必須找一條從圈外指向圈上某節(jié)點的弧必須找一條從圈外指向圈上某節(jié)點的弧a來代替圈上指向該節(jié)點的弧來代替圈上指向該節(jié)點的弧

47、a1： 替代后的權(quán)和為替代后的權(quán)和為 W(W(C )+ W()+ W(a )- W()- W( a1 ) )自然希望在上述兩種可能性中使總權(quán)和增加的量盡可能小自然希望在上述兩種可能性中使總權(quán)和增加的量盡可能小! ! 即要比較即要比較W(W(C )-W()-W(a* * ) )和和W(W(C )+ W()+ W(a )- W()- W( a1 ) )引入引入“收縮收縮”的概念的概念 - 弧弧a: “: “收縮收縮”前的權(quán)前的權(quán): W(: W(a ) ) “ “收縮收縮”后的權(quán)后的權(quán): W(: W(a )- W()- W( a1 ) + W() + W(a* * ) )a1aCa*38定義定義2.

48、6 設(shè)設(shè)C是有向網(wǎng)絡(luò)是有向網(wǎng)絡(luò)N=(V，A，W)的一個有向圈，的一個有向圈，W為權(quán)為權(quán)函數(shù)函數(shù). 記記C的節(jié)點集為的節(jié)點集為V(C)，弧集為，弧集為A（C）. 定義定義N收縮收縮C后得后得到的新網(wǎng)絡(luò)到的新網(wǎng)絡(luò)N*=（V*，A*，W*）為）為:V*= V V(C) y ，（節(jié)點，（節(jié)點y稱為收縮稱為收縮C后的人工節(jié)點）后的人工節(jié)點） A*= A A(C) ，其中其中a1 1是是C中與中與a有相同末端的弧，有相同末端的弧， a* *是是C中權(quán)最大的弧中權(quán)最大的弧. 這一這一過程稱為過程稱為網(wǎng)絡(luò)的收縮（網(wǎng)絡(luò)的收縮（Condensation），），N*稱為稱為N的收縮網(wǎng)絡(luò)的收縮網(wǎng)絡(luò)（Condensed

49、 Network），可簡記為），可簡記為N*=N/C. 收縮網(wǎng)絡(luò)的最小樹形圖與原網(wǎng)絡(luò)的最小樹形圖有何關(guān)系收縮網(wǎng)絡(luò)的最小樹形圖與原網(wǎng)絡(luò)的最小樹形圖有何關(guān)系? ?收縮網(wǎng)絡(luò)收縮網(wǎng)絡(luò) 定定義義,),()()(,),()(*1*yNaaWaWaWyNaaWaW中的末端是在當(dāng)中的末端不是在當(dāng)39定理定理2.4 設(shè)設(shè)C是網(wǎng)絡(luò)是網(wǎng)絡(luò)N=（V,A,W）的最小入弧圈，）的最小入弧圈，N*=N/C=（V*,A*,W*）是）是N收縮收縮C后得到的新網(wǎng)絡(luò)后得到的新網(wǎng)絡(luò). 如果如果T*是是N*的最小樹的最小樹形圖，則形圖，則T* C包含了包含了N的一棵最小樹形圖的一棵最小樹形圖. 證明證明 記記a*是是C C中權(quán)最大的弧

50、中權(quán)最大的弧. . 首先證明首先證明T* C中包含中包含N N中的一棵中的一棵權(quán)為權(quán)為W*(T*)+ W(C)- W( ( a*) )的支撐樹形圖的支撐樹形圖. .下面分兩種情況討論下面分兩種情況討論 收縮網(wǎng)絡(luò)收縮網(wǎng)絡(luò) 定理定理40收縮網(wǎng)絡(luò)收縮網(wǎng)絡(luò) 定理定理(2)(2) 設(shè)人工節(jié)點設(shè)人工節(jié)點y是是T*的根節(jié)點：此時的根節(jié)點：此時T2= =T* Ca*為為T* C包含包含的的N中的一棵支撐樹形圖中的一棵支撐樹形圖, ,且且 ).()()()(*2aWCWTWTW(1)(1)人工節(jié)點人工節(jié)點y在在T*中有入弧中有入弧( (記為記為a0) )：設(shè)：設(shè)C C中與中與a0有相同末端的有相同末端的弧為弧為

51、a1，則，則T1= =T* Ca1為為T* C包含的包含的N中的唯一支撐樹形圖中的唯一支撐樹形圖. . )()()()()()()()()()()()(*0*1010*0*aWCWTWaWCWaWaWaWCWaWaWTWaTaaTaa0a1a*a*41收縮網(wǎng)絡(luò)收縮網(wǎng)絡(luò) 定理定理所以所以類似于上面兩種情況的討論類似于上面兩種情況的討論, ,可以進一步得到可以進一步得到 W(T 0) = W*(T 0*) +W（C）-W（a*）根據(jù)定理根據(jù)定理2.3, 存在存在N的最小樹形圖的最小樹形圖T0使得使得|CT0 |=1. 在收在收縮縮C后后, T0變成變成N*中的支撐樹形圖中的支撐樹形圖T 0*, 因

52、此因此 W*(T 0*) W*(T*)于是只能有于是只能有W*(T 0*) = W*(T*), ,也就是說也就是說T 0*也也是是N*中的最小中的最小樹形圖樹形圖. .因為否則的話因為否則的話, ,T0不會是不會是N中的最小樹形圖中的最小樹形圖 ( (T1或或T2才才是是N中的最小樹形圖中的最小樹形圖).).T1和和T2是是T* C中包含的中包含的N中的最小樹形圖，權(quán)為中的最小樹形圖，權(quán)為W*(T*)+ W(C)- W( ( a*) )()()()()()(21*0TWTWaWCWTWTW證畢證畢42基本思想：收縮基本思想：收縮 展開展開 （EdmonsEdmons算法，算法，19681968

53、）STEP0.STEP0. 令令m=1 1， N1( (V1, ,A1, ,W1)=)=N( (V, ,A, ,W) )朱朱( (永津永津)-)-劉劉( (振宏振宏) )算法（算法（19651965）STEP1.STEP1. 在在Nm中對每個節(jié)點取一條最小入弧，組成的弧集記為中對每個節(jié)點取一條最小入弧，組成的弧集記為Hm. . 若若| |Hm|Vm|-1|-1，則原網(wǎng)絡(luò)沒有支撐樹形圖；否則若，則原網(wǎng)絡(luò)沒有支撐樹形圖；否則若| |Hm|=|=|Vm| | ，則去掉，則去掉Hm中的權(quán)最大的一條?。ㄈ杂洖橹械臋?quán)最大的一條?。ㄈ杂洖镠m），繼續(xù)下一步；否則直接繼續(xù)下一步），繼續(xù)下一步；否則直接繼續(xù)下一

54、步. . STEP2.STEP2.若若Hm不包含圈不包含圈, ,則令則令Hm= =Hm，轉(zhuǎn)，轉(zhuǎn)STEP4STEP4；否則??；否則取Hm包含的一個圈包含的一個圈Cm，繼續(xù)下一步繼續(xù)下一步. . STEP3.(STEP3.(收縮收縮) )對對Nm收縮收縮Cm得到新的網(wǎng)絡(luò)得到新的網(wǎng)絡(luò)Nm+1( (Vm+1, ,Am+1, ,Wm+1) )，記人工節(jié)點，記人工節(jié)點為為ym. . 令令m=m+1，轉(zhuǎn)，轉(zhuǎn)STEP1. STEP1. STEP5:STEP5:( (展開展開) )令令Hm-1 = = Hm ( (Cm-1 am-1) )，其中，其中am-1是是Cm-1中的一條弧：如中的一條?。喝绻鹹m-1在

55、在Hm中有入弧，則取中有入弧，則取am-1為與該入弧有相同末端的弧；為與該入弧有相同末端的??； 否則否則am-1取取Cm-1中的權(quán)最大的一條弧中的權(quán)最大的一條弧. . 令令m=m-1-1，轉(zhuǎn)，轉(zhuǎn)STEP4.STEP4. STEP4STEP4：若：若m=1=1，則，則H1就是就是N N中的最小樹形圖，結(jié)束；否則繼續(xù)下一步中的最小樹形圖，結(jié)束；否則繼續(xù)下一步. . 43朱朱- -劉算法劉算法 復(fù)雜性分析復(fù)雜性分析上述算法實際上包括兩大過程：上述算法實際上包括兩大過程：收縮（收縮（STEP1STEP3STEP1STEP3）和展開（）和展開（STEP4STEP5STEP4STEP5）. . 每一個過程

56、最多循環(huán)（每一個過程最多循環(huán)（n-1 1）次）次. . 容易容易看出看出STEP1的復(fù)雜度為的復(fù)雜度為O（m），），STEP2的復(fù)雜度為的復(fù)雜度為O(n)，STEP3的復(fù)雜度為的復(fù)雜度為O（m），），STEP4的復(fù)雜度為的復(fù)雜度為O（1），），STEP5的復(fù)雜度為的復(fù)雜度為O（m）。）。因此朱因此朱- -劉算法的總復(fù)雜度為劉算法的總復(fù)雜度為O（mn）. 該算法同樣可以用于計算最大樹形圖（只需將權(quán)反號即可）該算法同樣可以用于計算最大樹形圖（只需將權(quán)反號即可）. . 對算法作一些小的改動，容易設(shè)計求具有固定根的最小樹形對算法作一些小的改動，容易設(shè)計求具有固定根的最小樹形圖或最大樹形圖（留作練習(xí)）圖或最大樹形圖（留作練習(xí)）. . 44N=NN=N1 1H H1