計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第9章_第1頁(yè)
計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第9章_第2頁(yè)
計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第9章_第3頁(yè)
計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第9章_第4頁(yè)
計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第9章_第5頁(yè)
已閱讀5頁(yè),還剩31頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

PAGE36第9章 圖的最小支撐樹(shù)以圖9-6為例,圖示用Kruskal算法逐步計(jì)算下面各圖的最小支撐樹(shù)。解:(a)aab66dfcg412810539137e(1)66adbfcg412810539137e(2)666adbfcg412810539137e(3)66adbfcg412810539137e(4)666adbfcg412810539137e(5)66adbfcg412810539137e(6)666adbfcg412810539137e(7)66adbfcg412810539137e(8)666adbfcg412810539137e(9)66adbfcg412810539137e(10)666adbfcg412810539137e(11)66adbfcg4537e(12)算法產(chǎn)生的MST(b)4412adbfcg7561114312910e13(1)h412adbfcg7561114312910e13(2)h4412adbfcg7561114312910e13(3)h412adbfcg7561114312910e13(4)h4412adbfcg7561114312910e13(5)h412adbfcg7561114312910e13(6)h4412adbfcg7561114312910e13(7)h412adbfcg7561114312910e13(8)h4412adbfcg7561114312910e13(9)h412adbfcg7561114312910e13(10)h4412adbfcg7561114312910e13(11)h412adbfcg7561114312910e13(12)h4412adbfcg75639e(13)最后的MSTh以圖9-8為例,圖示用Prim算法逐步計(jì)算下面各圖的最小支撐樹(shù)。我們假設(shè)起始點(diǎn)為a。66adbfcg5981010h4137e(b)88766116adbfcg498105h11137e(a)9677解:(a)66d=0=niladbfcg498105h11137e(0)初始化967d==nild==nild==nild==nild==nild==nild==nil76d=0=niladbfcg498105h11137e(1)選a,更新b,c,d,e967d=5=ad==nild==nild==nild=13=ad=6=ad=9=a766d=0=niladbfcg498105h11137e(2)選d,更新e,f967d=5=ad=11=dd==nild==nild=13=ad=6=ad=7=d76d=0=niladbfcg498105h11137e(3)選b,更新c967d=5=ad=11=dd==nild==nild=10=bd=6=ad=7=d766d=0=niladbfcg498105h11137e(4)選e,更新c,f,g967d=5=ad=9=ed==nild=6=ed=7=ed=6=ad=7=d76d=0=niladbfcg498105h11137e(5)選g,更新f,h967d=5=ad=8=gd=7=gd=6=ed=7=ed=6=ad=7=d766d=0=niladbfcg498105h11137e(6)選c,沒(méi)有更新點(diǎn)967d=5=ad=8=gd=7=gd=6=ed=7=ed=6=ad=7=d76d=0=niladbfcg498105h11137e(7)選h,更新f967d=5=ad=4=hd=7=gd=6=ed=7=ed=6=ad=7=d766d=0=niladbfcg498105h11137e(8)選f,沒(méi)有更新點(diǎn)967d=5=ad=4=hd=7=gd=6=ed=7=ed=6=ad=7=d7adbfcg45h7e(9)最后的MST,總權(quán)值為426776(b)66adbfcg5981010h4137e(0)初始化8876611d==nild==nild==nild==nild=0=nild==nild==nild==nil6adbfcg5981010h4137e(1)選a,更新b,c,g8876611d=10=ad==nild==nild==nild=0=nild=4=ad=11=ad==nil66adbfcg5981010h4137e(2)選c,更新b,d,g,h8876611d=9=cd==nild==nild=6=cd=0=nild=4=ad=10=cd=8=c6adbfcg5981010h4137e(3)選h,更新g,f8876611d=9=cd==nild=13=hd=6=cd=0=nild=4=ad=7=hd=8=c66adbfcg5981010h4137e(4)選g,更新e8876611d=9=cd=6=gd=13=hd=6=cd=0=nild=4=ad=7=hd=8=c(5)選e,更新b,d,f6adbfcg5981010h4137e8876611d=8=ed=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e66adbfcg5981010h4137e(6)選f,無(wú)更新點(diǎn)8876611d=8=ed=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e6adbfcg5981010h4137e(7)選d,更新b8876611d=7=dd=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e66adbfcg5981010h4137e(8)選b,無(wú)更新點(diǎn)8876611d=7=dd=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e6adbfcg5h47e(9)最后的MST,總權(quán)值為41766我們知道,如果一圖中所有邊的權(quán)都一樣,那么任何一個(gè)支撐樹(shù)都是一個(gè)最小支撐樹(shù)并且可以用廣度優(yōu)先或者深度優(yōu)先算法求得?,F(xiàn)在,假設(shè)圖G(V,E)中邊的權(quán)不完全一樣,但是只有兩種,要么是w(>0)或者是2w。有個(gè)教授提出下面的算法:Smart-MST(G(V,E))在每一條有權(quán)2w的邊(u,v)中間插入一新點(diǎn)p,把邊(u,v)變成兩條邊,(u,p)和(p,v),并給每條邊以權(quán)值w,即w(u,p)=w(p,v)=w。我們把這個(gè)改變后的圖記為G’。用BFS算出G’的支撐樹(shù)T’。把T’中所有在第一步新插入的點(diǎn)去掉,即再把(u,p)和(p,v)并為一條邊(u,v)。剩下的圖為G的MST。請(qǐng)證明這個(gè)算法正確或證明不正確。解:這個(gè)算法不正確。下面圖給出一反例。下圖(a)是原圖G,圖(b)是在每條權(quán)為2w的邊中插入一點(diǎn)后的圖G’,圖(c)是用BFS后得到的支撐樹(shù)T’。顯然,把插入點(diǎn)移走后的T’不是MST。ww2wwacbwwwacb·wwwacb·w(a)(b)(c)假設(shè)邊(u,v)是加權(quán)的連通圖G(V,E)中權(quán)值最小的一條邊。證明邊(u,v)一定會(huì)出現(xiàn)在某個(gè)最小支撐樹(shù)中。進(jìn)一步,如果這條邊的權(quán)比任何其他的邊都絕對(duì)地小,即沒(méi)有另一與之權(quán)相等的邊,那么,任何一個(gè)最小支撐樹(shù)都含有這個(gè)邊。證明:考慮以頂點(diǎn)u為一邊的割C=({u},V-{u})。因?yàn)橐婚_(kāi)始的子集A為空集,那么這個(gè)割顯然尊重A。因?yàn)檫?u,v)的權(quán)最小,它必定是一個(gè)最小交叉邊,因而是一條安全邊。根據(jù)定理9.1,通用算法第一步就可把邊(u,v)選入集合A,所以這條邊一定會(huì)出現(xiàn)在某個(gè)最小支撐樹(shù)中。進(jìn)一步,如果這條邊的權(quán)比任何其他的邊都絕對(duì)地小,那么,任何一個(gè)最小支撐樹(shù)都含有這個(gè)邊。我們可以用反證法來(lái)證。假設(shè)樹(shù)T是一個(gè)MST,它不含邊(u,v)。那么把邊(u,v)加到這個(gè)MST中后形成一回路(見(jiàn)下圖)。uuvxT是一個(gè)MSTy(u,v)T刪除回路上一條邊(x,y)后我們得到一個(gè)支撐樹(shù)T’,T’=T{(u,v)}-{(x,y)}。因?yàn)?u,v)權(quán)最小,w(u,v)<w(x,y),所以有W(T’)=W(T)+w(u,v)-w(x,y)<W(T)。這與T是最小支撐樹(shù)相矛盾。所以,任何一個(gè)最小支撐樹(shù)都含有這個(gè)權(quán)最小的邊(u,v)。假設(shè)C是加權(quán)的連通圖G(V,E)中的一個(gè)回路,邊(u,v)是回路中權(quán)值最大的一條邊,那么一定會(huì)有某個(gè)最小支撐樹(shù)不含有邊(u,v)。證明: 假設(shè)T是連通圖G(V,E)的一個(gè)最小支撐樹(shù)。如果T不含有邊(u,v),則證明完成。所以,為了用反證法,我們假定T含有邊(u,v)?,F(xiàn)在,如果我們把邊(u,v)從T中刪除,則把T分裂為兩個(gè)不相交的子樹(shù)T1和T2,而且u和v分屬兩邊。不坊設(shè)uT1,vT2(見(jiàn)下圖(a))。再考慮把邊(u,v)從回路C中去掉后的路徑,P=C–{(u,v)},它的兩端為u和v。如果我們沿著路徑P從頂點(diǎn)u到頂點(diǎn)v走的話,一定會(huì)碰上一條邊(x,y)使得xT1,yT2(見(jiàn)下圖(b))。顯然T’=(T–{(u,v)}{(x,y)}也是一個(gè)支撐樹(shù)。因?yàn)閣(x,y)≤w(u,v),我們有W(T’)=W(T)-w(u,v)+w(x,y)≤W(T)。所以T’也必定是一個(gè)最小支撐樹(shù),否則矛盾。因?yàn)門’不含有邊(u,v),命題得證。(a)設(shè)計(jì)一個(gè)計(jì)算加權(quán)連通圖G(V,E)的最小支撐樹(shù)T的算法使它含有圖中某一條指定的邊(a,b)。也就是說(shuō),T是所有含邊(a,b)的支撐樹(shù)中權(quán)值最小的一個(gè)。你需要證明其正確性。(b)設(shè)計(jì)一個(gè)計(jì)算加權(quán)連通圖G(V,E)的最小支撐樹(shù)T的算法使它含有圖中一個(gè)邊的子集A。其中,子集A不包含回路。也就是說(shuō),T是所有含子集A的支撐樹(shù)中權(quán)值最小的一個(gè)。你需要證明其正確性。解: (a)算法如下:MST-Variation-1(G(V,E),a,b) //邊(a,b)Ez?min{w(u,v)|(u,v)?E} //找出邊里面最小的權(quán)值z(mì)k?w(a,b) //k是邊(a,b)的權(quán)值,顯然有zkw(a,b)?z–1 //把邊(a,b)的權(quán)值改為z-1后,它的權(quán)值最小用Kruskal或Prim算法找出變更后的圖G’的MST //w(a,b)=z–1是唯一的變化w(a,b)?k //恢復(fù)w(a,b)原來(lái)的值returnMST //這個(gè)MST就是解正確性證明:考慮算法第4行中變更后的圖G’,它與圖G的唯一區(qū)別是邊(a,b)的權(quán)值不同。在圖G’中,邊(a,b)的權(quán)值是w’(a,b)=z–1。讓我們用T’表示圖G’的最小支撐樹(shù);用T表示算法產(chǎn)生的支撐樹(shù);用T*表示原圖G的任一個(gè)含邊(a,b)的支撐樹(shù)。我們需要證明:邊(a,b)一定在T中。W(T)W(T*)。先證明(1)。算法的第4行得到圖G’的最小支撐樹(shù)T’,因?yàn)閣’(a,b)=z–1有最小的權(quán)值,習(xí)題4證明了邊(a,b)一定在T’中。為完整起見(jiàn),這里再用反證法證一下。假設(shè)邊(a,b)不在T’中,那么刪去T’中從a到b的路徑上一條邊(x,y),再把邊(a,b)加進(jìn)來(lái),就得到另一個(gè)支撐樹(shù)T’’(見(jiàn)下圖)。因?yàn)閣’(a,b)=z–1<w(x,y),所以有W(T’’)=W(T’)-w(x,y)+w’(a,b)<W(T’)。這與T’是MST矛盾,所以邊(a,b)一定在T’中,那么,也就在支撐樹(shù)T中了。接著,我們證明(2)。假設(shè)T*是原圖G的任何一個(gè)含邊(a,b)的支撐樹(shù)。如果我們把T*里的邊(a,b)的權(quán)值換為(z–1),那么T*就變成一個(gè)G’的的支撐樹(shù),但不一定是最小。因?yàn)門’是圖G’的MST,所以有W(T’)W(T*)–k+(z–1) (1)因?yàn)樗惴óa(chǎn)生的支撐樹(shù)T是把T’中邊(a,b)的權(quán)值換為k,所以有W(T)=W(T’)+k-(z–1) (2)把式(1)代入式(2),得 :W(T)=W(T’)+k-(z–1)(W(T*)–k+(z–1))+k-(z–1)=W(T*)。(b) 算法如下:MST-Variation-2(G(V,E),A)z?min{w(u,v)|(u,v)?E}G’(V’,E’)?G(V,E) //復(fù)制一個(gè)考貝A’?Aforeachedge(a’,b’)A’ w(a’,b’)?z–1 //把A’中,也就是A中每條邊的權(quán)值都變成z–1endfor用Kruskal或Prim算法找到圖G’的MST,記為T’T?foreachedge(a’,b’)inT’ TT{(a,b)} //T是原圖中同樣邊組成的樹(shù)endforreturnT End正確性證明:顯然,算法中,圖G’是把集合A中每一條邊的權(quán)值改為z-1而得到的。首先證明A’一定在T’中。如果其中有任何一條邊(a,b)A’不在T’中,那么把(a,b)加到T’中形成一回路。因?yàn)锳’中邊不形成回路,回路中一定會(huì)有不在A’中邊。那么,和上面(a)部分證明一樣,把這條邊換為(a,b)后可得權(quán)更小的支撐樹(shù)而矛盾。所以A’T’。從而有AT。假設(shè)T*是原圖G中任一個(gè)含子集A的支撐樹(shù)。如果我們T*中子集A的每一條邊的權(quán)值改為z-1,那么我們就得到一個(gè)圖G’的支撐樹(shù),但不一定最小。因?yàn)門’是G’的MST,所以有:W(T’)W(T*)-W(A)+|A|(z-1) (1)因?yàn)樗惴óa(chǎn)生的支撐樹(shù)T是把T’中子集A的每一條邊的權(quán)值從z-1改為它原來(lái)的的權(quán)值,所以有:W(T)=W(T’)+W(A)-|A|(z-1) (2)把式(1)代入式(2),得: W(T)=W(T’)+W(A)-|A|(z-1)(W(T*)-W(A)+|A|(z-1))+W(A)-|A|(z-1)=W(T*)。所以,算法產(chǎn)生的支撐樹(shù)T是所有含子集A的支撐樹(shù)中權(quán)值最小的一個(gè)。(a) T和T’是同一個(gè)連通圖G的兩個(gè)不同支撐樹(shù)。假設(shè)邊x是T的一條邊但不是T’里的邊。證明在T’中存在一條邊y不屬T,并且(T-{x}){y}和(T’-{y}){x}都是G的支撐樹(shù)。(b) 假設(shè)一個(gè)圖G的所有邊的權(quán)值都兩兩不等,證明它只能有唯一的一個(gè)最小支撐樹(shù)。證明:(a)假定x=(u,v)。如下圖(a)所示,把x從T里刪去后,T分裂為T1和T2兩個(gè)子樹(shù),并且uT1和vT2。 讓V1表示T1中頂點(diǎn)的集合,V2表示T2中頂點(diǎn)的集合,那么C=(V1,V2)是一個(gè)割。如果我們沿著在T’中從頂點(diǎn)u到頂點(diǎn)v的路徑走的話,我們一定會(huì)碰到一條穿越這個(gè)割的交叉邊y=(a,b)使得aV1和bV2。顯然(T-{x}){y}構(gòu)成一個(gè)支撐樹(shù)。把y從T’中刪去后,T’分裂為兩個(gè)子樹(shù),頂點(diǎn)a和b分屬兩邊,并且頂點(diǎn)u和a在同一邊,v和b在同一邊,而邊x=(u,v)連接這兩個(gè)子樹(shù)。因此,(T’-{y}){x}也是一個(gè)支撐樹(shù),證畢。(b) 我們用反證法。假設(shè)圖G有兩個(gè)不同的最小支撐樹(shù)T和T’。因?yàn)椴煌?,一定有一條邊xT,但xT’。根據(jù)(a)題的結(jié)果,在T’中存在一條邊y不屬T,并且(T-{x}){y}和(T’-{y}){x}都是G支撐樹(shù)。因?yàn)镚的所有邊的權(quán)都兩兩不等,w(x)w(y)。不失一般性,假設(shè)w(x)>w(y)。那么,T*=(T-{x}){y}的權(quán)值為W(T*)=W(T)–w(x)+w(y)<W(T)。這與T是一個(gè)最小支撐樹(shù)相矛盾。所以,圖G只能有唯一的一個(gè)最小支撐樹(shù)。假設(shè)圖G(V,E)的最小支撐樹(shù)是T。假設(shè)我們把圖中一條不在T中的某條邊(u,v)(T)的權(quán)減少。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)算法,把T進(jìn)行適當(dāng)修改,從而得到對(duì)應(yīng)於上述修改后圖的最小支撐樹(shù)。你需要證明你的算法的正確性。解: 假設(shè)邊(u,v)T的權(quán)w(u,v)減少為w*(u,v)<w(u,v)。修改后的圖的最小支撐樹(shù)可以用下面算法從T得到。MST-for-modified-graph(G,T,w*(u,v))沿著T里面從頂點(diǎn)u到頂點(diǎn)v的唯一路徑p(u,v),逐條邊檢查找出權(quán)值最大的邊e。ifw(e)>w*(u,v) thenT*Tè{(u,v)}–{e} elseT*TendifreturnT*因?yàn)樗惴ǖ谝徊娇梢詫?duì)最小支撐樹(shù)T作一次從頂點(diǎn)u開(kāi)始的DFS搜索實(shí)現(xiàn),所以算法的復(fù)雜度為O(n),這里n=|V|。正確性證明:顯然,算法輸出的T*是按題意修改后圖的一棵支撐樹(shù)。我們用W(T)表示原來(lái)圖的最小支撐樹(shù)的總權(quán)值,而用W(T*)表示上面算法產(chǎn)生的支撐樹(shù)的總權(quán)值。顯然,如果w(e)>w*(u,v),我們有W(T*)=W(T)+w*(u,v)–w(e)<W(T),否則有W(T*)=W(T)W(T)+w*(u,v)–w(e)。所以,任何情況下有:W(T*)W(T)和W(T*)W(T)+w*(u,v)–w(e) (1)假設(shè)Tmod是修改后的圖的任何一個(gè)支撐樹(shù),我們證明W(T*)W(Tmod)。我們分兩種情況討論如下。Tmod不含邊(u,v)。如果是這種情況,Tmod也是圖未改動(dòng)前的一個(gè)支撐樹(shù),所以必有W(T)W(Tmod)。由上面(1)式,W(T*)W(T),所以有W(T*)W(Tmod)。Tmod含有邊(u,v)。如果是這種情況,如下圖所示,我們把邊(u,v)從Tmod刪除以后會(huì)得到兩個(gè)不相交子樹(shù)T1和T2。那么,在原圖G的最小支撐樹(shù)T里面,從頂點(diǎn)u到頂點(diǎn)v的唯一路徑p(u,v)上一定含有一條邊(a,b)使得a?T1和b?T2。這條邊加上T1和T2也形成一個(gè)支撐圖T’={(a,b)}T1T2=Tmodè{(a,b)}–{(u,v)},并且有關(guān)系W(T’)=W(Tmod)+w(a,b)-w*(u,v)。因?yàn)門’不含有邊(u,v),它是原來(lái)圖中的一個(gè)支撐樹(shù),所以有W(T)W(T’),也就是,W(T)W(Tmod)+w(a,b)-w*(u,v) (2)由上面(1)式,我們有W(T*)W(T)+w*(u,v)–w(e)。把(2)式代入后,我們得到:W(T*)W(T)+w*(u,v)–w(e)[W(Tmod)+w(a,b)-w*(u,v)]+w*(u,v)–w(e)=W(Tmod)+w(a,b)-w(e)。W(Tmod) (因?yàn)檫卐也在路徑p(u,v)上,且有w(e)w(a,b)。)這就證明了,對(duì)于按題意修改后的圖的任何一個(gè)支撐樹(shù)Tmod,都有W(T*)W(Tmod)。那么,T*必定是一棵修改后的圖的最小支撐樹(shù)。與最小支撐樹(shù)對(duì)稱的一個(gè)概念是最大支撐樹(shù)。一個(gè)加權(quán)連通圖的最大支撐樹(shù)就是具有最大權(quán)值的支撐樹(shù)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度好的,計(jì)算一個(gè)加權(quán)連通圖G(V,E)的最大支撐樹(shù)的算法。解: 一個(gè)簡(jiǎn)單算法如下。Maximum-SP(G(V,E))從圖G構(gòu)造圖G’。G’是把G中每條邊的權(quán)值加上負(fù)號(hào)取得。用Kruskal算法或Prim算法得到G’的最小支撐樹(shù)T’把T’中每條邊的權(quán)改回原來(lái)的值,即去掉每條邊上所加負(fù)號(hào),得到圖G的支撐樹(shù)TReturnT因?yàn)橥瑯右粋€(gè)支撐樹(shù)T在圖G’中的權(quán)是它在圖G中的權(quán)取反,所以G’的最小支撐樹(shù)恰恰是G的最大支撐樹(shù)。所以算法正確。算法復(fù)雜度與最小支撐樹(shù)算法一樣。下面是兩個(gè)計(jì)算最小支撐樹(shù)的算法的偽碼。對(duì)每一個(gè)算法,如果正確,請(qǐng)證明其正確性,并討論如何有效地實(shí)現(xiàn)它;否則,用反例證明其不正確。我們假定圖G(V,E)是個(gè)加權(quán)連通圖。MST-A(G(V,E))Sortedgessuchthate1e2…emT?Efori1tom //按排好順序依次檢查每條邊 ifT–{ei}仍是一個(gè)連通圖 thenT?T–{ei} endifendforreturnTEndMST-B(G(V,E))T?foreachedgee,takeninarbitraryorder //以任意順序逐條邊檢查 ifTè{e}hasnocycles thenT?Tè{e} endifendforreturnTEnd解:(a)這個(gè)算法正確。我們先用歸納法證明,當(dāng)算法每次從T中刪去一條邊e=(u,v)時(shí),T–{e}仍然含有一個(gè)MST。歸納基礎(chǔ):開(kāi)始時(shí),圖G(V,E)是個(gè)加權(quán)連通圖,含有一個(gè)MST。所以,在第3行的循環(huán)前,T=E含有一個(gè)MST。歸納步驟:假設(shè)算法從T中刪去k條邊后,k0,剩下的圖是T’并且含有一個(gè)MST?,F(xiàn)在證明,如果算法在圖T’中再刪去一條邊e’,T’–{e’}仍然含有一個(gè)MST。由算法知,T’–{e’}是個(gè)連通圖。這意味著T’中有一個(gè)含有e’的回路C’??蓴喽?,回路中e’的權(quán)值最大。這是因?yàn)?,如果回路中有比e’的權(quán)值大的邊,那么它應(yīng)該在先前被檢查過(guò)并且被刪去。所以,根據(jù)第5題的結(jié)果,T’–{e’}含有一個(gè)MST。歸納成功。由上面證明的結(jié)果知,算法輸出的T含有一個(gè)MST?,F(xiàn)在,我們只需證明,T是一棵樹(shù)即可。這是顯然的。首先,T是連通的,因?yàn)槊恳徊蕉急WC了T的連通性。第二,T必不含回路。否則,回路中權(quán)最大的邊在被檢查時(shí)未被刪去,與算法矛盾。因此,最后的T必定是一棵樹(shù),那么它必定是一個(gè)MST,算法正確。這個(gè)算法的第一步可用任一已知的排序算法在O(mlgn)時(shí)間完成。檢查一個(gè)圖的連通性可以用BFS或DFS在O(m)時(shí)間完成。因?yàn)橛衜條邊要檢查,這樣做,算法需要O(m2)時(shí)間。(b)這個(gè)算法不正確。下圖給出一反例。下圖(a)是一個(gè)加權(quán)的連通圖。如果我們按順序(a,b),(b,c),(c,d),(d,a)檢查邊的話,會(huì)得到一個(gè)圖(b)中的支撐圖。這不是最小支撐樹(shù)。假設(shè)G(V,E)是一個(gè)加權(quán)的連通圖并有|V|=n,|E|=m。又設(shè)每條邊e上的權(quán)為1到W之間的某個(gè)整數(shù),1w(e)W,這里W是一個(gè)正整數(shù)的常數(shù)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)復(fù)雜度為O(m)的算法計(jì)算圖G的最小支撐樹(shù)。解: 我們采用Prim算法但需要設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)Q使得Extract-Min(Q)和更新d(v)可以很快。因?yàn)?w(e)W,所以d(v)[0,W]。我們把具有相同權(quán)值的頂點(diǎn)組織為一個(gè)集合或鏈表。具體來(lái)說(shuō),我們定義:L[k]={u|d(u)=k}(0£k£W)和L[W+1]={u|d(u)=¥}。我們用鏈表把每個(gè)集合中頂點(diǎn)鏈接起來(lái)。一開(kāi)始,L[0]={s},L[W+1]=V–{s},L[k]=,k?{1,2,…,W}。這些鏈表的總和組成Q。每當(dāng)算法需要做Extract-Min(Q)時(shí),我們就順序搜索L[0],L[1],L[2],…,直到找到一個(gè)非空的鏈表L[k]。那么,這個(gè)鏈表中任一頂點(diǎn)v的d(v)值等于k,并且必定是最小的。我們?nèi)〕鲈撴湵碇惺醉?xiàng)。這一步最多需要查看W+2個(gè)鏈表,時(shí)間為O(W)=O(1)。因總共需要做n次循環(huán),這部分總時(shí)間為O(n)。當(dāng)一個(gè)頂點(diǎn)u的d(u)值需要從k更新到p<k時(shí),我們只需把頂點(diǎn)u從鏈表L[k]摘下來(lái),然后掛到鏈表L[p]上去即可。因此每一次更新只需O(1)時(shí)間。因?yàn)槲覀冃枰疃?m次更新,所以算法的復(fù)雜度是O(n)+O(m)=O(m)。下面是該算法偽碼。Modified-Prim’s-Algorithm(G(V,E),s)foreachv?V d(v)?¥ p(v)?nil mark(v)F //表示點(diǎn)v還沒(méi)有加入到樹(shù)A中endfor d(s)?0A? ConstructT(V,A)fork1toW L[k]? //初始化鏈表,建立指向鏈表L[k]的指針,首項(xiàng)為空endforL[0]?{s}L[W+1]V–{s}forj1ton //循環(huán)n次,每次取一個(gè)頂點(diǎn)和一條邊 i?0 whileL[i]=? i?i+1 endwhile u?ExtractheadfromL[i] //從L[i]中刪除首項(xiàng) A?Aè{(p(u),u)} //如果p(u)=nil,A不變,否則,A加一條安全邊 mark(u)T foreachv?Adj(u) ifmark(v)=Fandw(u,v)<d(v) //更新u的鄰居v then p(v)?u k?d(v) L[k]?L[k]-{v} //從L[k]中刪除點(diǎn)v d(v)?p?w(u,v) //更新d(v) L[p]?L[p]è{v} //在L[p]尾部插入點(diǎn)v endif endforendforreturnT(V,A)End根據(jù)上面討論,該算法的時(shí)間復(fù)雜度是O(m)。(最寬路徑問(wèn)題)在加權(quán)連通圖G(V,E)的一條路徑上權(quán)值最小的一條邊稱為這條路徑的瓶頸,而這條路徑的寬度定義為它的一條瓶頸邊的權(quán)值。例如,下圖中路徑<a,b,e,g>的瓶頸是邊(b,e),這條路徑的寬度為w(b,e)=7。圖G(V,E)中從頂點(diǎn)u到頂點(diǎn)v的所有路徑中寬度最大的一條路徑稱為從u到v的最寬路徑。例如下圖中從a到g的最寬路徑是<a,b,c,d,f,g>,其寬度是8。假設(shè)T是G(V,E)的最大支撐樹(shù)(定義見(jiàn)第9題),證明T中任意兩點(diǎn)之間的路徑都是G(V,E)中這兩點(diǎn)間的最寬路徑。證明:為了用反證法證明,假設(shè)P(u,v)是T中一條從頂點(diǎn)u到頂點(diǎn)v的路徑但不是G中從u到v的最寬路徑,而路徑P*(u,v)才是最寬路徑。我們證明這會(huì)導(dǎo)致矛盾。假設(shè)邊(x,y)和邊(x*,y*)分別是P(u,v)和P*(u,v)的瓶頸。那么,必有關(guān)系w(x,y)<w(x*,y*)≤P*(u,v)上任一條邊的權(quán)。如下圖所示,如果我們把邊(x,y)從T中刪除,T便分裂為兩個(gè)不相交子樹(shù)T1和T2,并且假設(shè)x和u屬於T1而y和v屬於T2。那么,路徑P*(u,v)必定經(jīng)過(guò)一條連接T1和T2的邊(a,b)。那么,T’=T1T2{(a,b)}便是一個(gè)支撐樹(shù)并有權(quán)值W(T’)=W(T1)+W(T2)+w(a,b)=W(T1)+W(T2)+w(x,y)+[w(a,b)-w(x,y)]=W(T)+[w(a,b)-w(x,y)]因?yàn)槁窂絇*(u,v)的寬度比P(u,v)寬,我們有w(x,y)<w(a,b),從而有W(T’)=W(T)+[w(a,b)-w(x,y)]>W(T),這與T是最大支撐樹(shù)矛盾。重新考慮第11題,不同的是,題中W不再是常數(shù),而是一個(gè)任意的正整數(shù)。我們把題目重述如下。假設(shè)G=(V,E)是一個(gè)加權(quán)的連通圖并有|V|=n,|E|=m。又設(shè)每條邊e上的權(quán)為1到W之間的某個(gè)整數(shù),1w(e)W,這里W是一個(gè)任意的正整數(shù)。修改Prim算法使得最小支撐樹(shù)可以在O(nW+m)時(shí)間內(nèi)算出。*解釋如何設(shè)計(jì)一個(gè)O(mlgW)算法找到這個(gè)圖的最小支撐樹(shù)(不需詳細(xì)偽碼)。(提示:用紅黑樹(shù)。)解:(a) 算法與第11題的解相同。我們重寫在下面,但復(fù)雜度的分析不同。我們定義集合L[k]={u|d(u)=k}(0£k£W)和L[W+1]={u|d(u)=¥}。我們用鏈表把每個(gè)集合中頂點(diǎn)鏈接起來(lái)。一開(kāi)始,L[0]={s},L[W+1]=V–{s},L[k]=,k?{1,2,…,W}。這些鏈表的總和組成Q。每當(dāng)算法需要做Extract-Min(Q)時(shí),我們就順序搜索L[0],L[1],L[2],…,直到找到一個(gè)非空的鏈表L[k]。那么,這個(gè)鏈表中任一頂點(diǎn)v的d(v)值必定是k,并且是最小的。我們?nèi)〕鲈撴湵碇惺醉?xiàng)。這一步最多須要查W+2個(gè)鏈表,時(shí)間為O(W)。因總共需要做n次循環(huán),這部分總時(shí)間為O(nW)。當(dāng)一個(gè)頂點(diǎn)u的d(u)值需要從k更新到p<k時(shí),我們只需把頂點(diǎn)u從鏈表L[k]摘下來(lái),然后掛到鏈表L[p]上去即可。因此每一次更新只需O(1)時(shí)間。因?yàn)橐还灿蠴(m)個(gè)更新操作,所以算法的復(fù)雜度為O(nW+m)。下面是該算法偽碼。Modified-Prim’s-algorithm(G(V,E),s)foreachv?V d(v)?¥ p(v)?nil mark(v)Fendford(s)?0A? ConstructT(V,A)fork=1toW L[k]? //初始化鏈表,建立指向鏈表L[k]的指針,首項(xiàng)為空endforL[0]?{s}L[W+1]=V–{s}forj1ton i?0 whileL[i]=? i?i+1 endwhile u?ExtractheadfromL[i] //從L[i]中刪除首項(xiàng) A?Aè{(p(u),u)} //加一條安全邊。u=s時(shí),p(u)=nil,不操作 mark(u)T foreachv?Adj(u) ifmark(v)=Fandw(u,v)<d(v) //更新u的鄰居v then p(v)?u k?d(v) L[k]?L[k]-{v} //從L[k]中刪除點(diǎn)v d(v)?p?w(u,v) L[p]?L[p]è{v} //在L[k]尾部插入點(diǎn)v endif endforendforreturnT(V,A)End(b) 如果照上面(a)部分做法,為每一個(gè)權(quán)值k,建一個(gè)鏈表L[k](0£k£W+1)那么算法復(fù)雜度至少是(W)。因?yàn)閃可以是任意大正數(shù),這樣做不能滿足O(nlgW)要求。所以,我們的做法是,僅當(dāng)權(quán)值k確實(shí)出現(xiàn)在某條邊上,才建鏈表L[k]。我們用紅黑樹(shù)(參見(jiàn)附錄A)作為數(shù)據(jù)結(jié)構(gòu)。如果樹(shù)中有W個(gè)內(nèi)結(jié)點(diǎn),那么紅黑樹(shù)可以在O(lgW)時(shí)間內(nèi)完成以下操作:尋找紅黑樹(shù)里是否有結(jié)點(diǎn)含有關(guān)鍵字x,RB-Search(T,x)插入一個(gè)關(guān)鍵字x,RB-Insert(T,x)刪除一個(gè)關(guān)鍵字x,RB-Delete(T,x)尋找紅黑樹(shù)里最小的關(guān)鍵字x,RB-min(T,x)初始時(shí),我們建立兩個(gè)鏈表:L[0]?{s}L[]=V–{s}。這里L(fēng)[k]表示是所有d(v)=k的頂點(diǎn)組成的鏈表。然后初始化紅黑樹(shù)T,使它含有兩個(gè)內(nèi)結(jié)點(diǎn),一個(gè)含有指向L[0]的指針,另一個(gè)含有指向L[]的指針。其它的初始化與上面(a)部分同。當(dāng)我們需要Extract-min(Q)時(shí),我們可如下操作:kRB-min(T,x)uheadofL[k] //鏈表L[k]首項(xiàng)對(duì)應(yīng)頂點(diǎn)udeleteufromL[k] //把頂點(diǎn)u從L[k]刪除ifL[k]= thenRB-Delete(T,k) //這時(shí),T(V,A)之外沒(méi)有d(v)=k的頂點(diǎn)endif當(dāng)我們需要把頂點(diǎn)v的d(v)值,從d(v)=k更新為d(v)=p時(shí),p<k,我們可如下操作:deletevfromL[k]ifL[k]= thenRB-Delete(T,k)endififRB-Search(T,p)=true //紅黑樹(shù)中有指向L[p]的指針,L[p]非空 then L[p]L[p]{v} //插入點(diǎn)v else L[p] //建立并初始化鏈表L[p] L[p]L[p]{v} //含一個(gè)頂點(diǎn)v RB-Insert(T,p) //紅黑樹(shù)中插入指向L[p]的指針endif由以上討論可見(jiàn),紅黑樹(shù)里結(jié)點(diǎn)都指向不同的鏈表,所以內(nèi)結(jié)點(diǎn)的個(gè)數(shù)最多是W,當(dāng)然,也不會(huì)大于m。再有,每個(gè)操作,不論是Extract-min(Q)還是更新d(v),都需要最多O(lgW)時(shí)間。因?yàn)榭偣灿衝個(gè)Extract-min(Q)操作和O(m)個(gè)更新操作,所以算法的復(fù)雜度為O(nlgW+mlgW)=O(mlgW)。如果加權(quán)連通圖G(V,E)的一個(gè)支撐子圖由k棵樹(shù)組成,則稱為k-樹(shù)支撐森林。一個(gè)支撐樹(shù)則是k=1時(shí)支撐森林的一個(gè)特殊情況。最小k-樹(shù)支撐森林是具有最小權(quán)值的一個(gè)k-樹(shù)支撐森林。證明下面計(jì)算最小2-樹(shù)支撐森林的算法正確Minimum-2-Tree-Spanning-Forest(G(V,E))用Kruskal或Prim算法計(jì)算G(V,E)的一個(gè)最小支撐樹(shù)T找出T中有最大權(quán)值的邊eFT–{e}returnFEnd請(qǐng)?jiān)O(shè)計(jì)一個(gè)高時(shí)效的計(jì)算圖G(V,E)的最小k-樹(shù)支撐森林(k2)的算法并證明其正確性和分析其復(fù)雜度。解: (a)我們用反證法證明。假設(shè)T和F分別是上面算法得到的最小支撐樹(shù)和2-樹(shù)支撐森林,但F的權(quán)值不是最小的。設(shè)最小2-樹(shù)支撐森林是F*,它含有兩個(gè)樹(shù)T1和T2,并有W(F)>W(T1)+W(T2)。T1和T2對(duì)應(yīng)了一個(gè)頂點(diǎn)的分割C={P,V-P},其中P包含T1中的所有頂點(diǎn),而V-P包含T2中的所有頂點(diǎn)。設(shè)E*為所有交叉邊的集合,即E*={(u,v)E|uT1,vT2}。那么,因T中有從T1中點(diǎn)到T2中點(diǎn)的路徑,E*必定含有一條T里的邊。假設(shè)邊(u,v)T并且(u,v)E*。那么,T*=T1T2{(u,v)}是G的一個(gè)支撐樹(shù)。因?yàn)閣(u,v)w(e),所以有W(T*)=W(T1)+W(T2)+w(u,v)<W(F)+w(e)=W(T)。這與T是最小支撐樹(shù)相矛盾。所以算法正確。(b)Minimum-k-Tree-Spanning-Forest(G(V,E)) //kn1 用Kruskal或Prim算法計(jì)算G(V,E)的一個(gè)最小支撐樹(shù)T2 找出T中(k-1)條有最大權(quán)值的邊e1,e2,…,ek-13 FT–{e1,e2,…,ek-1}4. ReturnF正確性證明:我們對(duì)k進(jìn)行歸納證明。歸納基礎(chǔ):問(wèn)題(a)證明了k=2的情況。歸納步驟:假定對(duì)最小(k-1)-樹(shù)的支撐森林,k3,上面算法都能正確計(jì)算,我們證明上面算法也能正確算出最小k-樹(shù)的支撐森林。假設(shè)T和F分別是上面算法得到的最小支撐樹(shù)和k-樹(shù)支撐森林,但F的權(quán)值不是最小的。假設(shè)最小k-樹(shù)支撐森林是F*,它的k個(gè)樹(shù)為T1,T2,…,Tk。我們將證明W(F)W(T1)+W(T2)+…+W(Tk)=W(F*)。我們用E*表示子樹(shù)T1,T2,…,Tk之間的所有邊的集合,即E*={(u,v)E|uTi和vTj,1i,jk,ij}。那么,E*必定有(k-1)條在T里的邊。這是因?yàn)門1,T2,…,Tk把G的頂點(diǎn)分割為k個(gè)集合,所以至少要k-1條邊才可以把它們連結(jié)成一棵樹(shù)。所以|E*T|(k-1)。假定邊(u,v)是E*T中權(quán)值最小的邊。因?yàn)樯厦嫠惴ㄖ袆h去的是樹(shù)T中權(quán)值最大的(k-1)條邊,e1,e2,…,ek-1,且滿足w(e1)w(e2)…w(ek-1),所以我們有w(u,v)w(ek-1)。因?yàn)镕*{(u,v)}=T1T2…Tk{(u,v)}形成一個(gè)(k-1)-樹(shù)支撐森林,由歸納假?zèng)],F(xiàn){ek-1}是一個(gè)最小(k-1)-樹(shù)支撐森林,所以有W(F{ek-1})W(F*{(u,v)})。也就是W(F)+w(ek-1)W(F*)+w(u,v)。所以有:W(F)W(F*)+w(u,v)-w(ek-1)。因?yàn)閣(u,v)w(ek-1),所以有W(F)W(F*)。證畢。算法第二步從n個(gè)數(shù)中找k個(gè)最大的數(shù)可以用第5.4.3節(jié)的方法在O(n+klgn)=O(nlgn)時(shí)間內(nèi)完成,因此,算法復(fù)雜度與計(jì)算最小支撐樹(shù)相同。加權(quán)連通圖G(V,E)的一個(gè)支撐樹(shù)的瓶頸邊是這棵樹(shù)中有最大權(quán)值的一條邊,其權(quán)值稱為這個(gè)樹(shù)的瓶頸值。如果一個(gè)支撐樹(shù)的瓶頸值是G的所有支撐樹(shù)中最小的,那么這個(gè)支撐樹(shù)稱為瓶頸支撐樹(shù),記為BT(G)。證明最小支撐樹(shù)也是一個(gè)瓶頸支撐樹(shù)。設(shè)計(jì)一個(gè)線性時(shí)間的算法以決定給定的加權(quán)連通圖G(V,E)是否有瓶頸值不大于b的支撐樹(shù)。*解釋如何設(shè)計(jì)一個(gè)線性時(shí)間的算法找出加權(quán)連通圖G(V,E)的瓶頸支撐樹(shù)。不要求偽碼。解:證明:我們用BN(T)表示樹(shù)T的瓶頸值。假設(shè)T是圖G(V,E)的最小支撐樹(shù),而BT是G的瓶頸支撐樹(shù)。假設(shè)T和BT的瓶頸邊分別是(u,v)和(a,b),我們要證明w(u,v)w(a,b),即BN(T)BN(BT)。為了用反證法證明,我們假定w(u,v)>w(a,b),并證明導(dǎo)致矛盾。我們把邊(u,v)從T中刪去后,T分裂為不相交的兩個(gè)子樹(shù)T1和T2,uT1,vT2。讓U表示在T1中頂點(diǎn)的集合,V-U表示在T2中頂點(diǎn)的集合,那么C=(U,V-U)是V的一個(gè)割(見(jiàn)下圖)。UUV-UuvxyT1T2因?yàn)閣(u,v)>w(a,b),邊(u,v)BT。那么,如果我們沿著BT中從頂點(diǎn)u到頂點(diǎn)v的路徑走,一定會(huì)碰到一條邊(x,y),其中xU,yV-U。把邊(x,y)加到T1和T2中,我們得到一個(gè)支撐樹(shù)T*,T*=T1T2{(x,y)}=T{(x,y)}–{(u,v)}。它的權(quán)值是W(T*)=W(T)+w(x,y)–w(u,v)。 因?yàn)樵贐T中,邊(a,b)的權(quán)最大,而反證假設(shè)w(u,v)>w(a,b),所以有w(u,v)>w(a,b)w(x,y)。因此有W(T*)=W(T)+w(x,y)–w(u,v)<W(T)。這與T是最小支撐樹(shù)相矛盾。設(shè)計(jì)一個(gè)線性時(shí)間的算法以決定給定的加權(quán)連通圖G(V,E)是否有瓶頸值不大于b的支撐樹(shù)。算法如下,其正確性一目了然。Exist-BT(G(V,E),b)foreachedgeeE ifw(e)>b thenEE–{e} endifendforSelectavertexsinVBFS(G(V,E),s) //從點(diǎn)s開(kāi)始作廣度優(yōu)先搜索,產(chǎn)生BFS樹(shù)foreachvV ifcolor(v)=White thenreturn(nospanningtreeTwithBN(T)b) endifendforBTBFStreereturnBTEnd因?yàn)橹恍枰惠咮FS,算法的時(shí)間復(fù)雜度為O(m)。*解釋如何設(shè)計(jì)一個(gè)線性時(shí)間的算法找出加權(quán)連通圖G(V,E)的瓶頸支撐樹(shù)。不要求偽碼。算法的思路是用二元搜索找出最小瓶頸支撐樹(shù)T的BN(T)值。遞歸算法如下:BN(G(V,E))如果E中所有邊有相同權(quán)值b,停止并報(bào)告BN(G(V,E))=b。(遞歸見(jiàn)底)找出E中邊的權(quán)值的中位數(shù)。假設(shè)邊e的權(quán)值為中位數(shù),w(e)=b。E1E中權(quán)值小于b的邊。E2E中權(quán)值等于b的邊。E3E中權(quán)值大于b的邊。如果圖G(V,E1)有BFS樹(shù),則G(V,E)G(V,E1)。否則,如果圖G(V,E1E2)有BFS樹(shù),則停止并報(bào)告BN(G(V,E))=b。否則,如下操作:設(shè)圖G(V,E1E2)有BFS森林,含有k個(gè)樹(shù),T1,T2,…,Tk,也稱為分支。(8.1) 為每個(gè)G中頂點(diǎn)u打上分支號(hào),分支(u)。(8.2) 構(gòu)造分支圖中的點(diǎn)集合,V’={1,2,…,k},頂點(diǎn)i(1ik)代表分支i。(8.3) 構(gòu)造分支圖中的邊,E’={(分支(u),分支(v))|分支(u)分支(v),(u,v)E3}。(8.4) V’中兩點(diǎn)間可能有多條邊,只保留一條有最小權(quán)值的邊。辦法是把所有E’中邊排序使得(i,j)<(u,v)如果i<u或者i=u但是j<v。顯然用計(jì)數(shù)排序O(n)=O(m)可完成。這樣一來(lái),兩點(diǎn)間的多條邊在序列中就連在一起了,掃描這一序列一遍就可為兩點(diǎn)間保留一條有最小權(quán)值的邊。(8.5) G(V’,E’)是分支圖。G(V,E)G(V’,E’)。遞歸調(diào)用BN(G(V,E))。因?yàn)閨E1|<m/2,|E3|<m/2,我們有遞推關(guān)系:T(m)<T(m/2)+cm。所以,該算法的復(fù)雜度是T(m)=(m)。找出最小瓶頸支撐樹(shù)T的BN(T)值以后,只需一次BFS搜索就可以找出最小瓶頸支撐樹(shù)T。假設(shè)連通圖G的邊可以是任意的權(quán)值,可正可負(fù)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)找最小支撐連通子圖的算法,使其復(fù)雜度與最小支撐樹(shù)一樣。請(qǐng)證明算法的正確性。注意,最小支撐連通子圖可能比最小支撐樹(shù)的邊多卻有更小的總權(quán)值。下圖給出了一個(gè)例子。aabcd-2-1-346有正負(fù)權(quán)值的連通圖Gabcd-2-34G的最小支撐樹(shù)abcd-2-34G的最小支撐連通子圖-1解: Minimum-Spanning-Connected-Subgraph(G(V,E))SelectavertexsVT(V,A)MST-Prim(G(V,E),s) //先算出一個(gè)MSTA’AforeachedgeeE ifw(e)<0andeA’ then A’A’{e} //把所有負(fù)值邊全包進(jìn)來(lái) endifendforreturnT’(V,A’) //T’(V,A’)是把所有負(fù)值邊全包進(jìn)來(lái)后的圖End正確性證明:我們用反證法證明。假設(shè)最小支撐連通子圖G’(V,E’)的權(quán)值比T’(V,A’)小,W(G’)<W(T’)。顯然,G’必定含有所有負(fù)權(quán)值的邊,否則不會(huì)最小。我們把所有T’(V,A’)的邊分為3個(gè)集合:S1: 算法第2步中得到的最小支撐樹(shù)T(V,A)中有正權(quán)值的邊的集合。因?yàn)閃(G’)<W(T’),S1非空。S2: 算法第2步中得到的最小支撐樹(shù)T(V,A)中有負(fù)權(quán)值的邊的集合。由頂點(diǎn)V和S2中邊形成的子圖G(V,S2)必不連通,否則第2步中得到的最小支撐樹(shù)T(V,A)必不含有正權(quán)值的邊,與S1非空矛盾。因此S2中邊形成若干個(gè)連通分支,C1,C2,…,Ck(k>1),并且每個(gè)分支是一棵樹(shù)。S3: 算法第3步以后加入A’中的邊的集合。我們斷言,任一條S3中的邊一定在上述某個(gè)分支內(nèi),而不會(huì)連接兩個(gè)分支,否則可找到有比T(V,A)更小權(quán)值的支撐樹(shù)而矛盾。顯然G’中邊也包含S2和S3,因?yàn)樗胸?fù)權(quán)值的邊。S2S3是所有負(fù)權(quán)值的邊的集合。因此,G’中邊包含連通分支,C1,C2,…,Ck。我們把S3從G’中刪去,得到圖G’’=(V,E’-S3)。那么,我們斷言G’’必定是個(gè)連通圖,這是因?yàn)槿我粭lS3中的邊一定在某個(gè)分支內(nèi),而不會(huì)連接兩個(gè)分支,所以刪除S3中的邊不會(huì)改變G’的連通性,所以圖G’’是連通的。因此G’’有最小支撐樹(shù)T’’并且T’’必定包含S2中所有邊。這是因?yàn)镾2中所有邊不形成回路。因?yàn)門’’包含了G’’中所有負(fù)權(quán)值的邊,和一部分正權(quán)值的邊,所以有W(T’’)≤W(G’’)。因?yàn)門(V,A)是G的最小支撐樹(shù),G’’G,我們有:W(T(V,A))≤W(T’’)≤W(G’’),因此有W(T’(V,A’))=W(T(V,A))+W(S3)≤W(G’’)+W(S3)=W(G’),與假設(shè)矛盾。無(wú)向連通圖的一棵支撐樹(shù)再加上一條邊稱為一棵1-樹(shù)。下面圖顯示了一個(gè)1-樹(shù)的例子。(a)(a)一個(gè)無(wú)向圖G(b)G的一棵1-樹(shù)abcdebcdea一個(gè)加權(quán)的無(wú)向連通圖G(V,E)的一棵1-樹(shù)稱為最小1-樹(shù),如果它有最小的總權(quán)值。請(qǐng)?jiān)O(shè)計(jì)一個(gè)復(fù)雜度好的計(jì)算最小1-樹(shù)的算法。你需要證明其正確性和分析復(fù)雜度。解: Minimum-1-Tree(G(V,E)) SelectavertexsVT(V,A)MST-Prim(G(V,E),s) //用Prim算法找出一個(gè)最小支撐樹(shù)TE’E–A //不在T里的剩余的邊集合ifE’= thenreturn(no1-treeexists) //1-樹(shù)不存在 else findeE’suchthatw(e)=min{w(e)|eE’} //E’中最小邊e returnT{e}endifEnd這個(gè)算法顯然有與Prim算法相同的復(fù)雜度。正確性證明:首先,如果集合E’是空集,那么1-樹(shù)不可能存在。所以假定E’。我們證明算法產(chǎn)生的T{e}必定是最小1-樹(shù)。假設(shè)T’{e’}是任意一個(gè)1-樹(shù)。因?yàn)門’{e’}含有一個(gè)回路C,那么C上必有一條邊e’’不屬於A而屬于E’。把這條邊從這個(gè)1-樹(shù)中刪去后得到一個(gè)支撐樹(shù)T’’,并且有權(quán)值為w(T’’)=w(T’)+w(e’)-w(e’’)。顯然也有w(T’)+w(e’)=w(T’’)+w(e’’)。那么,我們有如下關(guān)系:w(e’’)w(e) 因?yàn)閑’’E’=E–A。w(T’’)w(T) 因?yàn)門和T’’都是G的支撐樹(shù),但T是最小支撐樹(shù)。所以,我們有w(T’)+w(e’)=w(T’’)+w(e’’)w(T)+w(e)。這也就是說(shuō),任一棵1-樹(shù)的權(quán)值都大于等于算法產(chǎn)生的1-樹(shù)的權(quán)值,所以算法正確。假設(shè)T是圖G(V,E)的一棵以頂點(diǎn)s為根的最小支撐樹(shù)。如果我們把圖G(V,E)中的一條邊(u,v)的權(quán)值增加到w(u,v),而這條邊也是T中的一條邊,(u,v)T,那么T就不一定是這個(gè)變化后的圖G(V,E)的一棵最小支撐樹(shù)了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(m)的算法把T修改為變化后的圖G(V,E)的一個(gè)最小支撐樹(shù)并證明其正確性。解: 我們的做法是,把邊(u,v)從樹(shù)T里刪去,得到兩個(gè)子樹(shù),T1和T2。T1和T2形成對(duì)頂點(diǎn)集合V的分割,C=(U1,U2),其中U1包含T1中所有頂點(diǎn),U2包含T2中所有頂點(diǎn)。然后,在圖G里找出這個(gè)割的最小交叉邊e,那么T1T2{e}形成的樹(shù)就是答案。Modify-MST-Increase-Weight(G(V,E),T,u,v)foreachvV Adj(v) //為樹(shù)T的每個(gè)頂點(diǎn)建鄰居集合,初始為空endfor foreachvV if(v)=w //(w,v)是一條邊 then Adj(w)Adj(w){v} //w和v互為鄰居 Adj(v)Adj(v){w} endifendforTT–{(u,v)} //刪除邊(u,v)后,T=T1T2。設(shè)uT1,vT2BFS(T,u)andcolorallvisitedverticesred //只能訪問(wèn)到T1中點(diǎn),并著為紅色BFS(T,v)andcolorallvisitedverticesblue//只能訪問(wèn)到T2中點(diǎn),并著為藍(lán)色e(u,v)ww(u,v)foreachedge(x,y)E //找最小交叉邊 if(color(x)≠color(y))andw(x,y)<w then e(x,y) ww(x,y) endifendforT’T{e} //也就是T1T2{e}returnT’End正確性證明:設(shè)T*是邊(u,v)的權(quán)值增加后的圖G(V,E)的任意一個(gè)支撐樹(shù)。我們證明W(T’)W(T*),這里,T’是我們算法產(chǎn)生的支撐樹(shù)。我們分兩種情況證明.T*包含邊(u,v)。如果是這種情況,我們把邊(u,v)從T*中刪去后得到子樹(shù)T1*和T1*。因?yàn)門是圖G的一棵最小支撐樹(shù),所以有W(T1)+W(T2)+w0(u,v)W(T1*)+W(T2*)+w0(u,v)。這里,w0(u,v)是邊(u,v)原來(lái)的權(quán)值。所以有W(T1)+W(T2)W(T1*)+W(T2*)。因?yàn)閣(e)w(u,v),這里e是算法得到的割C=(U1,U2)的最小交叉邊,其中,U1包含T1中所有頂點(diǎn),U2包含T2中所有頂點(diǎn)。所以有:W(T1)+W(T2)+w(e)W(T1*)+W(T2*)+w(u,v),也就是W(T’)W(T*)。T*不包含邊(u,v)。如果是這種情況,在T*中,從點(diǎn)u到點(diǎn)v的路徑上,一定有一條邊(x,y)與割C=(U1,U2)相交。因?yàn)檫?u,v)是原圖中這個(gè)割的最小交叉邊,w0(u,v)w(x,y),這里,w0(u,v)是邊(u,v)原來(lái)的權(quán)值?,F(xiàn)在,如果把邊(x,y)從T*中刪去,則會(huì)得到子樹(shù)T1*和T2*,使得點(diǎn)u和點(diǎn)v分屬兩邊。因?yàn)?,T1*T2*{(u,v)}也是原圖G的一棵支撐樹(shù),而T是一棵最小支撐樹(shù),故有:W(T1)+W(T2)+w0(u,v)W(T1*)+W(T2*)+w0(u,v)。所以有:W(T1)+W(T2)W(T1*)+W(T2*)。因?yàn)檫卐是(u,v)的權(quán)值增加后的圖G中割C=(U1,U2)的最小交叉邊,所以有w(e)w(x,y)。因此有W(T1)+W(T2)+w(e)W(T1*)+W(T2*)+w(x,y)。這就證明了W(T’)W(T*)。因?yàn)門有n個(gè)點(diǎn),n-1條邊,算法在第14行前只需O(n)時(shí)間,而第15行的循環(huán)有O(m)的復(fù)雜度,所以算法有O(m)的復(fù)雜度。假設(shè)T是圖G(V,E)的一棵最小支撐樹(shù)。它的邊是e1,e2,…,en-1,并有權(quán)值順序?yàn)閣1w2…wn-1,這里,n=|V|。我們定義T的一個(gè)子圖Ti(V,Ei)如下。子圖Ti(V,Ei)有與T相同的頂點(diǎn)集合V,但它的邊是Ei=e1e2…ei,即它的邊是由T中權(quán)值最小的i條邊組成(0in-1)。當(dāng)i=0時(shí),T0不含有邊,只含n個(gè)頂點(diǎn)。顯然,Ti由n-i個(gè)連通分支組成,C1,C2,…,Cn-i,而每個(gè)連通分支是一棵T的子樹(shù)。證明圖G(V,E)里,除Ei以外的任一條邊e,eE-Ei,如果它連結(jié)分屬兩個(gè)不同分支的兩個(gè)點(diǎn),那么,它的權(quán)值w(e)大于等于wi+1,即w(e)wi+1。證明:為了用反證法,假設(shè)有邊e=E-Ei,連結(jié)C1和C2,但w(e)<wi+1。設(shè)e=(a,b),其中aC1,bC2。因?yàn)閑Ei而且w(e)<wi+1,邊e不可能屬于T,e{e1,e2,…,en-1}。考慮T中從點(diǎn)a到點(diǎn)b的路徑P(a,b)。它必定經(jīng)過(guò)T-Ei中某條邊e*,即e*{ei+1,ei+2,…,en-1}。我們有:w(e)<wi+1w(e*)。如果我們把e*從T中刪去,把邊e加進(jìn)來(lái),我們會(huì)得到一個(gè)權(quán)值更小的支撐樹(shù)T’:W(T’)=W(T)-w(e*)+w(e)<W(T)。這與T是最小支撐樹(shù)矛盾。*假設(shè)T是圖G(V,E)的一個(gè)最小支撐樹(shù)。它的邊是e1,e2,…,en-1,并有權(quán)值順序?yàn)閣1w2…wn-1,這里,n=|V|。假設(shè)T’是圖G的另一個(gè)支撐樹(shù),它的邊是e’1,e’2,…,e’n-1,并有權(quán)值順序?yàn)閣’1w’2…w’n-1。證明wiw’i(1in-1)。(題示:先做第19題。)解:我們對(duì)i用歸納法證明。 歸納基礎(chǔ)。當(dāng)i=1時(shí),由19題知,w1w’1。 歸納步驟。假設(shè)我們有w1w’1,w2w’2,…,wkw’k(k1),我們證明必有wk+1w’k+1。我們用反證法。假設(shè)有wk+1>w’k+1。我們定義子圖Tk(V,Ek),它的頂點(diǎn)集合V與G相同,邊集合是Ek=e1e2…ek,即它的邊是由T中權(quán)值最小的k條邊組成(0kn-1)。當(dāng)k=0時(shí),T0不含有邊,只含n個(gè)頂點(diǎn)。顯然,Tk有n-k個(gè)連通分支,C1,C2,…,Cn-k,每一分支是一棵樹(shù)。由19題知,任何集合E–Ek中的邊e,如果連結(jié)不同分支的話,必有w(e)wk+1。因?yàn)閣’k+1<wk+1,所以邊e’k+1必定連結(jié)同一分支的兩個(gè)點(diǎn)。又因?yàn)閣’1w’2…w’k+1,所以邊e’1,e’2,…,e’k也必定是連結(jié)同一分支中的點(diǎn)。所以這n-k個(gè)分支含有集合S’={e’1,e’2,…,e’k+1}中所有k+1條邊。讓我們假設(shè)這n-k個(gè)分支中頂點(diǎn)的個(gè)數(shù)分別是n1,n2,…,nn-k。因?yàn)門’是圖G的一個(gè)支撐樹(shù),不含回路,所以這n-k個(gè)分支中能夠含有T’中邊的個(gè)數(shù)必定小于等于(n1-1)+(n2-1)+…+(nn-k-1)=n1+n2+…+nn-k–(n–k)=n–(n–k)=k。這就產(chǎn)生了矛盾。所以,必定有wk+1w’k+1,歸納成功。假設(shè)T是圖G(V,E)的一個(gè)最小支撐樹(shù)。設(shè)圖中的一條邊(u,v)E不屬于T,(u,v)T。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)的算法去修改一下T使得修改后的支撐樹(shù)含邊(u,v)并且有最小權(quán)值。你需要證明它的正確性。解:偽碼如下,證明隨后。Modify-MST(T,u,v)BFS(T,u)andgetaBFStree //從頂點(diǎn)u開(kāi)始對(duì)T作BFS,并得到BFS樹(shù)w-bv //從頂點(diǎn)v開(kāi)始,沿著到頂點(diǎn)u的路徑,找權(quán)值最大邊a(v)whileanil ifw(a,b)>w then ww(a,b) xa yb endif ba a(a)endwhileT’(T–{(x,y)}){(u,v)}returnT’End正確性證明:假設(shè)T*是含有邊(u,v)的一棵支撐樹(shù),我們證明有W(T’)W(T*),這里T’是上面算法產(chǎn)生的支撐樹(shù)。如果我們把邊(u,v)從T*刪去,那么如下圖(a)所示,得到兩個(gè)子樹(shù),T1*和T2*,頂點(diǎn)u屬于T1*,頂點(diǎn)v屬于T2*。如果我們沿著最小支撐樹(shù)T中從頂點(diǎn)u到頂點(diǎn)v的路徑走,那么,如圖(b)所示,一定會(huì)碰到一條邊(a,b),其中,aT1*和bT2*。把邊(a,b)從最小支撐樹(shù)T中刪除會(huì)得到T的兩個(gè)子樹(shù),T1和T2。因?yàn)檫?a,b)連接T1*和T2*,那么T1*T2*{(a,b)}是一個(gè)支撐樹(shù)。因?yàn)門是最小支撐樹(shù),所以有W(T1)+W(T2)+w(a,b)W(T1*)+W(T2*)+w(a,b)。從而有:W(T1)+W(T2)W(T1*)+W(T2*)。因此有:W(T1)+W(T2)+w(u,v)W(T1*)+W(T2*)+w(u,v)=W(T*)。因?yàn)?,由算法知:W(T’)=W(T)-w(x,y)+w(u,v)=[W(T1)+W(T2)+w(a,b)]-w(x,y)+w(u,v)=W(T1)+W(T2)+w(u,v)+(w(a,b)-w(x,y))W(T1)+W(T2)+w(u,v) //因?yàn)橛伤惴ㄖ獁(a,b)w(x,y)所以有W(T’)W(T*)。這證明了算法的正確性,其復(fù)雜度顯然是O(n)。假設(shè)T是圖G(V,E)的一個(gè)最小支撐樹(shù)。我們考慮如何能在O(n2)時(shí)間里找到第二小的支撐樹(shù)。第二小的支撐樹(shù)指的是所有與T不同的支撐樹(shù)中權(quán)值最小的一個(gè)。我們假設(shè)G(V,E)T,否則不存在。我們分三個(gè)小問(wèn)題來(lái)解決。假設(shè)我們的算法需要對(duì)一個(gè)堆棧S作一系列的Push(S,x)和Pop(S)的操作,其中Push(S,x)表示把數(shù)字x壓入堆棧S,Pop(S)表示把棧頂?shù)脑貜棾觥4送?,我們的算法需要能夠知道?dāng)前堆棧S中哪個(gè)元素最大,它的數(shù)字是多少。請(qǐng)?jiān)O(shè)計(jì)一個(gè)簡(jiǎn)單算法,任憑堆棧S如何動(dòng)態(tài)變化,都能在O(1)時(shí)間里幫我們找到當(dāng)前堆棧中這個(gè)最大元素。假設(shè)T(V,E,r)是一個(gè)以頂點(diǎn)r為根的樹(shù),樹(shù)中的每條邊有實(shí)數(shù)權(quán)值。我們用M(r,v)表示在從根r到頂點(diǎn)v的路徑上的邊的最大權(quán)值。下圖給出了一個(gè)例子。rr57-3-6abcdfghiljke9-428910611M(r,a)=5,M(r,b)=9,M(r,c)=5,M(r,d)=5,M(r,e)=11,M(r,f)=-3,M(r,g)=-3,M(r,h)=9,M(r,i)=8,M(r,j)=10,M(r,k)=8,M(r,l)=7.請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)的算法為樹(shù)中每一個(gè)根以外的頂點(diǎn)vV,v≠r,計(jì)算M(r,v),這里n=|V|。我們假定,每個(gè)頂點(diǎn)u的父親已知,是π(u),根的父親是π(r)=nil。另外,每個(gè)頂點(diǎn)u的兒子們由一個(gè)鏈表組織起來(lái),用“vu’snextson”語(yǔ)句就可以訪問(wèn)頂點(diǎn)u的下一個(gè)兒子或第一個(gè)兒子。如果u’snextson=nil,則表明頂點(diǎn)u的所有兒子們都已被算法訪問(wèn)過(guò)了,或者頂點(diǎn)u是個(gè)樹(shù)葉。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n2)算法為加權(quán)連通圖G(V,E)找出第二小的支撐樹(shù)。為簡(jiǎn)單起見(jiàn),我們假定圖G的所有邊的權(quán)值都不同,并已知T是圖G(V,E)的MST。解: (a) 我們用另外一個(gè)堆棧S’來(lái)幫忙,使得S’的頂始終指向堆棧S中的最大數(shù)。我們假定一開(kāi)始時(shí),堆棧S和S’都是空的。每當(dāng)我們操作Push(S,x)或Pop(S)時(shí),我們對(duì)堆棧S’作出相應(yīng)的更新操作。具體做法如下:(1)每次Push(S,x)以后,進(jìn)行以下操作:ifS’=orxTop(S’) //否則不操作 thenPush(S’,x) //x是堆棧S中最大的數(shù)(2)每次Pop(S)以前,進(jìn)行以下操作: ifS’andTop(S)=Top(S’) //否則不操作 thenPop(S’)正確性證明:我們用歸納法證明,如果堆棧S非空,Top(S’)始終指向堆棧S中的最大數(shù)。歸納基礎(chǔ):一開(kāi)始時(shí),堆棧S和S’都是空的。命題正確。當(dāng)?shù)谝粋€(gè)數(shù)壓入堆棧S時(shí),這個(gè)數(shù)也被壓入堆棧S’,命題正確。歸納步驟:

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論