論文國(guó)家隊(duì)吳景岳

《論文國(guó)家隊(duì)吳景岳》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、最小生成樹算凍及其應(yīng)用江蘇省常州高級(jí)中學(xué)吳景岳【摘要】最小生成樹是圖論中的經(jīng)典問(wèn)題,也是一個(gè)重要部分，一般書上往往只介紹求最小生成樹的算法，而忽略了更精彩的算法應(yīng)川部分。本文將對(duì)最小生成樹算法及其應(yīng)川作全血的分析說(shuō)明，使大家對(duì)此有更加深刻的認(rèn)識(shí)。本文分三部分：一、基礎(chǔ)篇，主要介紹基礎(chǔ)概念、求最小生成樹的一般算法和常用算法。二、應(yīng)用篇，具體問(wèn)題具體分析，側(cè)重于思考和證明的過(guò)程。三、總結(jié)?！娟P(guān)鍵字】最小生成樹【目錄】一、基礎(chǔ)篇1.定義2.求最小生成樹的一般算法3.常用算法a)Kruskal算法b)Prim算法4?Maintain——1012003二、應(yīng)用篇1.概述2?

2、例題a)RobotBOI2002b)北極通訊網(wǎng)絡(luò)WaterlooUniversity2002三、總結(jié)笫1頁(yè)共29頁(yè)【正文】1.基礎(chǔ)篇1.1定義在電路設(shè)計(jì)小，常常需要把一些電子元件的插腳用電線連接起來(lái)。如果每根電線連接兩個(gè)插腳，把所有n個(gè)插腳連接起來(lái)，只要用n?l根電線就可以了。在所有的連接方案中，我們通常對(duì)電線總長(zhǎng)度最小的連接方案感興趣。把問(wèn)題轉(zhuǎn)化為圖論模型就是：一個(gè)無(wú)向連通圖G=(V,E),V是插腳的集合，E是插腳兩兩之間所有可能的連接的集合。給每條邊(u,v)—個(gè)權(quán)值w(u,v),表示連接它們所需的電線氏度。我們的目標(biāo)就是找到一個(gè)無(wú)環(huán)的邊集T,連接其中所有的點(diǎn)

3、且使總權(quán)值最小。既然T是連接所有點(diǎn)的無(wú)環(huán)邊集，它一定是一棵樹。因?yàn)檫@棵樹是從圖G中生成出來(lái)的，我們把它叫做生成樹。如果一棵生成樹在所有生成樹屮總權(quán)值最小，我們就把它稱作最小生成樹。1.2求最小生成樹的一般算法解決最小生成樹問(wèn)題有沒有一般的方法呢？下而我們就介紹一種貪心算法。該算法設(shè)置了集合A,該集合一直是某最小生成樹的子集。算法執(zhí)行的每一步，都要決策是否把邊(u,v)添加到集合A屮，能夠添加的條件是保證AU{(u,v)}仍然是最小生成樹的子集。我們稱像(u,v)這樣的邊為A的安全邊，或稱這樣的邊對(duì)集合A是安全的。求最小生成樹的一般算法流程如下：GENERIC-MS

4、T(Gfw)1?A—①2.whileA沒有形成一棵生成樹3?do找出A的一條安全邊(u,v)4.A—AU{(u,v)}5?returnA一開始A為①，顯然滿足最小生成樹子集的條件。之后，每一次循環(huán)都把一條A的安全邊加入A中，A依然是最小生成樹。本節(jié)的余下部分將提出一條確認(rèn)安全邊的規(guī)則(定理1),下一節(jié)將具體討論運(yùn)用這一規(guī)則尋找安全邊的兩個(gè)有效的算法。總權(quán)值圖1一個(gè)圖的割(S,V-S)首先定義幾個(gè)概念。有向圖G=(V,E)的割(S,V-S)是V的一個(gè)分劃。當(dāng)一條邊(u,v)eE的一個(gè)端點(diǎn)屬于S而另一端點(diǎn)屬于V?S,我們說(shuō)邊(u,v)通過(guò)割(S,V?S)。若集合A中沒

5、有邊通過(guò)割，就說(shuō)割不妨礙集合Ao如果某邊是通過(guò)割的具有最小權(quán)值的邊，則稱該邊為通過(guò)割的一條輕邊。如圖1,集合S中的結(jié)點(diǎn)為黑色結(jié)點(diǎn)，集合V?S中的結(jié)點(diǎn)為白色結(jié)點(diǎn)。連接白色和黑色結(jié)點(diǎn)的那些邊為通過(guò)該割的邊。從邊上所標(biāo)的權(quán)值看，邊(d,c)為通過(guò)該割的唯一一條輕邊。子集A包含陰影覆蓋的那些邊，注意，由于A屮沒有邊通過(guò)割，所以割(S,V-S)不妨礙Ao確認(rèn)安全邊的規(guī)則由下列定理給出。定理1設(shè)圖G(V,E)是一無(wú)向連通圖，且在E上定義了相應(yīng)的實(shí)數(shù)值加權(quán)函數(shù)w,設(shè)A是E的一個(gè)子集且包含于G的某個(gè)最小生成樹中，割(S,V?S)是G的不妨礙A的任意割且邊(n,v)是穿過(guò)割(S,V

6、-S)的一條輕邊，則邊(u,v)對(duì)集合A是安全的。證明：設(shè)T是包含A的一最小生成樹。如果T包含輕邊(u,v),則T包含AU{(u,v)},證明就完成了。否則，可設(shè)法建'、/〔另一棵包含AU{(u,v)}的最小生成樹F,(u,v)對(duì)集合A仍然是安全的。圖2最小生成樹「的建立圖2示岀了最小生成樹T'的建立。S屮的結(jié)點(diǎn)為黑色，V?S中的結(jié)點(diǎn)為白色，迦u,v)與T屮從u到v的通路P構(gòu)成一回路。由于迦u,v)通過(guò)割(S,V-S),因此在T中的通路P上至少存在一條邊也通過(guò)這個(gè)割。設(shè)(x,y)為滿足此條件的邊。因?yàn)楦畈环恋KA,所以迦x,y)不屬于Ao又因?yàn)?x,y)處于T中從u

7、到v的唯一通路上，所以去掉邊(x,y)就會(huì)把T分成兩個(gè)子圖。這時(shí)加入邊(u,v)以形成一新的生成樹T=(T-{(x,y)})U{(u,v)}o下一步我們證明F是一棵最小生成樹。因?yàn)?u,v)是通過(guò)割(S,V-S)的一條輕邊，且邊(x,y)也通過(guò)割，所以有w(u,v)Ww(x,y),因此w(F)=w(T)-w(x,y)+w(u,v)寸VjWw(T)。但T是最小生成樹，因此F必定也是最小生成樹。乂因?yàn)門'包含AU{(u,v)},所以(u,v)對(duì)A是安全的。(證畢)通過(guò)定理1可以更好地了解算法GENERIC-MST在連通圖G=(V,E)上的執(zhí)行流程。在算法執(zhí)行過(guò)程屮，集

8、合A始終是