PresentedbySiWenjunABriefIntroductionto

NETWORKFLOW引述：三類問題實(shí)際問題中，我們常常會(huì)遇到以下幾類問題：分配(Distribution)匹配(Matching)切割(Cut)這些問題很多情況下都可以使用網(wǎng)絡(luò)流解決。引述：分配(Distribution)在一個(gè)存在流量限制的網(wǎng)絡(luò)中，將物體從一處移到另一處。例如：貨物從產(chǎn)地經(jīng)過各中轉(zhuǎn)站運(yùn)送到零售商；網(wǎng)絡(luò)中兩臺(tái)服務(wù)器間的數(shù)據(jù)；交通線路；電力供應(yīng)(POJ1459:PowerNetwork)引述：分配(Distribution)一個(gè)流量分配問題實(shí)例引述：匹配(Matching)此時(shí)網(wǎng)絡(luò)代表連接節(jié)點(diǎn)的可能性。目標(biāo)為找出節(jié)點(diǎn)間的一一配對(duì)。例如：安排工作選課(POJ2239:SelectingCourses)最小距離匹配引述：匹配(Matching)一個(gè)匹配的例子：找工作引述：切割(Cut)刪除一些邊使網(wǎng)絡(luò)分為兩部分或更多我們?cè)诤竺鎸?huì)看到，盡管割與前面提到的流量分配差異巨大，但是，兩者緊密地聯(lián)系在一起。割的例子：網(wǎng)絡(luò)的穩(wěn)定性切斷敵軍供應(yīng)線人與人失去聯(lián)系(POJ1815:Friendship)引述還有很多問題可以使用網(wǎng)絡(luò)流解決。例如：任務(wù)調(diào)度。POJ上的可用網(wǎng)絡(luò)流解決問題不完全列表1087127312741422145914691698171918152060219522391149概念：流網(wǎng)絡(luò)(FlowNetworks)有向圖G=(V,E)兩個(gè)特殊節(jié)點(diǎn)：源(Source)和匯(Sink)每一條邊包含一個(gè)容量概念：流(PositiveFlow)邊的另一非負(fù)權(quán)值，滿足的性質(zhì)：受容量限制(CapacityConstraint)流在源、匯以外節(jié)點(diǎn)的“守恒”(FlowConservation)(聯(lián)想：基爾霍夫電流定律)總流量：源的凈流出。概念舉例流守恒：流入u的流量：3；流出u的流量：3總流量：3最大流(MaximalFlow)對(duì)于給定的流網(wǎng)絡(luò)G，找出使總流量最大的流分布。對(duì)以上網(wǎng)絡(luò)，最大流為4性質(zhì)對(duì)以上流網(wǎng)絡(luò)的定義，有以下定理：定理一：源的凈流出量與匯的凈流入量相等。為證明此定理，先證明引理：對(duì)

，S的流入量與S的流出量相等。證明：任取，由流守恒知該節(jié)點(diǎn)流入與流出相等；另取一節(jié)點(diǎn)，則集合

流入量為：

流出量為：性質(zhì)

根據(jù)流守恒，兩者相等。此時(shí)可以將S等效為一個(gè)新的節(jié)點(diǎn)p’’，p’’滿足流網(wǎng)絡(luò)的定義。由歸納法可知引理成立。對(duì)原網(wǎng)絡(luò)增加兩個(gè)節(jié)點(diǎn)a、b，a指向s，c(a,s)=s的凈流出，t指向b，c(t,b)=t的凈流入，則此時(shí)s，t滿足流守恒。由引理，在新的流網(wǎng)絡(luò)中，c(a,s)=c(t,b)。因此，在原流網(wǎng)絡(luò)中，s的凈流出量與t的凈流入量相等?！跣再|(zhì)推論：兩個(gè)頂點(diǎn)集合并集的流等于兩集合流的和減去兩集合間的流。證明：將原引理證明中的頂點(diǎn)替換為頂點(diǎn)集合即可?！醐h(huán)流(Circulations)由定理一知，一個(gè)流網(wǎng)絡(luò)的凈流入等于它的凈流出。因此我們可以在網(wǎng)絡(luò)中增加一條由匯指向源的邊，該邊流量等于網(wǎng)絡(luò)凈流量。由推論，易知該環(huán)流網(wǎng)絡(luò)中任意頂點(diǎn)集合滿足流守恒。此時(shí)流的問題可以轉(zhuǎn)化為某條邊上的最大流量問題。環(huán)流：流分解定理定理二（環(huán)流分解定理）：任意環(huán)流可被分解為至多流經(jīng)E個(gè)環(huán)的環(huán)流之和。證明：采用以下方法構(gòu)造所求的環(huán)：從任意存在流的邊起，任取一條以該邊終點(diǎn)為起點(diǎn)的存在流的邊，重復(fù)此過程直到回到任一已被訪問的頂點(diǎn)S。（一定存在這樣一條路，為什么？）取這個(gè)環(huán)上每條邊流的最小值，使環(huán)上每條邊流量減去該值。環(huán)流：流分解定理

