計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第11章

PAGE1第11章 網(wǎng)絡(luò)流在例11.7的網(wǎng)絡(luò)中，如果集合S={s，v3，v4}，T={v1，v2，t}，那么割(S,T)的容量是多少？解： 割(S,T)的容量是c(S,T)=13+12+9+19+7=60，參照下圖。svsv1v2v3v45412181376109t19假設(shè)f是網(wǎng)絡(luò)G(V,E)的一個(gè)流。證明，在剩余網(wǎng)絡(luò)Gf(V,Ef)中，任一對(duì)頂點(diǎn)u和v之間有如下關(guān)系:cf(u,v)+cf(v,u)=c(u,v)+c(v,u)。證明： 因?yàn)閏f(u,v)=c(u,v)-(u,v)和cf(v,u)=c(v,u)–(v,u)，我們有cf(u,v)+cf(v,u)=c(u,v)+c(v,u)–[(u,v)+(v,u)]。因?yàn)閇(u,v)+(v,u)]=0，從而有cf(u,v)+cf(v,u)=c(u,v)+c(v,u)。證明任一個(gè)網(wǎng)絡(luò)G(V,E)的最大流總可以由最多m個(gè)增廣路徑增廣而得。(等價(jià)地證明，其最大流可以分解為最多m個(gè)增廣流之和。)證明： 假設(shè)f是G(V,E)的最大流，其值為|f|=F。我們先復(fù)制一個(gè)網(wǎng)絡(luò)G(V,E)的考貝，G’(V’,E’)=G(V,E)。其中，V’=V，E’=E，c’(u’,v’)=c(u,v)。因?yàn)榫W(wǎng)絡(luò)G’和G完全一樣，網(wǎng)絡(luò)G的最大流也必定是G’的最大流，反之也成立。現(xiàn)在，我們利用G(V,E)的最大流f來找G’(V’,E’)的最大流。設(shè)G’(V’,E’)的初始流是零。我們證明，最多m次增廣路徑的增廣可得到G’(V’,E’)的最大流。在G(V,E)中一條從源點(diǎn)s到匯點(diǎn)t的路徑p稱為一條流路徑(flowpath)，如果路徑p經(jīng)過的每條邊都有非零的流。我們定義這條流路徑的流量為fp=min{f(u,v)|(u,v)p}，也就是路徑p上有最小流量的邊上的流。我們從G(V,E)的最大流f來找G’(V’,E’)的最大流的算法如下。Max-flow(G’(V’,E’))foreachedge(u’,v’)E’ f’(u’,v’)0 //初始流為零endforforeachedge(u,v)E F(u,v)f(u,v) //F(u,v)記下f的初值，算法會(huì)更改變f，但不改FendforwhilethereexistsaflowpathpinG(V,E) //如果存在一條s到t的流路徑p(可用BFS找) f(p) //f(p)是p的流量，f(p)=min{f(u,v)|(u,v)p} foreachedge(u,v)p f’(u’,v’)f’(u’,v’)+ //增加G’中邊(u’,v’)上流量 f(u,v)f(u,v)- //減少G中邊(u,v)上流量 endforendwhileEnd上面算法的正確性可以證明如下。首先，我們證明，一條G中的流路徑就是G’中的增廣路徑。因?yàn)镚’中的任何一條邊(u’,v’)上流量的增加就等于G中邊(u,v)上流量的減少，兩者之和f’(u’,v’)+f(u,v)始終不變，f’(u’,v’)+f(u,v)=0+F(u,v)c(u,v)=c’(u’,v’)，所以，在每次第7行while循環(huán)之后，G’中邊(u’,v’)上的剩余容量c’f(u’,v’)滿足以下不等式：c’f(u’,v’)=c(u,v)-f’(u’,v’)F(u,v)-f’(u’,v’)=f(u,v)。因此，只要f(u,v)>0，就有c’f(u’,v’)>0。所以，一條G中的流路徑就是G’中的增廣路徑。其次，容易看出，每一次G中的流減少以后仍然是一個(gè)正常流。這是因?yàn)樗鼭M足f(u,v)c(u,v)和流量守恒?，F(xiàn)在需要證明的是，只要G中的流不是零，就一定有流路徑。我們用反證法。如果不是，那么，我們把所有從源點(diǎn)s有流路徑可達(dá)的點(diǎn)放在集合S中，其它點(diǎn)放在集合T中。因?yàn)閠T，(S,T)必定是個(gè)割，并且有f(S,T)=0從而|f|=0。這與G中的流不是零相矛盾。所以，上面的算法Max-flow正確地產(chǎn)生G’(V’,E’)的最大流。因?yàn)槊看卧鰪V后，G中至少有一條邊的流量為零，所以經(jīng)過最多m次增廣，G中所有邊的流量為零，算法結(jié)束。這時(shí)，G’中的流增加到最大，并有流|f’|=F。因?yàn)榫W(wǎng)絡(luò)G與G’完全一樣，網(wǎng)絡(luò)G(V,E)的最大流也可以由最多m個(gè)增廣路徑增廣而得。用Edmonds-Karp算法找出以下每個(gè)網(wǎng)絡(luò)的一個(gè)最大流。請(qǐng)參照?qǐng)D11-7的形式，圖示每輪中的剩余網(wǎng)絡(luò)，所用增廣路徑，以及對(duì)應(yīng)的增廣流。另外，請(qǐng)給出一個(gè)最小割。1212sv1v2v3v4471314164109t20(a)11sv1v2

v3

v4

