算法合集之《最小生成樹問題的拓展》

1、1012004國家集訓(xùn)隊論文汪汀最小生成樹問題的拓展安徽省蕪湖一中汪汀摘要本文主要論述瑕小生成樹問題屮的兩類拓展一般小度限制生成樹和次小生成樹。首 先分別介紹了這兩類拓展問題的模型，然后提出了求解這兩類問題的算法，/后，通過一些 例子分析其在實際問題屮的應(yīng)用。關(guān)鍵字牛成樹抓展度限制正文址小生成樹是信息學(xué)競賽中的經(jīng)典問題，但近年來，競賽中的題H不再局限J：這類經(jīng)典 模也，難度人人増加。為解決這些問題，我們必須対這些經(jīng)典模梨加以拓展。拓展的類型很 多，本文主耍論述Jt中的兩類一最小度限制生成樹和次小生成樹。1最小生成樹1.1最小生成樹的定義設(shè)G=(V.E.3)是連通的無向圖，G中權(quán)值和最小的生成樹

2、稱為放小生成樹。1.2求解最小生成樹的算法求最小牛成樹，比較常用的算法令Prim算法和Kruskal算法。前者借助Fibonacci堆町 以便復(fù)雜度降為O(Vlog2V+E),后者一般應(yīng)用稀疏圖，其時間復(fù)雜度為0(Elog2V)a2、最小度限制生成樹2.4、最小度限制生成樹的定義對一個加權(quán)的無向圖，在一些滿足卜面性質(zhì)的生成樹：某個特殊的結(jié)點的度等一 個指定的數(shù)值。最小度限制生成樹就是滿足此性質(zhì)II權(quán)值和垠小的-棵生成樹。把它抽彖成數(shù)學(xué)稅型就是：設(shè)G=(V,E,3 )是連通的無向圖，v。GV是特別指定的一個頂點k為給定的一個正整數(shù).如果T是G的一個生成樹且d,<v0)=k,則稱T為G的k度

3、限制生成樹。G中權(quán)值和最小的 k度限制生成樹稱為G的最小k度生成樹。2.2、求解最小度限制生成樹的算法約定:T為圖G的一個生成樹,T+a-b記作(+a.b),如果T+a-b仍然是一個生成樹，則稱(+a.b) 是T的一個可行交換。引理1：設(shè)T.T?是圖G的兩個不同的生成樹，E(T1)E(T2)=aI.a2,a.E(T2)E(T1)=bI.b2,bj則存在一個排序 bihb12,咯,使得 Tz+ej-fjj (j=l,2,n)仍然是G的生成樹。定理1:設(shè)T是G的k度限制生成樹，則T是G的最小k度限制生成樹當(dāng)且僅當(dāng)下面三 個條件同時成立：I對于G中任何兩條與關(guān)聯(lián)的邊所產(chǎn)生的T的可行交換都是不可改進的

