最小生成樹模型與實驗

1、第六章 最小生成樹模型與實驗樹是圖論中的一個重要概念，由于樹的模型簡單而實用，它在企業(yè)管理、線路設(shè)計等方面都有很重要的應(yīng)用。6.1樹與樹的性質(zhì)上章已討論了圖和樹的簡單根本性質(zhì)。為使更清楚明了，現(xiàn)在使用實例來說明。圖 6.1 例6.1 有五個城市，要在它們之間架設(shè) 線，要求任何兩個城市都可以互相通話允許通過其它城市，并且 線的根數(shù)最少。 用五個點代表五個城市，如果在某兩個城市之間架設(shè) 線，那么在相應(yīng)的兩個點之間聯(lián)一條邊，這樣一個 線網(wǎng)就可以用一個圖來表示。為了任何兩個城市都可以通話，這樣的圖必須是連通的。其次，假設(shè)圖中有圈的話，從圈上任意去掉一條邊，余下的圖仍是連通的，這樣可以省去一根 線。因而

2、，滿足要求的 線網(wǎng)所對應(yīng)的圖必定是不含圈的連通圖。圖6.1的表達式滿足要求的一個 線網(wǎng)。定義6.1 一個無圈的連通圖稱為樹.例6.2 某大學(xué)的組織機構(gòu)如下所示:文科辦公室 教務(wù)處 研究處 理科辦公室 校行政辦公室 研究生院 財務(wù)科數(shù)學(xué)系校長 行政科物理系 理工學(xué)院 校教學(xué)辦公室 人事學(xué)院 外語學(xué)院 如果用圖表示，該工廠的組織機構(gòu)圖就是一個樹。上章給出了一些樹的性質(zhì)，為使能進一步研究這局部知識，先再列出常用一些樹和生成樹的性質(zhì)。樹的性質(zhì)：（1） 樹必連通，但無回路圈；（2） 個頂點的樹必有條邊；（3） 樹中任意兩點間，恰有一條初等鏈；（4） 樹連通，但去掉任一條邊，必變?yōu)椴贿B通；（5） 樹無回路

3、圈，但不相鄰頂點連一條邊，恰得一回路圈。生成樹與最小樹 定義6.2 設(shè)圖是圖的生成子圖，如果是一棵樹，記，那么稱是的一棵生成樹。定理6.1 圖有生成樹的充分必要條件是圖的連通的。證：必要性是顯然的 充分性：設(shè)是連通圖。i如果不含圈，由定義6.1可知，本身就是一棵樹，從而是它自身的生成樹。i i如果含圈，任取一圈，從圈中任意去掉一條邊，得到圖的一個生成子圖，如果不含圈，那么是的一棵生成樹因為易見是連通的；如果仍含少量圈，那么從中任取一個圈，從圈中再任意去掉一條邊，得到圖的一個生成子圖，如此重復(fù)，最終可以得到的一個生成子圖，它不含圈，那么是圖的一棵生成樹。6.2 最小生成樹的實例與求解1圖 6.2

4、e7 由以上充分性的證明中，提供了一個尋求連通圖的生成樹的方法，稱這種方法為“破圈法。 例6.4 在圖6.1中，用破圈法求出圖的一棵生成樹解： 取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉；如圖6.3所示，此圖是圖6.2的一個生成子圖，且為一棵樹無圈，所以我們找一棵生成樹，其中，。不難發(fā)現(xiàn)，圖的生成樹不是唯一的，對于上例假設(shè)這樣做：取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。 圖6.3 圖6.4如圖的生成樹還有另外一種方法“避圈法，主要步驟是在圖中任取一條邊，找出一條不與構(gòu)成圈的邊，再找出不與構(gòu)成圈的邊。一般地，設(shè)已有，找出一條不與構(gòu)成圈的邊，重復(fù)這個過程，直到不能進行下去為止。這時，由

