第九章降低管道,網(wǎng)絡(luò)成本的,最小樹方法

1、 第九章第九章 降低管道網(wǎng)絡(luò)成本的最小樹方法降低管道網(wǎng)絡(luò)成本的最小樹方法 第一節(jié)第一節(jié) 引引 例例 C O D A B 4 10 4 9 5 8 6 13 O: 鍋爐房鍋爐房; A,B,C,D: 浴室。浴室。 如何架設(shè)管道，既保證四個如何架設(shè)管道，既保證四個 浴室都有蒸汽管道供應(yīng)，又浴室都有蒸汽管道供應(yīng)，又 使管道的的總長度為最短。使管道的的總長度為最短。 樹樹T=（V，E），）， p=n， q=m， 則則 m=n-1。 邊數(shù)邊數(shù)=點數(shù)點數(shù)-1 定義：定義： 無圈的連通圖稱為樹。樹一般用無圈的連通圖稱為樹。樹一般用T表示。表示。 一、樹的概念、一、樹的概念、 樹的性質(zhì)樹的性質(zhì): 二二 、圖的生

2、成樹、圖的生成樹 定義定義 設(shè)圖設(shè)圖T=V，E是圖是圖G=（V，E）的生成）的生成 子圖，如果子圖，如果T是一個樹，則稱是一個樹，則稱T是是G的一個生成樹。的一個生成樹。 v1 v3 v2v4 v5 v6 （a） v3 v1 v2v4 v5 v6 （b） （b）是（）是（a）的一個生成樹。）的一個生成樹。 定理定理 圖圖G有生成樹的充分必要條件是圖有生成樹的充分必要條件是圖G是連通的。是連通的。 證明：證明：必要性是顯然的。必要性是顯然的。 充分性：充分性： 設(shè)設(shè)G是連通的，如果是連通的，如果G不含圈，則不含圈，則G本身是本身是 一個樹，從而是它自身的一個生成樹。一個樹，從而是它自身的一個生成

3、樹。 現(xiàn)設(shè)現(xiàn)設(shè)G含圖，從圈中任意去掉一條邊，得含圖，從圈中任意去掉一條邊，得G的一的一 個生成子圖個生成子圖G1，如，如G1不含圈，則不含圈，則G1是是G的一個生成樹；的一個生成樹； 如如G1含圈，則從含圈，則從G1中任取一圈，從圈中再任意去掉一中任取一圈，從圈中再任意去掉一 條邊，得條邊，得G的一個生成子圖的一個生成子圖G2，如此重復(fù)，終可得，如此重復(fù)，終可得G 的一個不含圈的生成子圖的一個不含圈的生成子圖Gk，于是，于是Gk是是G的一個生成的一個生成 樹。樹。 （一）（一）破圈法破圈法 （二）（二）避圈法避圈法 在圖中任取一條邊在圖中任取一條邊e1，找一條與，找一條與e1不構(gòu)成圈的邊不構(gòu)成

4、圈的邊e2， 再找一條與再找一條與e1，e2不構(gòu)成圈的邊不構(gòu)成圈的邊e3。一般設(shè)已有。一般設(shè)已有e1， e2，ek，找一條與，找一條與e1，e2，ek中任何一些邊中任何一些邊 不構(gòu)成圈的邊不構(gòu)成圈的邊ek+1，重復(fù)這個過程，直到不能進行為，重復(fù)這個過程，直到不能進行為 止。止。(找到生成樹或判定沒有生成樹找到生成樹或判定沒有生成樹) v1 v2 v3 v4 v5 v6v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 如果生成樹如果生成樹T*的權(quán)的權(quán)w（T*）是）是G的所有生成樹的權(quán)的所有生成樹的權(quán) 中最小的，則稱中最小的，則