615172124109t194(b)解： (a)tt12sv1v2v3v447131416410920(a)12/12sv1v2v3v40/40/70/130/1412/160/40/100/9t12/20(b)tt12/12sv1v2v3v40/40/74/134/1412/164/40/100/9t12/20(d)12sv1v2v3v4471314441098(c)121212/1212/12sv1v2v3v40/47/711/1311/1412/164/40/100/9t19/20(f)t12sv1v2v3v447910441098(e)1212441212sv1v2v3v4472344109t1(g)12191111圖(f)中流是最大流，流量是23。一個(gè)最小割（S,T）是：S={s,v1,v2,v4}，T={t,v3}。(b)1111sv1v2v3v4615172124109t194(a)11/11sv1v2v3v40/60/150/1711/210/240/100/9t11/190/4(b)tt11/11sv1v2v3v40/615/1515/1711/2115/240/100/9t11/190/4(d)11sv1v2v3v461517102410984(c)1111tt11/11sv1v2v3v40/615/1515/1715/2119/240/100/9t11/194/4(f)11sv1v2v3v46151510910984(e)111121511/1111/11sv1v2v3v40/615/1517/1717/2121/242/100/9t11/194/4(h)11sv1v2v3v46151565109t84(gv1v2v3v4615174389t84(i)1711221圖(h)中流是最大流，流量是32。一個(gè)最小割（S,T）是：S={s,v1,v2}，T={t,v3,v4}。如果把一個(gè)有向圖G(V,E)中的一個(gè)邊的集合H刪去后，圖中沒有從頂點(diǎn)a到頂點(diǎn)b的路徑，那么稱H為a到b的一個(gè)割。如果H是所有a到b的割中最小的，也就是它含有的邊的個(gè)數(shù)最少，則稱H為a到b的一個(gè)最小割，并且稱|H|為a到b的邊連通度。如果G本身就沒有從a到b的路徑，那么最小割為空集，a到b的邊連通度為0。請(qǐng)把計(jì)算有向圖G(V,E)中的從a到b的邊連通度問題建模為一個(gè)網(wǎng)絡(luò)流問題來解，使得流網(wǎng)絡(luò)中的點(diǎn)的個(gè)數(shù)不超過O(n)，而邊的個(gè)數(shù)不超過O(m)。這里，n=|V|，m=|E|。請(qǐng)嚴(yán)格證明你的方法的正確性。解： 建模和計(jì)算的過程表達(dá)在下面的偽碼中。Edge-Connectivity(G(V,E),a,b)構(gòu)造流網(wǎng)絡(luò)G’(V’,E’)，其中V’=V，E’=E，并賦以E’中每一條邊容量1以a為源點(diǎn)，b為匯點(diǎn)，計(jì)算網(wǎng)絡(luò)G’(V’,E’)的最大流f和最小割(S,T)，讓C(a,b)為所有穿越邊的集合HC(a,b)k|H|returnH,k //最小割是H，連通度是kEnd算法正確性證明如下。首先，因?yàn)辄c(diǎn)aS，bT，刪除集合H后，沒有路徑可以從點(diǎn)a到達(dá)點(diǎn)b，所以集合H是a到b的一個(gè)割。又因?yàn)槊織l邊的容量是1，所以，c(S,T)=|C(a,b)|=|H|=k。下面證明，集合H小于等于任何一個(gè)a到b的割。假設(shè)H’是任意一個(gè)a到b的割。我們由H’構(gòu)造一個(gè)流網(wǎng)絡(luò)G’(V’,E’)的割(S’,T’)如下：E’E’–H’(刪除H’)在余下的圖G’中，定義集合S’為V’中有路徑從點(diǎn)a可達(dá)的點(diǎn)，即S’={uV’|thereisapathpinG’fromnodeatonodeu}定義集合T’=V’–S’。因?yàn)镠’是一個(gè)a到b的割，所以頂點(diǎn)b不屬于集合S’。那么，(S’,T’)就是網(wǎng)絡(luò)G’(V’,E’)的割。由最大流最小割定理，算法得到的割H最小，故滿足|H|=|f|c(S’,T’)。所以(S’,T’)至少有|H|=k條穿越邊。因?yàn)榧蟃’中的點(diǎn)都沒有從點(diǎn)a可達(dá)的路徑，所以，所有穿越邊一定被刪除了。這也就是說，H’包含了(S’,T’)中的所有穿越邊。這意味著c(S’,T’)|H’|。因此有|H||H’|，H是a到b的一個(gè)最小割。如果把無向圖G(V,E)中的一個(gè)邊的集合H刪去后，剩余的圖是一個(gè)不連通圖，那么H稱為一個(gè)割。圖G的最小割所含的邊數(shù)稱為G的邊連通度。如果G是個(gè)不連通圖，那么最小割H為空集，G的邊連通度為0。如果G是棵樹，顯然連通度為1，而一個(gè)回路的連通度為2。請(qǐng)?jiān)O(shè)計(jì)一個(gè)用網(wǎng)絡(luò)流來決定一個(gè)無向圖G(V,E)的邊連通度的算法。你調(diào)用網(wǎng)絡(luò)流算法的次數(shù)不應(yīng)超過n次，而且每次構(gòu)造的流網(wǎng)絡(luò)中的點(diǎn)的個(gè)數(shù)不超過O(n)，邊的個(gè)數(shù)不超過O(m)。這里，n=|V|，m=|E|。解： 我們先構(gòu)造一個(gè)加權(quán)有向圖G’(V’,E’)，其中V’=V,E’={(u,v),(v,u)|(u,v)E}，即G中每條邊(u,v)對(duì)應(yīng)為G’中一對(duì)有向邊(u,v)和(v,u)，并且賦給每條邊容量1。構(gòu)造好以后，算法如下。Undirected-Graph-Edge-Connectivity(G’(V’,E’))H’kSelectavertexsV’ //任選一個(gè)頂點(diǎn)sforeachvV’–{s} UseEdmonds-Karp(G’(V’,E’),s,v)tofindaminimumcut(S,T)。 //以s為源點(diǎn)，v為匯點(diǎn)，用Edmonds-Karp算法計(jì)算G’的最小割(S,T) C{(u,v)E’|uS,vT} //(S,T)的所有穿越邊集合 if|C|<k then H’C k|C| endifendforH{(u,v)E|(u,v)H’} //H中邊是圖G中無向邊returnH,kEnd因?yàn)閨V’|=|V|，|E’|=2|E|，所以算法中每次求最大流的網(wǎng)絡(luò)中的點(diǎn)的個(gè)數(shù)不超過O(n)，而邊的個(gè)數(shù)不超過O(m)。另外，算法中一共調(diào)用最大流的算法n-1次，所以，復(fù)雜度符合要求。現(xiàn)在證明其正確性。首先，由G’(V’,E’)的構(gòu)造知，如果H’是G’(V’,E’)中以s為源點(diǎn)，v為匯點(diǎn)的一個(gè)割(S,T)，其中sS，vT，那么，我們可由H’得到G(V,E)的一個(gè)割H如下：H={(u,v)E|(u,v)H’}。我們注意到，如果(u,v)H’，那么uS，vT。所以，(u,v)H’當(dāng)且僅當(dāng)((u,v)H，uS，vT)。因?yàn)閯h除H’后，圖G’中沒有從集合S到T的邊，那么，刪除H后，圖G中也沒有從集合S到T的邊。所以H是G(V,E)的一個(gè)割。另外，任何一對(duì)邊(u,v)和(v,u)之間，只能有一條屬于H’，所以有|H|=|H’|。反之，如果H是G(V,E)的一個(gè)割，把H刪除后，G(V,E)不連通，集合V可分為兩部分，S和T，使得S和T之間沒有邊，并且有sS。選集合T中任一點(diǎn)v，那么，由H可構(gòu)造一個(gè)G’(V’,E’)的以s為源點(diǎn)，v為匯點(diǎn)的一個(gè)割H’如下：H’={(u,v)E’|(u,v)HanduS,vT}。因?yàn)閯h除H后，圖G中沒有從集合S到T的邊，那么，刪除H’之后，圖G’中也必定沒有從集合S到T的邊。所以H’是G’(V’,E’)的一個(gè)割。因?yàn)檫?u,v)H對(duì)應(yīng)的一對(duì)邊(u,v)和(v,u)之間，只能有一條可以被選入H’，所以有|H|=|H’|。所以，找到G’(V’,E’)的任何兩點(diǎn)間的最小割，就找到了G(V,E)的最小割。因?yàn)镚’(V’,E’)的最小割一定會(huì)把頂點(diǎn)s和某個(gè)頂點(diǎn)v分開，所以我們對(duì)集合V-{s}中每個(gè)點(diǎn)v，逐個(gè)找出把頂點(diǎn)s和v分開的最小割。顯然，其中最小的就是解。上面的算法Undirected-Graph-Edge-Connectivity正是這一思路的實(shí)現(xiàn)。如果一個(gè)圖G(V,E)中的每個(gè)點(diǎn)的度數(shù)等于d，d>0，則稱為d-正則圖(d-regulargraph)。假設(shè)G(V,E)是一個(gè)d-正則的二部圖，其中V=LR，而且|L|=|R|。E中任一條邊連結(jié)L中一個(gè)點(diǎn)和R中一個(gè)點(diǎn)。證明這個(gè)二部圖有完美匹配。證明： 我們只要證明這個(gè)二部圖滿足Hall氏定理。假設(shè)SL是集合L的任一個(gè)子集。R(S)是S在R中的映象，即R(S)={vR|uL使得(u,v)E}?？紤]在S和R(S)之間的所有邊的集合E’={(u,v)|uS，vR(S)}。因?yàn)镾中每個(gè)點(diǎn)有相同度數(shù)d，所以有|E’|=d|S|。再考慮在L和R(S)之間的所有邊的集合E’’={(u,v)|uL，vR(S)}。因?yàn)镽(S)中每個(gè)點(diǎn)有相同度數(shù)d，所以有|E’’|=d|R(S)|。因?yàn)镋’E’’，所以d|S|d|R(S)|，因此有|S||R(S)|。根據(jù)Hall氏定理，這個(gè)二部圖有完美匹配。證明定理11.18:假設(shè)G(V,E)是一個(gè)單分支0-1網(wǎng)絡(luò)，那么用Dinic算法計(jì)算它的最大流的時(shí)間復(fù)雜度是O(mn)。證明： 首先，我們注意到，對(duì)應(yīng)于G(V,E)上的任一個(gè)整數(shù)流f的剩余圖Gf也是一個(gè)單分支網(wǎng)絡(luò)，這是因?yàn)槊織l邊上要么沒有流，要么流為1。所以，如果有流經(jīng)過一個(gè)有單入邊頂點(diǎn)u(us，ut)的話，在剩余圖Gf中，它的單入邊成為一條出邊，而其中一條有流的出邊成為一條單入邊，所以點(diǎn)u仍然是一個(gè)單入邊頂點(diǎn)。同理，如果有流經(jīng)過一個(gè)有單出邊頂點(diǎn)的話，這個(gè)點(diǎn)在剩余圖Gf中仍然是一個(gè)有單出邊的點(diǎn)。其次，假設(shè)剩余圖Gf中，從源點(diǎn)s到匯點(diǎn)t的距離是k。V0,V1,…,Vk是Gf的距離圖中各級(jí)頂點(diǎn)的集合，其中sV0，tVk。那么，我們可以為任一級(jí)頂點(diǎn)Vi，1￡i￡k-1，構(gòu)造一個(gè)割。設(shè)Vi={v1,v2,…,vh}，構(gòu)造一個(gè)割的步驟如下：SV0V1…Vi-1TVi+1Vi+2…Vk對(duì)Vi中每一個(gè)點(diǎn)v，如果點(diǎn)v有一條單入邊，那么把點(diǎn)v歸入集合T，否則點(diǎn)v有一條單出邊，把點(diǎn)v歸入集合S。容易看出，(S,T)是一個(gè)割。因?yàn)槊織l穿越邊關(guān)聯(lián)Vi中一個(gè)點(diǎn)，并且是一條單入邊或單出邊，所以，它的容量為c(S,T)=|Vi|。如果最大流的值是F的話，因?yàn)槊織l邊容量是1，因而有Fc(S,T)=|Vi|(1￡i￡k-1)。由此得到i=1k-1Fi=1k-1|Vi|n-2<n，也就是(k-1)F<n或k<n/F+1，也就是k用證明引理11.17的方法可證Dinic算法只需進(jìn)行2n輪阻塞流的計(jì)算。細(xì)節(jié)如下：如果網(wǎng)絡(luò)中最大流Fn，那么Dinic算法顯然只需進(jìn)行最多Fn輪阻塞流的計(jì)算。如果網(wǎng)絡(luò)中最大流F>n，那么經(jīng)過n輪阻塞流的計(jì)算后，設(shè)網(wǎng)絡(luò)G中流是f，而剩余網(wǎng)絡(luò)中的最大流是Mf。因?yàn)檫@時(shí)距離圖中s到t的距離k至少為n，kn，但是,又必須有kn/Mf，這里Mf是在剩余網(wǎng)絡(luò)中的最大流。所以有Mfn/kn/n=n。這樣，最多再經(jīng)過n輪阻塞流的計(jì)算后即可找到最大流。因每次阻塞流的計(jì)算只需O(m)(矩陣平分問題)假設(shè)A={aij}是一個(gè)n′n的整數(shù)矩陣，其中每個(gè)元素都是非負(fù)整數(shù)，aij0(1￡i,j￡n)。我們用ARi和ACj分別表示矩陣A的第i行元素之和，與第j列的元素之和，即ARi=j=1naij(1￡i￡n)和ACj=i=1naij(1￡j￡n)。為簡(jiǎn)單起見，假設(shè)這些和都是偶數(shù)?，F(xiàn)在我們希望把A分解為兩個(gè)整數(shù)矩陣B和C之和，即A=B+C，使得B的第i行元素之和等于C的第i行元素之和，BRi=CRi(1￡i￡n)，而B的第j列元素之和也等于C的第j列元素之和，BCj=CCj(1￡j￡A=ARi53030請(qǐng)把這個(gè)矩陣平分問題建模為一個(gè)網(wǎng)絡(luò)流問題，并證明一定有解。解： 我們構(gòu)造一個(gè)流網(wǎng)絡(luò)G如下:(a) 構(gòu)造一個(gè)有向二部圖G(UV,E)，其中U={u1,u2,…,un}代表矩陣A的n行，而V={v1,v2,…,vn}代表A的n列。如果aij>0，那么構(gòu)造一條邊(ui,vj)并賦以容量c(ui,vj)=aij。(b) 加上源點(diǎn)s，然后為U中每個(gè)點(diǎn)ui(1￡i￡n)，加上邊(s,ui)并賦以容量c(s,ui)=12ARi(c) 加上匯點(diǎn)t，然后為V中每個(gè)點(diǎn)vj(1￡j￡n)，加上邊(vj,t)并賦以容量c(vj,t)=12ACj作為例子，下面圖示了由題中矩陣A所構(gòu)造的網(wǎng)絡(luò)。容易看出，這個(gè)網(wǎng)絡(luò)的最大流使所有邊(s,ui)飽和(1￡i￡n)，也使所有邊(vj,t)飽和(1￡j￡n)。這是因?yàn)槲覀兛梢赃@樣構(gòu)造一個(gè)流f：f(s,ui)=c(s,ui)=12ARi (1￡i￡nf(vj,t)=c(vj,t)=12ACj (1￡j￡nf(ui,vj)=12c(ui,vj)=12aij (1￡i,j￡nuu1v1u2u3v2u4v3v4st63255533534321134411顯然這是一個(gè)合法的流，并且使所有邊(s,ui)飽和(1￡i￡n)，也使所有邊(vj,t)飽和。這個(gè)流不一定是整數(shù)流，但因?yàn)榫W(wǎng)絡(luò)中每個(gè)邊容量為整數(shù)，所以必存在有等值的整數(shù)流。下面圖顯示上面圖中網(wǎng)絡(luò)的一個(gè)最大整數(shù)流。uu1v1u2u3v2u4v3v4st6/63/32/25/55/55/53/33/31/53/32/41/31/21/10/12/34/41/40/10/1有了這個(gè)最大整數(shù)流f，置元素bij=f(ui,vj)(1￡i,j￡n)即可構(gòu)成矩陣B={bij}，而置元素cij=c(ui,vj)-f(ui,vj)(1￡i,j￡n)即可構(gòu)造矩陣C={cij}。從上面圖中的最大整數(shù)流所構(gòu)造的矩陣正是題目中例子里的矩陣B和C。因?yàn)榱髁渴睾悖覀冇校篺(s,ui)=12ARi=j=1nf(ui,vj)=j=1nbij=BRi f(vj,t)=12ACj=i=1nf(ui,vj)=i=1nbij=BCj 所以，矩陣B滿足要求。因?yàn)镃Ri=ARi-BRi=12ARi，CCj=ACj–BCj=12ACj，矩陣C(推廣的Hall氏定理)假設(shè)B是二部圖G(U,W,E)中U的一個(gè)子集，而R(B)W是B的映象集合，即R(B)={wW|$u?B使(u,w)?E}。Hall氏定理說，G(U,W,E)有完全匹配的充要條件是，對(duì)任何子集BU，都有|B|￡|R(B)|?，F(xiàn)在，讓我們來推廣這個(gè)定理。讓我們稱差值d(B)=|B|-|R(B)|為集合B的映象差，而集合U的最大映象差則定義為max-d(U)=maxB?Ud(B)。顯然，如果max-d(U)0，那么G有完全匹配。請(qǐng)證明，G的最大匹配的規(guī)模為(n–d)當(dāng)且僅當(dāng)max-d(U)=d，這里n=|U證明： 因?yàn)楫?dāng)max-d(U)=d=0時(shí)，命題就是Hall氏定理，當(dāng)然正確。假設(shè)max-d(U)=d>0。我們先證明，如果max-d(U)=d，G的最大匹配的規(guī)模為n–d。因?yàn)榇嬖诩螧U使得|B|-|R(B)|=d，那么在任何匹配M中，B中的頂點(diǎn)最多可與W中|R(B)|個(gè)頂點(diǎn)相匹配，而其余|B|-|R(B)|=d個(gè)頂點(diǎn)不可能被匹配。因此|M|￡n–d。我們只需證明|M|3n–d即可。如書上第11.4節(jié)，我們只需證明，圖G(U,W,E)對(duì)應(yīng)的單分支網(wǎng)絡(luò)G’(U,W,E’,s,t)中，從源點(diǎn)s到匯點(diǎn)t的最大流至少是n–d。根據(jù)最大流最小割定理，我們只需證明，G’(U,W,E’,s,t)中，任何一個(gè)割(S,T)的容量大于等于n–d。設(shè)V=UW。(S,T)為G’的任意一個(gè)割，SV，T=V–S，sS，tT。假設(shè)集合AU是集合U中屬于T的頂點(diǎn)，B=U-A是集合U中屬于S的頂點(diǎn)。如下圖所示，R(B)W是B的映象集合。設(shè)|A|=k，因此有BíS，|B|=n–k。顯然，每條從源點(diǎn)s到A中點(diǎn)的邊(s,ui)(ui?A)，都是穿越這個(gè)割的邊，一共k條?，F(xiàn)在讓我們檢查R(B)中每個(gè)點(diǎn)w。假設(shè)w與點(diǎn)b?B相鄰，那么如果w?S，那么邊(w,t)穿越這個(gè)割，否則邊(b,w)穿越這個(gè)割?？傊瑢?duì)R(B)中每個(gè)頂點(diǎn)w，都有至少一條關(guān)聯(lián)于w的穿越邊。因?yàn)檫@些穿越邊都不相同，所以這些穿越邊的個(gè)數(shù)至少是|R(B)|。因?yàn)閐(B)=|B|-|R(B)|￡d，我們有|R(B)|3|B|-d=(n–k)–d。加上從源點(diǎn)s到A中點(diǎn)的k條穿越邊，割(S,T)的容量至少是c(S,T)(n-k–d)+k=n–d。所以G的最大匹配的規(guī)模為n–d。我們?cè)僮C明，如果G的最大匹配M的規(guī)模為n–d，那么有max-d(U)=d。因?yàn)槿魏巫蛹疊U中的點(diǎn)最多有d個(gè)點(diǎn)在M中未被匹配，所以|B|-|R(B)|d。所以有max-d(U)=maxB?Ud(B)d。但是max-d(U)不會(huì)小于d。這是因?yàn)?，如果max-d(U)=d’<d，那么，由(A)部分的證明，G的最大匹配M的規(guī)模為n–d’>n–d，產(chǎn)生矛盾。所以必有max-d(U)=假設(shè)一個(gè)n′n矩陣A={aij}中每個(gè)元素是非負(fù)整數(shù)aij0(1￡i,j￡n)，但不是雙隨機(jī)矩陣。我們希望增加某些元素的值（正整數(shù)）使其成為一個(gè)雙隨機(jī)矩陣B。我們要求增加的總數(shù)最少。在下面的例子中，增加的總數(shù)為3+2+1+(1+2)+(1+3)=13。A=01101請(qǐng)把這個(gè)問題建模為一個(gè)網(wǎng)絡(luò)流問題解出。解：首先，我們計(jì)算矩陣A中各行和各列的元素和：ARi=j=1naij(i=1,2,…,n)，ACj=i=1naij顯然有i=1nARi=j=1n然后，計(jì)算最大的行或列的元素和：k=max1≤i≤n這個(gè)k值是雙隨機(jī)矩陣B中最小可能的行或列的元素和。我們的目標(biāo)是雙隨機(jī)矩陣B中每行和每列的元素和為k。為此，我們計(jì)算A中各行和各列的元素和需要增加的總數(shù)，稱為差距：DRi=k-ARi(i=1,2,…,n)，DCj=k-ACj(j=1,2,…,n)。因?yàn)橛衖=1nDRi=nk-i=1nARi和所以有 i=1nDRi現(xiàn)在，構(gòu)造一個(gè)流網(wǎng)絡(luò)G如下：構(gòu)造一個(gè)加權(quán)有向二部圖G(U,V,E)，其中U={u1,u2,…,un},代表矩陣A的n行，而V={v1,v2,…,vn}代表矩陣A的n列。另外，邊的集合是E={(ui,vj)|DRi>0與DCj>0}，并賦以邊(ui,vj)的容量為c(ui,vj)=￥。邊(ui,vj)的含義是，如果有整數(shù)流f(ui,vj)通過，那么把a(bǔ)ij增加一個(gè)整數(shù)f(ui,vj)，即bij=aij+f(ui,vj)。加上源點(diǎn)s和邊(s,ui)并賦以容量c(s,ui)=DRi(i=1,2,…,n)。加上匯點(diǎn)t和邊(vj,t)并賦以容量c(vj,t)=DCj(j=1,2,…,n)。讓我們以題目中矩陣A為例構(gòu)造這個(gè)流網(wǎng)絡(luò)。容易看出k=5。每行每列的差距值如下：DR1=3,DR2=2,DR3=1,DR4=3,DR5=4，DC1=4,DC2=4,DC3=0,DC4=3,DC5=2。構(gòu)造的網(wǎng)絡(luò)如下圖。為清楚起見，邊的方向和一些無窮大的容量均略去。容易看出網(wǎng)絡(luò)G的一個(gè)最小割是(S,T)，其中，S={s}，T=UV{t}，它的容量是c(S,T)=i=1nDRi。所以網(wǎng)絡(luò)G的最大整數(shù)流f使所有從s出去的邊飽和。因流量守恒，我們有f(s,ui)=c(s,ui)=DRi=j=1nf(ui,vj)(i=1,2,…,n)。因?yàn)橛衎ij=aij+f(uij=1nbij=j=1naij=ARi+f(s,ui)=ARi+DRi=k。又因?yàn)閕=1nDRi=j=1nDCj，所以這個(gè)整數(shù)流f也使得所有進(jìn)入?yún)R點(diǎn)t的邊飽和。所以，對(duì)矩陣i=1nbij=i=1n(aij+f(ui,vj))=i=1n因此，B是一個(gè)雙隨機(jī)矩陣。因?yàn)樵黾拥目偭繛閕=1nj=1nf(ui,uu2u5u3u4v2v5v4st3/32/21/14/43/34/44/43/32/23/u1v1211213假設(shè)一個(gè)n′n矩陣A={aij}中每個(gè)元素是非負(fù)整數(shù)aij0(1￡i,j￡n)。它每行元素之和為ARi=j=1naij(i=1,2,…,n)，每列元素之和為ACj=i=1naij(j=1,2,…,n)，并有max1≤i≤n1≤j≤n{ARi,ACj}=k>0。現(xiàn)在我們希望把某些元素值減少一個(gè)整數(shù)后得到一個(gè)矩陣B={bij}使得B的每個(gè)元素仍然是非負(fù)整數(shù)bij0(1￡i,j￡n)，但是每行元素之和以及每列元素之和都小于或等于一個(gè)比k小的非負(fù)整數(shù)d(0d<k)，也就是使BRi=j=1nbijd(i=1,2,…,n)，和BCj=i=1nbijd(j=1,2,…,n)。另外，我們要求減少的總數(shù)最小。例如，如果A=01102001001001請(qǐng)用網(wǎng)絡(luò)流的模型來為這個(gè)問題設(shè)計(jì)一個(gè)算法。解： 我們先做一些計(jì)算。首先，為每一行i(i=1,2,…,n)，計(jì)算ERi=max(ARi–d,0)，這里ARi=j=1naij。如果ERi>0，說明第i行的元素和大于d，我們必須把這行中某些元素減少，減少的總量至少是ERi，稱為冗余量。然后，為每一列j(j=1,2,…,n)，計(jì)算ECj=max(ACj–d,0)，這里ACj=i=1naij。如果ECj>0，說明第j列的元素和大于d，我們必須把這列中某些元素減少，現(xiàn)在，由上面的計(jì)算，我們來構(gòu)造一個(gè)流網(wǎng)絡(luò)G如下：構(gòu)造一個(gè)加權(quán)二部圖G(U,V,E)，這里U={u1,u2,…,un}代表矩陣A的n行，V={v1,v2,…,vn}代表矩陣A的n列。另外，如果aij>0，則構(gòu)造邊(ui,vj)，并且賦以容量c(ui,vj)=aij。加入源點(diǎn)s以及到每個(gè)U中點(diǎn)ui的邊(s,ui)(1￡i￡n)并賦以容量c(s,ui)=ERi。加入?yún)R點(diǎn)t以及從每個(gè)V中點(diǎn)vj到t的邊(vj,t)(1￡i￡n)并賦以容量c(vj,t)=ECj。我們用上面矩陣A作例子。先計(jì)算ER1=1，ER2=0，ER3=1，ER4=2，ER5=0，EC1=0，EC2=0，EC3=3，EC4=0，EC5=0。下圖是對(duì)應(yīng)的流網(wǎng)絡(luò)。為清楚起見，每條邊方向被省略。vv1u1u2u5u3u4v2v5v4st101020000v3223111111111流網(wǎng)絡(luò)構(gòu)造好以后，算法如下：Minimum-matrix-reduction(G,d)計(jì)算G的從s到t的最大整數(shù)流f構(gòu)造nn矩陣C={cij}使得cij=f(ui,vj)(1￡i,j￡n)BA–Cfori=1ton BRij=1 ifBRi>d then j1 yBRi-d whiley>0 bijbij–min{y,bij} cijcij+min{y,bij} yy-min{y,bij} jj+1 endwhile endifendforforj=1ton BCji=1 ifBCj>d then i1 yBCj-d whiley>0 bijbij–min{y,bij} cijcij+min{y,bij} yy-min{y,bij} ii+1 endwhile endifendforEnd用上面圖中網(wǎng)絡(luò)為例，它的最大流如下圖所示。為清楚起見，該圖只顯示有流經(jīng)過的邊。其對(duì)應(yīng)的矩陣C顯示在圖下方。注意，從最大流獲得對(duì)應(yīng)的矩陣C后，B=A–C不一定能滿要求。這時(shí)，要檢查B中每一行和每一列，如果發(fā)現(xiàn)某行或某列的元素之和仍大于d，則須要在這一行中，或這一列中把一些元素減少使這個(gè)和正好為d。算法笫4行和第17行的兩個(gè)for循環(huán)就是為此目的。uu1u3u4st1/11/11/2v31/23/31/11/1A=01102001001001注意，上面例子中的矩陣B的第4行不滿足要求。算法笫4行的for循環(huán)把B中元素(4,2)減去1，而C中元素(4,2)加1。所以，最后的矩陣C和B如下：A=01102001001001算法的正確性證明如下。首先，算法笫4行和第17行的兩個(gè)for循環(huán)保證得到的矩陣B是滿足要求的。我們只需證明減去的總數(shù)最小。我們注意到，從行的角度看，我們必須減少的總的冗余量為i=1nERi，而從列的角度看，我們必須減少的總的冗余量為j=1nECj。兩者之和為T=i=1nERi+j=1nECj。當(dāng)我們計(jì)算了最大流以后，置cij=f(ui,vj)。所以，當(dāng)我們從aij減去cij現(xiàn)在考慮任何一個(gè)解。在這個(gè)解中，有些元素的減少會(huì)同時(shí)減少行和列的冗余量，有些則只會(huì)減少行或列的冗余量但不同時(shí)減少兩者。假設(shè)這個(gè)解把元素aij減少一個(gè)數(shù)時(shí)，同時(shí)減少了第i行的冗余量和第j列的冗余量。如果這個(gè)共同減少的部分是cij，那么我們可以在網(wǎng)絡(luò)中給邊(ui,vj)賦以流量f(ui,vj)=cij。然后，我們給邊(s,ui)賦以流量f(s,ui)=j=1ncij，給邊(vj,t)賦以流量f(vj,t)=i=1ncij。注意，流量f(s,ui)=j=1ncij不會(huì)大于容量c(s,ui)=ERi。這是因?yàn)椋绻笥赾(s,ui)=ERi，則必有元素aij，其減少的共同部分cij不正確，太大了，不會(huì)最優(yōu)。同理，流量f(vj,t)=i=1ncij也不會(huì)大于容量c(vj,t)=假設(shè)這個(gè)解中減少的冗余量的其余部分是y，即這部分只減少行或列的冗余量但不同時(shí)減少兩者。那么，我們有2x+y=i=1nERi+j=1nECj=T。因此，這個(gè)解從矩陣A減少的總數(shù)是x+y=T–x。這個(gè)值當(dāng)假設(shè)f是網(wǎng)絡(luò)G(V,E)的一個(gè)預(yù)流，而h是其高度函數(shù)。證明，如果剩余網(wǎng)絡(luò)Gf中的某一頂點(diǎn)v有高度h(v)n，那么在Gf中，v以及v有路徑到達(dá)的點(diǎn)都沒有路徑到t，而且在以后的任何時(shí)刻，他們也不會(huì)有路徑到t。證明： 我們先用反證法證明在剩余圖Gf中，頂點(diǎn)v以及v有路徑到達(dá)的點(diǎn)沒有路徑到t。假設(shè)不是，則有一條從v到t的簡(jiǎn)單路徑，v0,v1,…,vk，其中v=v0，t=vk，并有kn-1。那么根據(jù)高度函數(shù)的定義有：h(v0)h(v1)+1h(v2)+2…h(huán)(vk)+k=0+k=k。因?yàn)閔(v)n，我們有nh(v0)kn-1。這不可能，所以v沒有路徑到t。顯然，任何一個(gè)點(diǎn)u，如果有從v到u的路徑，那么，一定沒有從u到t的路徑，否則就會(huì)有從v到t的路徑而矛盾。現(xiàn)在用反證法證明，在以后的任何時(shí)刻，這些頂點(diǎn)也不會(huì)有路徑到t。假設(shè)不是，則有點(diǎn)u(可以是v本身)，它在當(dāng)前的Gf中有一條從v到u的簡(jiǎn)單路徑，v0,v1,…,vk，其中v=v0，u=vk，而在以后某個(gè)時(shí)刻的剩余圖Gf*中有一條從u到t的簡(jiǎn)單路徑，u0,u1,…,uk*，其中u=u0，t=uk*。我們可假定在路徑u0,u1,…,uk*中，除u=u0外，不含v0,v1,…,vk中任何一個(gè)點(diǎn)。否則的話，可以選取u0,u1,…,uk*中最右邊一個(gè)出現(xiàn)在序列v0,v1,…,vk中的點(diǎn)取代u。根據(jù)高度函數(shù)的定義，在Gf*中有：h*(u)h*(u1)+1h*(u2)+2…h(huán)*(uk*)+k*=0+k*=k*。這里，h*表示在剩余圖Gf*中的高度函數(shù)。而在原先Gf中有：nh(v0)h(v1)+1h(v2)+2…h(huán)(vk)+k=h(u)+k。因?yàn)轫旤c(diǎn)u的高度不減，h(u)≤h*(u)≤k*，所以有n≤k*+k。因?yàn)樯厦鎯蓚€(gè)序列，v0,v1,…,vk，和u0,u1,…,uk*中一共有k+k*+1個(gè)不同頂點(diǎn)，那么網(wǎng)絡(luò)中至少有n+1個(gè)頂點(diǎn)，這不可能。(a)在一個(gè)nn的棋盤上，我們用(i,j)表示在第i行，第j列的格子(1i,jn)。這些格子中，有一些格子不可用，其余可用。我們用B(i,j)=0表示格子(i,j)不可用，B(i,j)=1表示可用。我們的問題是，在可用的格子中找出最大的一組不同行和不同列的格子。也就是說，每一行最多可以選一個(gè)可用格子，每一列也最多可以選一個(gè)可用格子。請(qǐng)用下面圖示的88棋盤的例子說明如何把這個(gè)問題建模為一個(gè)二部圖的匹配問題。(b)為下面圖示的88棋盤的例子找出最大的一組不同行和不同列的可用格子。11234567821348657陰影的格子表示不可用B(i,j)=0解： 我們構(gòu)造一個(gè)二部圖G(U,V,E)如下：U={u1,u2,…,un}，其中，ui代表棋盤的第i行(1≤i≤n)。V={v1,v2,…,vn}，其中，vj代表棋盤的第j列(1≤j≤n)。如果B(i,j)=1，格子(i,j)可用，則構(gòu)造邊(ui,vj)。也就是E={(ui,vj)|B(i,j)=1,1≤i,j≤n}。下面圖(a)顯示了由題中例子所構(gòu)造的二部圖。顯然，二部圖G(U,V,E)的最大匹配對(duì)應(yīng)一組最大的不同行和不同列的可用格子，也就給出了本題的解。uu1u2u3u4u5v1v2v3v4v5u6u7u8v6v7v8(a)(b)下圖(b)顯示了上面二部圖(a)的一個(gè)最大匹配。下圖(c)顯示的是對(duì)應(yīng)于圖(b)中最大匹配的一組最大的不同行和不同列的可用格子uu1

u2

u3u4u5v1

v2

v3v4v5u6u7u8v6v7v8(b)11234567821348657陰影的格子表示不可用B(i,j)=0黑色的格子表示選取的可用格子(c)假設(shè)圖G(L,R,E)是一個(gè)二部圖，其中LR是頂點(diǎn)的集合。E中任何一條邊關(guān)聯(lián)L中的一個(gè)點(diǎn)和R中的一個(gè)點(diǎn)。另外，集合L中的任何一個(gè)點(diǎn)u有度數(shù)d(u)≥5，而集合R中的任何一個(gè)點(diǎn)v有度數(shù)d(v)5。證明圖G有完全匹配。證明： 我們證明這個(gè)二部圖滿足Hall氏定理，即集合L中的任何一個(gè)子集SL，都有|S|≤|R(S)|。讓我們定義E’為集合S和R(S)之間的所有邊的集合，再定義E’’為集合L和R(S)之間的所有邊的集合。因?yàn)镾L，所以有E’E’’，|E’||E’’|。下面的圖顯示了集合S和R(S)之間的關(guān)系。因?yàn)榧螸中的任何一個(gè)點(diǎn)u有度數(shù)d(u)≥5，所以有5|S||E’|。又因?yàn)榧蟁(S)中的任何一個(gè)點(diǎn)v有度數(shù)d(v)5，所以有|E’’|5|R(S)|。把以上的不等式連起來，我們有：5|S||E’||E’’|5|R(S)|，也就是|S|≤|R(S)|。 SRSR(S)LR邊的個(gè)數(shù)|E’|滿足E’|≥5|S|邊的個(gè)數(shù)|E’’|滿足|E’||E’’|≤5|R(S)|假設(shè)有n個(gè)研究生，g1,g2,…,gn，參加不同項(xiàng)目的物理實(shí)驗(yàn)的競(jìng)賽，但每個(gè)研究生必須有兩個(gè)本科生做助手，組成一個(gè)小組。又假設(shè)有2n個(gè)本科生可選，他們是u1,u2,…,u2n。但是，因?yàn)轫?xiàng)目的不同，不是每個(gè)本科生都合格參加所有項(xiàng)目的競(jìng)賽。也就是說，每個(gè)本科生只能合格參加某幾個(gè)項(xiàng)目的物理實(shí)驗(yàn)。換句話說，每個(gè)研究生只能從合格的本科生中選取兩個(gè)與之組成一個(gè)小組。另外，因?yàn)樗许?xiàng)目的競(jìng)賽是在同一個(gè)時(shí)間進(jìn)行，每個(gè)人只能參加一個(gè)項(xiàng)目的競(jìng)賽。我們的目標(biāo)是把這n個(gè)研究生和2n個(gè)本科生組成正好n個(gè)競(jìng)賽小組。請(qǐng)用下面的例子來說明，怎樣把這個(gè)問題建模為一個(gè)網(wǎng)絡(luò)流的問題以確定是否可能。如果可能，輸出這n個(gè)競(jìng)賽小組的組成。5個(gè)研究生是: g1,g2,g3,g4,g510個(gè)本科生是: u1,u2,u3,u4,u5,u6,u7,u8,u9,u10 可以與每個(gè)研究生配合的本科生集合如下：可與g1配合的本科生集合是:{u1,u3,u5,u9}可與g2配合的本科生集合是:{u1,u7,u8}可與g3配合的本科生集合是:{u2,u4,u5,u6,u10}可與g4配合的本科生集合是:{u3,u6,u8}可與g5配合的本科生集合是:{u2,u4,u5,u10}。解: 我們構(gòu)造一個(gè)流網(wǎng)絡(luò)如下：構(gòu)造有向二部圖G(L,R,E)，其中L={g1,g2,…,gn}代表n個(gè)研究生，R={u1,u2,…,u2n}代表2n個(gè)本科生。如果本科生uj可以與研究生gi配合，則在集合E中加上一條有向邊(gi,uj)，容量為1。在圖中加上一個(gè)源點(diǎn)s。從源點(diǎn)s到每一個(gè)L中點(diǎn)gi(1in)加上一條有向邊(s,gi)，容量為2。在圖中加上一個(gè)匯點(diǎn)t。從每一個(gè)R中點(diǎn)uj(1j2n)加上一條到匯點(diǎn)t的有向邊(uj,t)，容量為1。下圖顯示的是由題中例子所構(gòu)造的流網(wǎng)絡(luò)。為清晰起見，容量是1的邊不標(biāo)注容量。uu10g1g2g3g4g5u1u2u3u4u5u6u7u8u9ts22222構(gòu)造好流網(wǎng)絡(luò)之后，計(jì)算它的最大整數(shù)流f。如果|f|=2n，那么，問題有解。這時(shí)，經(jīng)過頂點(diǎn)gi(1in)的流必定是2。因?yàn)槭钦麛?shù)流，必定有兩條邊，(gi,uj)和(gi,uk)，使得f(gi,uj)=1和f(gi,uk)=1(1j,k2n)，jk。我們可以把本科生uj和uk配給研究生gi。因?yàn)閨f|=2n，經(jīng)過頂點(diǎn)uj的流必定是1(1j2n)，所以，存在一個(gè)頂點(diǎn)gi(1in)，使得，f(gi,uj)=1和f(uj,t)=1。所以，每個(gè)本科生會(huì)配給正好1個(gè)研究生。下圖顯示的是對(duì)應(yīng)題目中流網(wǎng)絡(luò)的最大流以及問題的解。1/11/11/11/11/11/11/1u1

