最小枝杈樹問題

最小枝杈樹問題

又叫最小支撐樹問題、最小生成樹問題,是指在一個網路規劃中,從一個起點出發到所有接點,找出一條或幾條路線,以使在這樣一些路線中所採用的全部支線的總長度最小的規劃問題。

基本內容

圖1 圖1

:一個有k個連通分支且無圈的圖為k-樹或森林。即兩個要求:第一是連通的,第二是不含圈的。這樣的圖很像一棵樹,我們就形象地稱之為“樹”。例如圖1所示。

樹的性質:樹的邊數等於其頂點數減1;樹的任意兩個頂點之間恰有一條初級鏈相連線;在樹中任意去掉一條邊後,便得到一個不連通的圖;在樹中任意兩個頂點之間添加一條新邊,所得新圖恰有一個初級圈。

枝杈樹:若圖 G 的生成子圖 H 是樹,則稱 H 為 G 的枝杈樹或支撐樹。

最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題

最小枝杈樹:設G=[V,E]是一個無向圖,對每一條邊 ∈E有一個長度C( ) ≥0,G的任意支撐樹T各條邊的長度之和稱為樹T的長度,記為C(T)。長度最小的支撐樹稱為最小樹 。

相關定理

1.連通圖的生成樹一定存在 。

證明:給定連通圖 G,若 G 無圈,則 G 本身就是自己的生成樹。若 G 有圈,則任取 G 中一個圈C,記刪去 C 中一條邊後所得之圖為 G。顯然 G中圈 C 已經不存在,但 G仍然連通。若 G中還有圈,再重複以上過程,直到得到一個無圈的連通圖 H。易知 H 是 G 的生成樹。

2.設G=(V,E)是一個圖,則下列命題等價於:

①G是樹;
②G是無環圖且G的任意兩個頂點之間有唯一的一條路;
③G是無圈圖且有|V|-1條邊;
④G是連通圖且有|V|-1條邊;
⑤G是連通圖且每一條邊都是割邊;
⑥G是無圈圖,但在任意一對頂點間加上一條邊後恰有一個圈。

3.設圖G=(V,E)是一個樹,|V|≥2,則G中至少有兩個點的度為1(懸掛點) 。

最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題

證明:令p=( ) 是G中含邊數最多的一條路,因|V|≥2,並且G是連通的,故 與 是不同的。則有d( )= d( )= 1。否則有d( )≥2,則存在邊{ }使h≠2. 那么將出現G有圈或p不是最長路。同理可證d( )=1。

解決方法

最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題

一個簡單連通圖只要不是樹,其生成樹就不唯一,而且非常多。一般地,n 個頂點地完全圖,其不同地生成樹個數為 。因而,尋求一個給定賦權圖的最小生成樹,一般是不能用窮舉法的。例如,30 個頂點的完全圖有 個生成樹, 有 42 位,即使用最現代的計算機,在我們的有生之年也是無法窮舉的。所以,窮舉法求最小生成樹是無效的算法,必須尋求有效的算法。在求最小生成樹的有效算法中,最著名的兩個是 Kruskal(克羅斯克爾)算法和 Prim(普瑞姆)算法,其疊代過程都是基於貪婪法來設計的。

Kruskal 算法

Kruskal算法思想

在構造支撐樹的過程中每一步都避開圈,同時要求所選擇加入的邊的權最小。

Kruskal 算法的直觀描述

最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題

假設

是賦權圖 G 的最小生成樹,中的邊和頂點均塗成紅色,初始時 G 中的邊均為白色。
① 將所有頂點塗成紅色;
② 在白色邊中挑選一條權值最小的邊,使其與紅色邊不形成圈,將該白色邊塗紅;
③ 重複②直到有 n-1 條紅色邊,這 n-1 條紅色邊便構成最小生成樹的邊集合。

Prim 算法

最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題

Prim 算法的思想

和 C() 分別為圖 G 的最小生成樹的邊集及其權值,初始狀態均為空,算法結束時包含最小生成樹的所有邊,C() 表示最小生成樹的權值。先指定一個頂點為初始訪問點,記做,將加到“通過點”的集合 V 中,然後找出跨接在“通過點”集合與“未通過點”集合之間權最小的邊 e 作為“通過邊”加入中,並將 e 在中的端點轉到中。重複上述過程直至為止。
最小枝杈樹問題 最小枝杈樹問題
最小枝杈樹問題 最小枝杈樹問題

Prim 算法的直觀描述
假設

是賦權圖 G 的最小生成樹。任選一個頂點將其塗紅,其餘頂點為白點;在一個端點為紅色,另一個端點為白色的邊中,找一條權最小的邊塗紅,把該邊的白端點也塗成紅色;如此,每次將一條邊和一個頂點塗成紅色,直到所有頂點都成紅色為止。最終的紅色邊便構成最小生成樹的邊集合。

Prim和Kruskal的貪心策略是一樣的,都是選取耗費最小的邊,只不過選取的範圍不同:對於Prim,其選取的邊(u,v)必有一個頂點已經被覆蓋,另一個頂點未被覆蓋。而對於Kruskal,其選取的邊(u,v)任意,只要這個邊的加入不能使被覆蓋的頂點構成迴路 。

破圈法

破圈法思想:將圖的全部邊按照邊權的大小從大到小排序,在原圖的基礎上,從前到後考察這些邊,每考察一邊,驗證是否存在包含該邊在內的初級圈。若有,將該邊從邊集中刪除,否則保留。直到剩餘子圖為一樹(可以以剩餘的邊數作為檢驗條件),否則在考察下一條邊 。

破圈法的直觀描述

任取一個圈,從圈中去掉一條權最大的邊(如果有兩條或兩條以上的邊都是權最大的邊,則任意去掉其中一條)。在餘下的圖中,重複這個步驟,直至得到一個不含圈的圖為止,這時的圖便是最小枝杈樹 。

套用

在工農業生產、交通運輸、通訊和電力領域經常都能看到許多網路,如管道網、公路網、計算機通訊網、輸電線網等。還有許多看不見的網路,如各種關係網、事物的相互衝突關係等等,這些網路都可歸結為網路最最佳化問題 。常見的套用有電信網路(計算機網路、電話專用線網路、有線電視網路等等)的設計、低負荷運輸網路的設計,使得網路中提供連結的部分(如鐵路、公路 等)的總成本最小、高壓輸電線路網路的設計電器設備線路網路(如數字計算機系統)的設計、連線多個場所的管道網路設計等。

現實生活中有許多類似在城鎮間架設的電話線、鋪設管道、修築道路的問題,通常在一些早期的發展階段,由於技術或財力的局限,人們總是從節省材料或資金的角度,試圖設計一個網路能夠使得不同城鎮均能被直接或間接的連線起來,使其總長度最短。例如:要在n個城市之間鋪設光纜,主要目標是要使這 n 個城市的任意兩個之間都可以通信,但鋪設光纜的費用很高,且各個城市之間鋪設光纜的費用不同,因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小枝杈樹。

相關詞條

熱門詞條

聯絡我們