易知，經(jīng)過減小的環(huán)流網(wǎng)絡(luò)各頂點(diǎn)仍然符合流守恒。重復(fù)以上步驟直至結(jié)束。因?yàn)槊看螠p小都至少使一條邊上流量減為0，因而至多可以找到E個(gè)環(huán)?！趵涵h(huán)流例：環(huán)流例：環(huán)流例：環(huán)流環(huán)流回到一般流網(wǎng)絡(luò)，由定理二可得以下推論：推論二：任意流網(wǎng)絡(luò)都有最大流，使得非零流量子圖無(wú)環(huán)。證明：仍然引進(jìn)邊t→s。易知任意不包含t→s邊的環(huán)對(duì)流量無(wú)貢獻(xiàn)。因此按定理二中過程第二步減小流量。重復(fù)此過程可使網(wǎng)絡(luò)中無(wú)環(huán)。□推論三：任意流網(wǎng)絡(luò)都有從s到t，至多E條路徑上的最大流。增廣路(AugmentPath)算法如何找到最大流？一個(gè)很自然的想法：沿著一切可能的從s到t的路徑增大流量，直到無(wú)法增加為止。是否正確呢？錯(cuò)誤！增廣路算法：反例最大流：19錯(cuò)誤！最大流：20正確錯(cuò)誤原因過早地認(rèn)為邊1→2上流量不為0，因而“封鎖”了流量繼續(xù)增大的可能。一個(gè)改進(jìn)的思路：改進(jìn)定義，使算法能夠修改已建立的流網(wǎng)絡(luò)，使得建立的“不合理”的流量被刪掉。一種實(shí)現(xiàn)：對(duì)每條邊建立“反向”的容量，利用“反向”的容量尋找路徑。殘余網(wǎng)絡(luò)(ResidualNetwork)以上a(u,v)的定義事實(shí)上給出了一個(gè)新圖，圖的權(quán)值為a(u,v)。稱該圖為流網(wǎng)絡(luò)的殘余網(wǎng)絡(luò)。其中，a(u,v)=0的邊不實(shí)際存在。例：殘余網(wǎng)絡(luò)上頁(yè)中流網(wǎng)絡(luò)的殘余網(wǎng)絡(luò)。對(duì)2→s的解釋：3=1+2，1增加2→s的流量，2反向減小s→2的流量。Ford-Fulkerson算法從流量為0開始，沿殘余網(wǎng)絡(luò)尋找增廣路徑，沿路徑增加流量，直到增廣路徑找不到。算法框架：WHILE(增廣路徑存在)[

沿路徑增廣;]該算法證明需要補(bǔ)充割的定義。割(Cut)回想先前給出的問題模型。定義：割：頂點(diǎn)集合S、T，滿足：S∪T=VS∩T=Φs∈S，t∈T性質(zhì)：經(jīng)過流網(wǎng)絡(luò)任意割的流量與流網(wǎng)絡(luò)流量相等。（為什么？）割(Cut)定義：割的容量(CapacityofaCut)性質(zhì)：流網(wǎng)絡(luò)的流量不超過任何割的容量。最大流最小割定理

TheMaxflow-MincutTheorem以下命題等價(jià)：f=min{c(S,T)}，(S,T)取所有割；f是最大流；殘留網(wǎng)絡(luò)中無(wú)增廣路徑。證明：（①→②，②→③，③→①）①→②：∵f≤c(S,T)，∴c(S,T)=f等價(jià)于f為最大流。②→③：如果增廣路徑存在，那么f不是最大流。最大流最小割定理

TheMaxflow-MincutTheorem③→①：假設(shè)殘留網(wǎng)絡(luò)中不存在增廣路徑，規(guī)定S為s在殘余網(wǎng)絡(luò)中能夠達(dá)到的頂點(diǎn)集合。顯然，。T=V-S。從而(S,T)是一個(gè)割。對(duì)于殘余網(wǎng)絡(luò)中a(u,v)，u∈S，v∈T，一定有a(u,v)=0。∴c(S,T)=f。□Ford-Fulkerson算法算法正確性：由最大流最小割定理知，當(dāng)算法完成時(shí)，形成的割為最小割，故經(jīng)過最小割的為最大流?！踝⒁猓阂陨蠈?duì)Ford-Fulkerson算法的正確性討論僅限于整數(shù)流。對(duì)實(shí)數(shù)流，尋找殘余網(wǎng)絡(luò)的過程可能陷于死循環(huán)。算法拓展Ford-Fulkerson算法只是增廣路徑最大流算法的總稱。對(duì)以下兩方面的討論可以影響算法的效率：完成最大流需要找到的增廣路數(shù)目；找到增廣路的效率。常見算法：直接DFS最短增廣路算法(Edmonds-Karp)最大容量增廣路算法Dinic算法最大容量增廣路算法利用類似Dijkstra的方法找出從s到t的剩余容量最大的增廣路。時(shí)間復(fù)雜度O(V2log2Mlog2V)詳見maxcap.cpp。最短增廣路算法(Edmonds-Karp)每次在殘余網(wǎng)絡(luò)中利用BFS找到s到t邊數(shù)最少的路徑。效率：O(V3)詳見ekarp.cpp。Dinic算法Edmonds-Karp的提高余地：需要多次從s到t調(diào)用BFS，可以設(shè)法減少調(diào)用次數(shù)。亦即：使用一種代價(jià)較小的高效增廣方法?？紤]：在一次增廣的過程中，照顧到多于一條路徑。DFSDinic算法利用BFS對(duì)殘余網(wǎng)絡(luò)分層Dinic算法利用BFS對(duì)殘余網(wǎng)絡(luò)分層，利用DFS從前一層向后一層反復(fù)尋找增廣路。Dinic算法一次DFS過程具體實(shí)現(xiàn)請(qǐng)參考dinic.cpp謝謝本節(jié)只是對(duì)網(wǎng)絡(luò)流的簡(jiǎn)要介紹。下次將由潘昊同學(xué)為大家介紹預(yù)流推進(jìn)算法，王小龍同學(xué)為大家介紹最小費(fèi)用流和流模型的靈活應(yīng)用專題。網(wǎng)絡(luò)流是一個(gè)應(yīng)用廣泛的發(fā)展領(lǐng)域，許多方面還有提高潛力。感興趣的同學(xué)可以參考NetworkFlows:Theory,Algorithms,andApplications(byAhuja,R.K.)謝謝祝大家明天校內(nèi)賽發(fā)揮順利！參