5、稱T*是是G的最小生成樹（簡稱最小樹）。的最小生成樹（簡稱最小樹）。 即即 )(min*)(TwTw T 最小樹問題，即求網(wǎng)絡(luò)最小樹問題，即求網(wǎng)絡(luò)G的最小生成樹。的最小生成樹。 第二節(jié)第二節(jié) 找找最小生成樹破圈法和加邊法最小生成樹破圈法和加邊法 若若 網(wǎng)絡(luò)中邊網(wǎng)絡(luò)中邊( i , j )的權(quán)為的權(quán)為dij ,則網(wǎng)絡(luò)的生成樹的則網(wǎng)絡(luò)的生成樹的 權(quán)為生成樹的各邊的權(quán)的和權(quán)為生成樹的各邊的權(quán)的和. C O D A B 10 45 6 C O D A B 4 10 4 9 5 8 6 13 C O D A B 4 9 5 6 C O D A B 4 10 45 6 （一）避圈法（一）避圈法（Kruska

6、l） 思想：在圖中取一條最小權(quán)的邊，以后每一步中，總思想：在圖中取一條最小權(quán)的邊，以后每一步中，總 從未被選取的邊中選一條權(quán)最小的邊，并使從未被選取的邊中選一條權(quán)最小的邊，并使 之與已選取的邊不構(gòu)成圈（每一步中，如果有之與已選取的邊不構(gòu)成圈（每一步中，如果有 兩條或兩條以上的邊都是最小權(quán)的邊，則從中兩條或兩條以上的邊都是最小權(quán)的邊，則從中 任選一條）。任選一條）。 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 6 7

7、 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 v6 2 3 4 5 6 7 4 v3 v1 v2v4 v5 1 5 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 （二）（二）破圈法破圈法 任取一個圈，從圈中去掉一條權(quán)最大的邊（如任取一個圈，從圈中去掉一條權(quán)最大的邊（如 果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意 去掉其中一條）。在余下的圖中，重復(fù)這個步驟，去掉其中一條）。在余下的圖中，重復(fù)這個步驟， 直到得到一個不含圈的圖為止，這時的圖便是最小直到得到一

8、個不含圈的圖為止，這時的圖便是最小 樹。樹。 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 6 7 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 64 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 64 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 4 v3 v1 v2v4 v5 v6 1 5 2 3 4 v3 v1 v2v4 v5 v6

9、1 5 第三節(jié)第三節(jié) 應(yīng)應(yīng) 用用 舉舉 例例 例例1 O:中央控制室中央控制室;A,B,C,D,E:控制點控制點 電纜線每米電纜線每米10元元,挖電纜挖電纜 溝溝(深深1米米,寬寬0.6米米)土方土方 3元元/米米3,其他材料和施工其他材料和施工 費費5元元/米米,這項工程的預(yù)這項工程的預(yù) 算至少要多少元算至少要多少元? C O D A B 30 40 90 70 70 20 60 110 E 100 80 C O D A B 30 40 90 70 70 20 60 110 E 100 80 C O D A B 30 40 70 70 20 60 110 E 100 80 C O D A B

10、 30 40 70 70 20 60 110 E 80 C O D A B 30 40 70 20 60 E 80 70 費用費用:最小樹的權(quán)最小樹的權(quán)(長度長度)230米米, 電纜電纜230米米 ,費用費用2300元元; 土方土方23010.6=138m3, 費用費用1383=414元元; 其他材料和施工費其他材料和施工費2305=1150元元. 總預(yù)算總預(yù)算3864元元. C O D A B 30 40 70 20 60 E 80 70 C O D A B 30 40 20 60 E 80 70 C O D A B 30 40 20 60 E 80 203頁頁 4題題 油井 2345678

11、 11.32.10.90.71.82.01.5 20.91.81.22.62.31.1 32.61.72.51.91.0 40.71.61.50.9 50.91.10.8 60.61.0 70.5 八口海上油八口海上油 井井,相間距相間距 離如表離如表,1號號 井離海岸最井離海岸最 近近,為為5海里海里. 從海岸井從海岸井1 號井鋪設(shè)油號井鋪設(shè)油 管管,把各井把各井 連接起來連接起來, 應(yīng)如何鋪設(shè)應(yīng)如何鋪設(shè), 使輸油管長使輸油管長 度最短度最短. 依次在表中找最小數(shù)依次在表中找最小數(shù),連接相應(yīng)的邊連接相應(yīng)的邊,但但 不能構(gòu)成圈不能構(gòu)成圈. 油井 2345678 11.32.10.90.71.82.01.5 20.91.81.22.62.31.1 32.61.72.51.91.0 40.71.61.50.9 50.91.10.8 60.61.0 70.5 8 7 0. 5 6 0.6 51 0.7 4 0.7 0.8 23 0.9 1.0 問題問題1 若要求若要求 前述網(wǎng)絡(luò)中點前述網(wǎng)絡(luò)中點v2與與v5必須直接連通，必須直