u10g1

g2

g3g4g5u2

u3u4u5u6u7u8u9ts2/22/22/22/22/21/11/11/11/11/11/11/11/11/11/11/11/11/11/11/11/1這5個(gè)競(jìng)賽小組是：{g1,u1,u9}{g2,u7,u8}{g3,u2,u4}{g4,u3,u6}{g5,u5,u10}給定一個(gè)圖G(V,E)，如果V的子集V’V中任意兩點(diǎn)之間沒有邊，那么V’稱為是一個(gè)獨(dú)立集。最大獨(dú)立集問題就是要找出圖G的一個(gè)最大的獨(dú)立集，即含有最多頂點(diǎn)的獨(dú)立集。如果G是一個(gè)樹T，那么，這個(gè)最大獨(dú)立集問題可以在O(n)時(shí)間內(nèi)解決(見第8章習(xí)題19)?，F(xiàn)在，假設(shè)G(V,E)是一個(gè)二部圖，請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n2.5)的算法為G找出一個(gè)最大獨(dú)立集并證明其正確性。這里，n=|V|。解： 設(shè)頂點(diǎn)集合的兩部分是L和R，V=LR，LR=，G(V,E)=G(L,R，E)算法的偽碼如下。Maximum-Independent-Set-Bipartite-Graph(G(L,R，E),I) //屬出最大的獨(dú)立集I計(jì)算由G(L,R，E)構(gòu)造的網(wǎng)絡(luò)的最大流f，并得到L和R之間的最大匹配ML1{u|uL并且有邊(u,v)M}R1{v|vR并且有邊(u,v)M}L2L-L1R2R-R1L3{u|uL1并且u在二部圖G中有路徑可達(dá)L2中某一點(diǎn)}R3{v|vR1并且v在二部圖G中有路徑可達(dá)L2中某一點(diǎn)}L4{u|uL1并且u在二部圖G中有路徑可達(dá)R2中某