Mathematicamodel最小生成樹算法參考書：1.傅鸝龔劬劉瓊蓀何中市《數學試驗》科學出版社2.張紹民李淑華《數據結構教程C語言版》中國電力出版社主講：龔劬制作：龔劬Prim算法Kruskal算法主要內容最小生成樹問題0-1規劃模型一個例子基本概念與結論趙根趙明趙亮趙麗趙雷趙虹趙雨趙霞趙云趙梅趙松樹圖——直觀形象表示工具類似于自然界中樹形象地表示家族樹：

沒有圈連通圖

樹中任意兩點間有唯一路徑。

樹邊數恰好為頂點數減1。

樹圖——直觀形象表示工具城市電信局有許多業務如收費，營業，112，114等，希望在全市范圍實現計算機聯網服務，共享各種資源。一個主要關心問題是：用數據通訊線把一組站點聯結起來，而不允許通訊線在非站點處相交，怎樣連接可使通訊線花費最小？引例：計算機網絡線路設計12345869157103引例：計算機網絡線路設計最經濟網絡不應該有任何封閉回路。引例：計算機網絡線路設計生成樹或支撐樹(spanningtree)：G子圖且是樹，其頂點集等于G頂點集；12345869157103怎樣簡便地得到左圖生成樹？它應有幾條邊？想確定應在哪些站點之間鋪設通訊線路，是否可看作是在對應加權圖中結構最小費用生成樹問題？引例：計算機網絡線路設計最小生成樹最大生成樹引例：計算機網絡線路設計想1)一個完全圖Kn有多少不一樣生成樹？2)怎樣求其最小生成樹?10個頂點完全圖，其不一樣生成樹就有一億棵。普通地，n個頂點完全圖，其不一樣生成樹個數為nn-2。30個頂點完全圖就有3028個生成樹，求最小生成樹時用窮舉法是無效。引例：計算機網絡線路設計返回返回最小生成樹與算法假如生成樹*T權)(*Tw是G全部生成樹權中最小者，則稱*T是G最小生成樹，簡稱為最小樹，即)}({min)(*TwTwT?=，式中取遍G全部生成樹T.

定義設),(1EVT=是賦權圖),(EVG=一棵生成樹，稱T中全部邊上權數之和為生成樹權，記為)(Tw，即??=1)()(EeewTw.

Prim算法Kruskal算法最小生成樹算法及其MATLAB程序實現返回算法MATLAB程序實現基本思想:

最初把圖n個頂點看作n個分離部分樹，每個樹含有一個頂點，算法每一步選擇可連接兩分離樹邊中權最小邊連接兩個部分樹，合二為一,部分樹逐步降低，直到只有一個部分樹（n-1步之后）便得到最小生成樹。Kruskal算法13245869157103時間復雜度:O(m)其中m為圖邊數Kruskal算法1)選擇邊e1，使得w(e1)盡可能小；2)若已選定邊，則從中選取，使得:i)為無圈圖，

ii)是滿足i)盡可能小權，3)當第2)步不能繼續執行時，則停頓.步驟定理由Kruskal算法構作任何生成樹都是最小生成樹.Kruskal算法123458391571061號子樹

2號子樹