4、。 II對于G中任何兩條與不關(guān)聯(lián)的邊所產(chǎn)生的T的可行交換都是不可改進的。DI對于T的任何兩個可行交換(+如,小|)和(+a2,4>2),若亦血與關(guān)聯(lián)，不于 Vo 關(guān)聯(lián)，則有 3 (bj)+ 3 (b2)W 3 仙)+3 (a2)證明：必要性設(shè)T是最小k度限制生成樹，則1,11顯然成立。以下證明III：由I ,1【 可知如果(+a“b2)秋+a2，bj都是T的可行交換,則有3(bJW 3(aJ,3(bi)W 3 (a2)» 故3(b|)+3(b2)W3(aJ+3(a2);否則,或者(+a“b2)或者(+a2,bj不是 T 的 可行交換,根據(jù)引理1, T=T+agH6b2仍然是T的

5、k度限制生成樹,則3 (T)W 3 (T).故 3(bJ+3 (bW 3(ai)+3(a2)。(2)充分性設(shè)T是k度限制生成樹且滿足I JI, IIL假如有另一個k度限制生成樹F, 3(TJV3(T),設(shè)E(T,)E(T)=aba2.,anE(T)E(TXb2,，bn 顯然有E o(ai)<E 3 ©),根據(jù)引理1,存在一個排列br,b2S.bn ,滿足T+arbr 仍然是G的生成樹。由3(TJV3(T)得Z(3(bi )-3(a,)>0,因而,在T的這n 個可行交換中,一定存在某個可以改進的交換(+a,.-bf)o由于T滿足1,11,則 aib若同時與V。關(guān)聯(lián)或不關(guān)聯(lián)都

6、是不町改進的。也就是說，荷和時中必定恰好 何一個不與V。關(guān)聯(lián)。不妨設(shè)與V。無關(guān)聯(lián)，因為D(v。)也等J：k,所以必存在 另一個交換(+aj,bj),滿足與與%關(guān)聯(lián),bj，與無關(guān)聯(lián),11(3(5) 3佝)+(3(切) 一3(丐)>0此與III矛質(zhì)。因此，T，是不存在的，即T是G的最小k度限制生成 樹。定理2：設(shè)T是G的最小k度限制生成樹，E。是G中與有關(guān)聯(lián)的邊的集合，E,=E0E(T), E2=E(T)Eo, A=(+a,-b)l aGE19bGE2> 設(shè)3 (a)一o (b,)=min co (a)(o(b)l (+a,-b)GA» 則T+Hb，是G的一個最小k+1度限制

7、生成樹。第3頁共7頁1012004國家集訓(xùn)隊論文汪汀如何求最小k度限制生成樹呢？首先考電邊界情況。先求出問題有解時k的最小值:把V。點從圖中刪去后，圖中可能會出第4頁共7頁1012004國家集訓(xùn)隊論文汪汀第#頁共7頁1012004國家集訓(xùn)隊論文汪汀現(xiàn)m個連通分屆，而這m個連通分屆必須通過v。來連接，所以，在圖G的所仃生成樹中 dr(vo)$m。也就是說，當(dāng)kvm時，問題無解。再根擁上述定理，得出算法的框架:1先求出最小m度限制生成樹：2由最小m度限制生成樹得到最小m+1度限制生成樹: 3當(dāng)dT(v0)=k時停止。卜面分別考偲每一步首先,將V。和與之關(guān)聯(lián)的邊分別從圖中刪去,此時的圖可能不再連通，

8、對各個連通分量, 分別求最小生成樹。接著，對于每個連通分量V，,求一點Vi，VWVS且3(v6vJ=min 3(%丁)1 WWW，則該連通分最通過邊(jv。)與v()相連。J：是，我們就得到了一個m度限制生成樹, 不難證明，這就是垠小m度限制生成樹。這一步的時間復(fù)雜度為0(Vlog2V+E)我們所求的樹是無根樹，為了解題的簡便，把該樹轉(zhuǎn)化成以為根的有根樹。假設(shè)已經(jīng)得到了最小p度限制生成樹，如何求最小p+1度限制牛成樹呢？根據(jù)定理2,最小p+1度限制生成樹兒宦是由繪小p度限制牛成樹經(jīng)過一次可行交換(+時bj 得到的。我們口然就仃了一個址慕本的想法一枚舉！但是，簡單的枚舉，時間復(fù)雜度高達 0(E:

9、),顯然是不能接受的。深入思考不難發(fā)現(xiàn)，任意町行的交換，必定是一條邊跟V。關(guān)聯(lián), 另一條與V。無關(guān)，所以，只要先枚舉與V。關(guān)聯(lián)的邊，再枚舉另一條邊，然后判斷該交換是 否可行，垠后在所勺町行交換屮取址優(yōu)值即叭J：是時間復(fù)雜度降到了 O(VE),但這仍然不 能令人滿意。進一步分析，在原先的樹中加入條與V。相關(guān)聯(lián)的邊后，必定形成-個環(huán)。 若想得到一棵p+1度限制生成樹，盂刪去一條在環(huán)上的且與無關(guān)聯(lián)的邊。刪去的邊的權(quán) 値越人，則所得到的乞成樹的權(quán)值和就越小。如果每添加一條邊，都需要對壞上的邊一一枚 舉，時間復(fù)雜度將比較高，因為有不少邊晅復(fù)統(tǒng)計多次(卜圖中紅色的邊統(tǒng)計了多次)。這里，動期原鬲如武約*云砧

10、)為路徑V亦蔦;先關(guān)聯(lián)且畑g人的'邊' 定義 fatnv)為 V 的父結(jié)點態(tài)轉(zhuǎn)移Best(viiax)Best(father(v).(J(father(v).y), 邊界條rlJ Bestlvo-Aptfvs-ooWvcbvAEfra !'0(V)：狀態(tài)共I業(yè)二匹汐沛i寸処翌妙/以總應(yīng)迴©妙 故由最小 展溯盛樹得到蘇站奩限制生成樹希詢4樂度為0(V)。綜上 求最小k度限制生成樹算法總的時間復(fù)雜度為0(Vlog2V+E+kV)«3、次小生成樹3. 1、次小生成樹的定義設(shè)G=(V.E.w)是連通的無向圖，T是圖G的一個址小生成樹。如果仃另一棵樹匚，滿 足

11、不存在樹F,3 (F) <3 (T,),則稱Ti是圖G的次小生成樹。3. 2、求解次小生成樹的算法約定：由T進行一次町行交換得到的新的牛成樹所組成的集合，稱為樹T的鄰集，記為N(T)。定理3：設(shè)T是圖G的最小生成樹，如果T滿足3(TJ=mln3(T，)l T，WN(T).則T】是G 的次小生成樹.證明：如果Ti不是G的次小生成樹，那么必定存在另一個生成樹TT'=T使得 3(T)W3(T')v3(TJ,由T的定義式知T不屬于N(T),則E(TJE(T)二am',aj, E(T)E(T)=bhb2.,b«,其中&2。根據(jù)引理 1 知，存在一 個排列b

12、,hbi2.使得T+apb.j仍然是G的生成W. K均屬J-N(T).所以3佝)$ 3(%), 所以3(TJ$3(T+arbij)$3(Tj,故矛盾。所以h是圖G的次小生成樹。通過上述定理，我們就冇了解決次小生成樹問題的基本思路。首先先求該圖的報小牛成樹To時間復(fù)雜度OfVlog2V+E)然后，求T的鄰集屮權(quán)值和最小的生成樹，即圖G的次小生成樹。如采只足簡單的枚舉，復(fù)雜度很奇。|1先枚舉兩條邊的復(fù)雜度是O(VE),再判斷該交換是否 可行的復(fù)雜度是0(V),則總的時間復(fù)雜度是O(VE)c這樣的算法顯得很盲目。經(jīng)過簡單的 分析不難發(fā)現(xiàn)，每加入一條不在樹上的邊，總能形成一個壞，只有刪去壞上的一條邊，

13、才能 保證交換后仍然是生成樹，而刪左邊的權(quán)值越人，新得到的生成樹的權(quán)值和越小。我們町以 以此將復(fù)雜度降為0(VE)o這己經(jīng)前進了一人步，但仍不夠好。冋顧上一個模熨一一最小度限制生成樹，我們也曾面臨過類似的問題，并H.最終采用動態(tài)規(guī) 劃的方法避免了車復(fù)計算，使得復(fù)雜度人人降低。對J：本題，我們町以采用類似的思想。首 先做一步預(yù)處理，求出樹上每兩個結(jié)點Z間的路徑上的權(quán)值最人的邊，然后，枚舉圖屮不在 樹上的邊，令了剛才的預(yù)處理，我們就町以用0(1)的時間得到形成的環(huán)上的權(quán)值址人的邊。 如何預(yù)處理呢？因為這是一棵樹，所以并不需耍什么高深的算法，只耍簡單的BFS即町。 預(yù)處理所要的時間復(fù)雜度為O(V2)

14、<»這樣，這一步時間復(fù)雜度降為O(V2)o綜上所述，次小生成樹的時間復(fù)雜度為0(V')。4x實際問題中的應(yīng)用4.1野餐計劃綾人雖小卻喜歡乘坐巨人的轎乍，轎乍人到可以裝卜無論多少建人。菜犬，N(NW20) 個矮人打算到野外聚餐。為了集中到聚餐地點，煖人A耍么開車到矮人B家中，留|、自己 的轎車在復(fù)人B家，然后乘坐B的轎車同行；要么直接開車到聚餐地點，并將車停放在聚 餐地。雖然綾人的家很人，町以停放無數(shù)杲轎乍，但是聚餐地點卻最多只能停放K輛轎乍。 現(xiàn)在給你一張加權(quán)無向圖，它描述了 N個矮人的家和聚餐地點，耍你求出所有矮人開車的 最短總路程。解答這是一個比較明顯的度限制生成樹

15、的模型，町以把妙人的家和聚餐地看成圖I.的點， 兩個矮人家之間的斗離看成一條帯權(quán)的無向邊，聚餐地為有度限制的點。需要注意的是,本 題是求度不超過k的最小生成樹，不過這并沒仃帶來更人的難度，因為從算法的流程來看我 們很容易得到度不超過k的所有最小度限制生成樹.4.2通訊線路某地區(qū)共仃n座村莊(l<n< 5000),每朋村莊的坐標(biāo)用一對糧數(shù)(x. y)表示，直中0 S x. yS 10000。為了加強聯(lián)系，決定在村莊Z間建工通訊網(wǎng)絡(luò)。通訊匚其可以是需耍鋪設(shè)的普通 線路，也對以是衛(wèi)星設(shè)備。衛(wèi)星設(shè)備數(shù)冰仃限，只能給-部分村莊配備。擁仃衛(wèi)星設(shè)備的兩 座村莊無論相距多遠都可以直接通訊。而互相間

16、鋪設(shè)了線路的村莊也可以通訊。現(xiàn)在仃k 臺(0<k<100)衛(wèi)星設(shè)備，請你編一個程序，計算出應(yīng)該如何分配這k臺衛(wèi)星設(shè)備，才能 使鋪設(shè)線路垠短，并保證每兩朋村莊Z間都町以苴接或間接地通訊。解答首先構(gòu)造圖，把村莊作為圖中的點，村莊間的距離作為邊。如果沒仔或只令一臺衛(wèi)星設(shè)備，就町以目接用最小生成樹來解決。衛(wèi)星設(shè)備的作用實際就是 連接k個點II代價為0 ,不妨設(shè)一個虛點v。，與原圖中的每-個點連接-條代價為0的 邊，V。的度限制為k,再套用度限制生成樹的算法即可。例如下圖:A (10. 60) B(IO.O) C (90, 0)A則新構(gòu)造的圖為:其中.D-r(v()=k43秘密的牛奶運輸Fa

17、rmer John耍把他的牛奶運輸?shù)礁鱾€銷竹點。運輸過程中，可以先把牛奶運輸?shù)揭恍?銷售點，再由這些銷售點分別運輸?shù)狡渌N售點。運輸?shù)目偩嚯x越小，運輸?shù)某杀疽簿驮降?。低成本的運輸是Farmer John所希望的。不過， 他并不想讓他的竟?fàn)帉澯谥浪鸍I體的運輸方案，所以他希塑采用費用笫二小的運輸方案而 不是址小的?，F(xiàn)在請你幫忙找到該運輸方案。解答木題是一個典型的求次小生成樹的模也 可以把銷仕:點看成圖中的點，每兩點間仃一 條加權(quán)的無向邊，邊的權(quán)值為銷代點間的距離。那么，宜接套用上文所講述的求次小牛成樹 的算法即可5、結(jié)語本文主要論述最小生成樹問題的兩個拓展一度限制生成樹和k小生成樹。苴實最小生 成樹問題的拓展是多種多樣的.并非只冇本文所提到的兩種。為然.不僅僅是最小生成樹 其他經(jīng)典模型亦是如此。這就需耍我們在解決實際問題屮，不能拘泥J：經(jīng)典模型，要剛題” 制宜，適當(dāng)?shù)貙?jīng)典模型加以拓展，建立出符介題目本身特點的模型。但足，這并不是說，經(jīng)典模型已經(jīng)被淘汰。