5、所有取出的邊所構(gòu)成的圖是圖的一棵生成樹。定義6.2 設(shè)是賦權(quán)圖的一棵生成樹，稱中全部邊上的權(quán)數(shù)之和為生成樹的權(quán)，記為。即 。 (7.1)如果生成樹的權(quán)是的所有生成樹的權(quán)中最小者，那么稱是的最小生成樹，簡稱為最小樹。即 7.2式中對的所有生成樹取最小。求最小樹通常用以下兩種方法。1破圈法：在給定連通圖中，任取一圈，去掉一條最大權(quán)邊如果有兩條或兩條以上的邊都是權(quán)最大的邊，那么任意去掉其中一條，在余圖中是圖的生成子圖任取一圈，去掉一條最大權(quán)邊，重復(fù)下去，直到余圖中無圈為止，即可得到圖的最小樹。例 6.4 用破圈法求圖6.5的最小樹。圖6.5是一賦權(quán)圖。13512423圖 6.5，；， ； ，；， ；

6、，； ， 。解： 取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。如圖6.6所示，得到一棵生成樹，即為所求最小樹，。2避圈法(Kruskal算法)：在連通圖中，任取權(quán)值最小的一條邊假設(shè)有兩條或兩條以上權(quán)相同且最小，那么任取一條，在未選邊中選一條權(quán)值最小的邊，要求所選邊與已選邊不構(gòu)成圈，重復(fù)下去，直到不存在與已選邊不構(gòu)成圈的邊為止。已選邊與頂點構(gòu)成的圖就是所求最小樹。算法的具體步驟如下：第一步：令，空集第二步：選一條邊，且是使圖中不含圈的所有邊中權(quán)最小的邊。如果這樣的邊不存在，由是最小樹。第三步：把換成，返回第二步。例6.5 用避圈法求圖6.5的最小樹。2112圖6.6解： 在中權(quán)值最小的邊有，

7、從中任取一條；在中選取權(quán)值最小的邊；在中權(quán)值最小邊有，從中任取一條邊；在中選取；在中選取。但與都會與已選邊構(gòu)成圈，故停止，得到與圖6.6一樣的結(jié)果。最小生成樹minimal spanning tree , MST模型概括為：給定網(wǎng)絡(luò)中一些點和這些點之間的距離，尋找連接所有這些點的最小總距離。 使用LINGO軟件編制此題的程序如下：MODEL:!Given the number of nodes and the distance between them, finding the shortest total distance of links on the network to connect

8、 all the nodes is the classic problem called minimal spanning tree (MST); SETS: CITY / 1. 5/: U; ! U( I) = level of city I; ! U( 1) = 0; LINK( CITY, CITY): DIST, ! The distance matrix; X; ! X( I, J) = 1 if we use link I, J; ENDSETS DATA: ! Distance matrix need not be symmetric; ! However, city 1 is

9、base of the tree; !to: A B C D E; DIST = 0 1 3 4 6 !from A; 1 0 2 3 5 !from B; 3 2 0 1 3 !from C; 4 3 1 0 2 !from D; 6 5 3 2 0;!from E; ENDDATA ! The model size: Warning, may be slow for N = 8; N = SIZE( CITY); ! Minimize total distance of the links; MIN = SUM( LINK: DIST * X); ! For city K, except