3號子樹給每個子樹一個不一樣編號返回初始化：j0,T,c0,k0；對全部頂點i,t(i)i.jj+1t(B(1,j))t(B(2,j))TT(B(1,j),B(2,j)),cc+B(3,j),kk+1，i0t(i)=max{t(B(1,j)),t(B(2,j))t(i)min{t(B(1,j)),t(B(2,j)),k=n-1或j=mT,c整理邊權矩陣NYi=n終止NYYii+1NYNB:圖邊權矩陣;T:生成樹邊集;C:生成樹權;t:頂點所屬子樹編號Kruskal算法例:用Kruskal算法求引例中加權圖最小生成樹。12345869157103b=[11122334;24535455;815679103];邊權矩陣：b=[11122334;24535455;815679103];[B,i]=sortrows(b',3);B=B’;m=size(b,2);n=5;t=1:n;k=0;T=[];c=0;fori=1:mift(B(1,i))~=t(B(2,i))k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i)tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i))); forj=1:n ift(j)==tmax t(j)=tmin;endendend ifk==n-1break;endendT,c程序運行結果：T=14452325c=17Kruskal算法123456173返回Prim算法●基本思想：任選一個頂點v0開始，連接與v0最近頂點v1,得子樹T1，再連接與T1最近頂點v2得子樹T2，如此繼續下去，直到全部頂點都用到為止。●時間復雜度：O(n2),n為圖頂點數提示Kruskal算法和Prim算法都蘊涵了貪婪法思想，是貪婪法；貪婪法基本思想：把解看成是由若干個部件組成，每一步求出解一個部件（不是從整體或久遠角度考慮，只是局部或當前最好選擇）。求出一個個部件組合而作為最終解。貪婪法可被用于各種各樣問題處理。該法只是一個試探法，計算上簡便有效，可提供正確解一個近似。但普通情況下，不能確保輸出解是正確。其正確性需要證實，這往往比較困難。已證實,求最小生成樹Kruskal算法和Prim算法都是正確

注意返回分組技術是設計制造系統一個方法，它把生產零件機器分組，對應地把需生產零件分類，使零件跨組加工情形盡可能少，最理想情況是使每個零件加工，都在組內完成。假設有13種零件，需在9臺機器上加工。在各臺機器上加工零件號在下表中給出。范例：制造系統分組技術范例：制造系統分組技術機器123456789加工零件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,106設用Mi表示需由機器i加工零件集，對任意兩臺機器i,j,定義相異度：范例：制造系統分組技術建模“”：對稱差，分子：在機器i但不在機器j上加工，或在機器j但不在機器i上加工零件數。分母：或在機器i，或在機器j上加工零件數。顯然01建模1)(i,j)=0和(i,j)=1分別表示什么？2)表示了什么？想結構加權圖

以機器為頂點，作一個完全圖，每條邊(i,j)被賦予權(i,j)。原問題轉化加權圖最小生成樹是由那些相異度最小邊組成連通圖，假如希望把機器分成k個組，就繼續刪去最小生成樹上權最大k-1條邊。于是得到k個分離子樹，每棵樹頂點集就組成各機器組。建模對表1給出數據，加權圖邊權矩陣以下：[111111112222222333333444445555666778;234567893456789456789567896789789899;0.510.890.141111110.621111111110.50.870.670.750.7511111111011]用Kruskal算法可求出最小生成樹，在前面給出Kruskal算法MATLAB程序中，邊權矩陣b值改為此處邊權矩陣，頂點數n改為9即可。模型求解上一頁下一頁主頁T=7815123946474513c=4.4300912547863.51.5.14.87.67.750機器分組：{3，9}，{1，2，5}，{4，6，7，8}。912547863.5.5.14.67.750你能給出對應于該機器分組零件分類嗎？機器分組：{3，9}，{1，2，5}，{4，6，7，8}。912547863.5.5.14.67.750想模型結果返回設是兩點i與j之間距離，或1（1表示連接，0表示不連接），并假設頂點1是生成樹根.則最小生成樹問題0-1規劃模型最小生成樹問題0-1規劃模型例

（最優連線問題）我國西部SV地域共有1個城市（標識為1）和9個鄉鎮（標識為2--10）組成，該地域很快將用上天然氣，其中城市1含有井源.現要設計一供氣系統，使得從城市1到每個鄉鎮（2--10）都有一條管道相連，而且鋪設管子量盡可能少.下表給出了城鎮之間距離.求SV地域最優連線.最小生成樹問題0-1規劃模型最小生成樹問題0-1規劃模型

解：按照數學規劃寫出對應LINGO程序，MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets

最小生成樹問題0-1規劃模型7]data:!Distancematrix,itneednotbesymmetirc;8]distance=08591214121617229]809151681118142210]5907911712121711]91570317107151512]12169308106151513]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata最小生成樹問題0-1規劃模型19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Theremustbeanarcoutofcity1;23]@sum(cities(i)|i#gt#1:x(1,i))>=1;24]!Forcityi,exceptthebase(city1);25]@for(cities(i)|i#gt#1:26]!Itmustbeentered;27]@sum(cities(j)|j#ne#i:x(j,i))=1;28]!level(j)=levle(i)+1,ifwelinkjandi;最小生成樹問題0-1規劃模型29]@for(cities(j)|j#gt#1#and#j#ne#i:30]level(j)>=level(i)+x(i,j)31]-(n-2)*(1-x(i,j))+(n-3)*x(j,i);32]);33]!Thelevelofcityisatleast1butnomoren-1,34]andis1ifitlinkstobase(city1);35]@bnd(1,level(i),999999);36]level(i)<=n-1-(n-2)*x(1,i);37]);38]!Makethex's0/1;39]@for(link:@bin(x));END最小生成樹問題0-1規劃模型利用水平變量(level)來確保所選邊不組成圈.Globaloptimalsolutionfoundatit