算法合集之《最小生成樹問(wèn)題的拓展》

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

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

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

4、。 II對(duì)于G中任何兩條與不關(guān)聯(lián)的邊所產(chǎn)生的T的可行交換都是不可改進(jìn)的。DI對(duì)于T的任何兩個(gè)可行交換(+如,小|)和(+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假如有另一個(gè)k度限制生成樹F, 3(TJV3(T),設(shè)E(T,)E(T)=aba2.,anE(T)E(TXb2,，bn 顯然有E o(ai)<E 3 ©),根據(jù)引理1,存在一個(gè)排列br,b2S.bn ,滿足T+arbr 仍然是G的生成樹。由3(TJV3(T)得Z(3(bi )-3(a,)>0,因而,在T的這n 個(gè)可行交換中,一定存在某個(gè)可以改進(jìn)的交換(+a,.-bf)o由于T滿足1,11,則 aib若同時(shí)與V。關(guān)聯(lián)或不關(guān)聯(lián)都

6、是不町改進(jìn)的。也就是說(shuō)，荷和時(shí)中必定恰好 何一個(gè)不與V。關(guān)聯(lián)。不妨設(shè)與V。無(wú)關(guān)聯(lián)，因?yàn)镈(v。)也等J：k,所以必存在 另一個(gè)交換(+aj,bj),滿足與與%關(guān)聯(lián),bj，與無(wú)關(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的一個(gè)最小k+1度限制

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

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

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

10、)為路徑V亦蔦;先關(guān)聯(lián)且畑g人的'邊' 定義 fatnv)為 V 的父結(jié)點(diǎn)態(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樂(lè)度為0(V)。綜上 求最小k度限制生成樹算法總的時(shí)間復(fù)雜度為0(Vlog2V+E+kV)«3、次小生成樹3. 1、次小生成樹的定義設(shè)G=(V.E.w)是連通的無(wú)向圖，T是圖G的一個(gè)址小生成樹。如果仃另一棵樹匚，滿 足

11、不存在樹F,3 (F) <3 (T,),則稱Ti是圖G的次小生成樹。3. 2、求解次小生成樹的算法約定：由T進(jìn)行一次町行交換得到的新的牛成樹所組成的集合，稱為樹T的鄰集，記為N(T)。定理3：設(shè)T是圖G的最小生成樹，如果T滿足3(TJ=mln3(T，)l T，WN(T).則T】是G 的次小生成樹.證明：如果Ti不是G的次小生成樹，那么必定存在另一個(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 知，存在一 個(gè)排列b

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

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

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

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

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

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