10、the base, . ; FOR( CITY( K)| K #GT# 1: ! It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1; ! If there are 2 disjoint tours from 1 city to another, we can remove a link without breaking connections. Note: These are not very powerful for large problems; FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:

11、 U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K); ); ); ! There must be an arc out of city 1; SUM( CITY( J)| J #GT# 1: X( 1, J) = 1; ! Make the Xs 0/1; FOR( LINK: BIN( X); ); ! The level of a city except the base is at least 1 but no more than N-1, and is 1 if it links to

12、 the base; FOR( CITY( K)| K #GT# 1: BND( 1, U( K), 999999); U( K) = 8; N = SIZE( CITY); ! Minimize total distance of the links; MIN = SUM( LINK: DIST * X); ! For city K, except the base, . ; FOR( CITY( K)| K #GT# 1: ! It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1; ! If there are 2 disjoi

13、nt tours from 1 city to another, we can remove a link without breaking connections. Note: These are not very powerful for large problems; FOR( CITY( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K); ); ); ! There must be an arc out of city 1; S

14、UM( CITY( J)| J #GT# 1: X( 1, J) = 1; ! Make the Xs 0/1; FOR( LINK: BIN( X); ); ! The level of a city except the base is at least 1 but no more than N-1, and is 1 if it links to the base; FOR( CITY( K)| K #GT# 1: BND( 1, U( K), 999999); U( K) = N - 1 - ( N - 2) * X( 1, K); );END使用Solve求解獲得如下結(jié)果：省略表6.

15、1中的城市間距離數(shù)據(jù)。最優(yōu)解 X(1,3)=1, X(1,4)=1, X(3,2)=1, X(4,5)=1, 其它X(I,J)=0。即：連接五個城市最小的生成樹網(wǎng)絡(luò)為：ChicagoHoustonAtlantaCincinnatiLA。其最小網(wǎng)絡(luò)距離。最優(yōu)值公里。6.4 選址問題選址問題是指為一個或幾個效勞設(shè)施在一定區(qū)域內(nèi)選定它的位置，使某一指標到達最優(yōu)值。選址問題的數(shù)學(xué)模型依賴于設(shè)施可能的區(qū)域和評判位置優(yōu)劣的標準，有許多不同類型的選址問題。在此只簡單介紹效勞設(shè)施與效勞對象都位于一個圖的頂點上的單效勞設(shè)施問題。中心問題有些公共效勞設(shè)施(例如一些緊急效勞型設(shè)施如急救中心、消防站)的選址，要求網(wǎng)絡(luò)

16、中最遠的被效勞點離效勞設(shè)施的距離盡可能小。例6.7 某城市要建立一個消防站，為該市所屬的七個區(qū)效勞圖6.7，問應(yīng)設(shè)在哪個區(qū)，才能使它至最遠區(qū)的路徑最短。算法：設(shè)各頂點為Vi, i=（1） 用最短路算法求出距離矩陣（2） 計算在各點設(shè)立效勞設(shè)施的最大效勞距離 （3） 求出頂點，使，那么就是要求的建立消防站的地點。此點稱為圖的中心點。重心問題有些設(shè)施例如一些非緊急型的公共效勞設(shè)施，如郵局、學(xué)校等的選址，要求設(shè)施到所有效勞對象點的距離總和最小。一般要考慮人口密度問題，要使全體被效勞對象來往的平均路程最短。例6.8某礦區(qū)有七個礦點圖6.8。各礦點每天的產(chǎn)礦量標在圖6.8的各頂點上。現(xiàn)有從這七個礦點選一

17、個來建造礦廠。問應(yīng)選在哪個礦點，才能使各礦點所產(chǎn)的礦運到選礦廠所在地的總運力單位：千噸/km最小。算法：頂點為Vi, i=，（1） 求距離陣；（2） 計算各頂點作為選礦廠的總運力：（3） 求，使，那么就是選礦廠應(yīng)設(shè)之礦點。此點稱為圖 的重心或中位點。例 6.9設(shè)備更新問題 企業(yè)使用一臺設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的。假設(shè)購置新設(shè)備，就要支付一定的購置費用；假設(shè)繼續(xù)使用，這需支付一定的維修費用。現(xiàn)要制定一個五年之內(nèi)的設(shè)備更新方案，使得五年內(nèi)總的支付費用最少。該種設(shè)備在每年年初的價格為：第一年第二年第三年第四年第五年1111121213使用不同時間設(shè)備所需維修費為：使用年限0-11-22-33-44-5維修費5681118對此問題，構(gòu)造加權(quán)有向圖，如圖6.9所示。 圖6.9的含義為：（1） 頂點集，每個頂點代表年初的一種決策，其中頂點代表第年初購置新設(shè)備的決策，頂點代表第年初修理用過年的舊設(shè)備的決策.（2） 弧集假設(shè)第年初作了決策