網(wǎng)路流與圖匹配-建中首頁課件

1、網(wǎng)路流與圖匹配Network Flow and Graph Matching網(wǎng)路流的歷史網(wǎng)路流(Network Flow)是近年來在圖論中相當(dāng)熱門的問題，在1955年 ，T.E. Harris在研究鐵路最大通量時，首先提出在一個給定的網(wǎng)路上尋求兩點(diǎn)間最大運(yùn)輸量的問題。1956年，L.R. Ford和D.R. Fulkerson給出解決這類問題的演算法，從而建立了網(wǎng)路流理論。 網(wǎng)路流的定義網(wǎng)路(Network)：圖G = ( V, A )為一有向圖，稱為網(wǎng)路源點(diǎn)與匯點(diǎn)(Source and Sink)：令一點(diǎn)S為源點(diǎn)、一點(diǎn)T為匯點(diǎn)，其餘為中間點(diǎn) 容量(Capacity)：每條弧上定義一個非負(fù)數(shù)C

2、(u, v)為該弧的容量流量(Flow)：每條弧上定義一個非負(fù)數(shù)F(u, v)為流量，所有流量的集合則稱為網(wǎng)路的一個流。網(wǎng)路流的定義剩餘容量(Residual Capacity)：每條弧上定義一個非負(fù)數(shù)Cf(u, v) = C(u, v) F(u, v) 為該弧的剩餘容量，而剩餘容量的集合則稱為剩餘網(wǎng)路(Residual Network)網(wǎng)路的流量(Flow of Network)：由源點(diǎn)發(fā)出，匯點(diǎn)匯集的總流量，若其為該網(wǎng)路能產(chǎn)生的最大流量，則稱其為最大流(Maximum Flow)。網(wǎng)路流的限制 容量限制(Capacity Constraints)：所有的F(u, v) C(u, v) (流

3、量不大於容量) 流量守恆(Flow Conservation)：對非源點(diǎn)或匯點(diǎn)的點(diǎn)，流入的流量和等於流出的流量和 源點(diǎn)流出的總流量等於流進(jìn)匯點(diǎn)的總流量斜對稱(Skew Symmetry) ：對於所有的F(u, v) + F(v, u) = 0，由u到v淨(jìng)流量加上由v到u的淨(jìng)流量必須為零?？尚辛?Positive Flow)：若一流符合上述三點(diǎn)限制，則稱其為可行流。網(wǎng)路流的弧飽和?。喝粢粭l弧的流量恰好等於容量，則稱其為飽和弧。不飽和弧：若一條弧的流量小於容量，則稱其為不飽和弧。零流弧：若弧的流量為零，稱其零流弧，反之稱非零流弧。前向弧與後向?。涸O(shè)W為一由源點(diǎn)到匯點(diǎn)的有向路徑，並定義由源點(diǎn)到匯點(diǎn)的

4、方向?yàn)樵撀窂降姆较?，若路徑上的弧方向與路徑相同，稱其為前向弧，反之為後向弧。增廣路徑設(shè)f是一個可行流，W是源點(diǎn)到匯點(diǎn)的一條有向路徑，如果W滿足下列的兩個條件，稱之為關(guān)於可行流f的一條增廣路徑：每條前向弧是非飽和弧每條後向弧是非零流弧也就是說，整條增廣路徑上的Cf(uk,uk+1)大於零，這就代表我們一定可以在這條增廣路徑上的每一條弧上加一流量d，使整個流仍然是可行流並使網(wǎng)路的總流量增加d。割集割集設(shè)流量網(wǎng)路G=(V,A)的頂點(diǎn)集V是兩不交的部分S, S的聯(lián)集，使源點(diǎn)S，匯點(diǎn)在S中。 若A是A的最小的子集，使得G中去掉A後成為兩個不相交的子圖，分別以S, S為頂點(diǎn)集，則稱A是關(guān)於(S,S)的割集

5、，而A裡的總?cè)萘縿t稱為割的容量。而若A為G所能產(chǎn)生的割集中容量和最小的，則稱A為最小割(Minimum Cut)網(wǎng)路最大流問題給定一個流量網(wǎng)路 G = ( V , A )，並指定一點(diǎn)為源點(diǎn)，一點(diǎn)為匯點(diǎn)，要求求出此網(wǎng)路的最大流量為何。s1243t1613104912714420Ford-Fulkerson方法利用殘餘網(wǎng)路的概念每次隨意找一條增廣路徑，修正殘餘網(wǎng)路（亦須對後向弧作更正），並增加路徑中最小的容量作為增加流量，直到找不到增廣路徑為止，而先前累積的流量則為最大流量，複雜度為O(Ef)，f為網(wǎng)路的最大流。Ford-Fulkerson方法過程s1243t1613104912714420124

6、845410404流量增加4目前流量為4Ford-Fulkerson方法過程s1243t1310458710020124444451131131107137流量增加7目前流量為13Ford-Fulkerson方法過程s1243t1335800444511113117137流量增加8目前流量為2105831112515Ford-Fulkerson方法過程s1243t5115000124451133117515流量增加4目前流量為25819112091Ford-Fulkerson方法過程s1243t1119000120451133117119已無法找到增廣路徑。最大流為25。12實(shí)現(xiàn)Ford-Fu

7、lkerson方法-Edmonds-Karps算法算法：原理與Ford-Fulkerson相同，但是以廣度優(yōu)先搜尋增廣路徑，效率較隨機(jī)找高。可避免上述情況s12t以及s21t交替出的話最差須找2,000,000,000次。st121,000,000,0001,000,000,0001,000,000,00011,000,000,000例題 網(wǎng)際網(wǎng)路頻帶給任兩點(diǎn)間的線路容量，線路是雙向的，且任兩點(diǎn)間可能有不只一條線路，求某兩點(diǎn)之間的最大流量。例題 草地排水農(nóng)夫約翰知道每一條排水溝每分鐘可以流過的水量，和排水系統(tǒng)的準(zhǔn)確佈局（起點(diǎn)為水潭而終點(diǎn)為小溪的一張網(wǎng)）。需要注意的是，有些時候從一處到另一處不只

8、有一條排水溝。 根據(jù)這些信息，計算從水潭排水到小溪的最大流量。對於給出的每條排水溝，雨水只能沿著一個方向流動，注意可能會出現(xiàn)雨水環(huán)形流動的情形。最大流最小割定理在一個流量網(wǎng)路G中，以下三個條件為等價條件 ：有一流f 為G的最大流 G的殘餘網(wǎng)路沒有增廣路徑 存在一割C，其容量為流量f 假設(shè)割集中連接分屬兩點(diǎn)集的u,v，我們可以確定Cf(u, v) = 0 (否則會產(chǎn)生一條增廣路徑使得v在所屬的集合中)又因?yàn)镃f(u, v) = C(u, v) - F (u, v)，得到C(u, v) = F (u, v)，又因?yàn)槎ɡ碇?.3，所以推得C為最小割 。最大流最小割定理證明12 若在f的殘餘網(wǎng)路中存在

9、增廣路徑，那麼f就肯定不是最大流，逆否命題成立。23假設(shè)f的殘餘網(wǎng)路中不存在增廣路徑，就代表說源點(diǎn)及匯點(diǎn)之間沒有路徑，先設(shè)立一個集合S代表源點(diǎn)所無法抵達(dá)的點(diǎn)，以及集合T代表除了S之外的所有點(diǎn)，設(shè)u為S中一點(diǎn)、v為T中一點(diǎn)，uv之間的流量必等於其割值，因此得證。最大流最小割定理證明31因?yàn)閒 = F (S,T) = F(u,v) C(u,v) = C(S,T)對於每個ST割集 f都不大於C(S,T)，所以當(dāng) f = C(S,T)時，f 為該網(wǎng)路的最大流。最小割集的求法由於最大流等於最小割，因此最小割的弧一定是飽和弧，在剩餘網(wǎng)路的容量則為0。所以我們可以從源點(diǎn)開始沿著剩餘網(wǎng)路的前向弧搜索，直到找到

10、每條路徑的第一條容量為0的弧，而那些弧就會是最小割集了！例題汙染控制光明牛奶公司不小心發(fā)送了一批壞牛奶。你知道這批牛奶要發(fā)給哪個零售商，但是要把這批牛奶送到他手中有許多種途徑。送貨網(wǎng)由一些倉庫和運(yùn)輸卡車組成，每輛卡車都在各自固定的兩個倉庫之間單向運(yùn)輸牛奶。停止每輛卡車都會有一定的經(jīng)濟(jì)損失。你的任務(wù)是，在保證壞牛奶不送到零售商的前提下，制定出停止卡車運(yùn)輸?shù)姆桨?，使損失最小。點(diǎn)容量一般網(wǎng)路流的限制只在邊上做限制，對點(diǎn)只要符合流量守恆就好了，但是如果給定一個點(diǎn)的流量限制呢？做法很簡單，既然只能在邊上做限制，那就把點(diǎn)當(dāng)作邊吧，我們把一個點(diǎn)拆成兩個點(diǎn)連結(jié)的邊，並在上面做限制，如此一般就可以輕易做到在點(diǎn)上

11、的容量了！sss例題電力輸送DESA正在進(jìn)行一項(xiàng)電力傳輸?shù)挠嫯?。由?Dhaka 的人口數(shù)相當(dāng)多，DESA 希望盡可能透過網(wǎng)路傳輸最大的電力給它。但是電力在傳輸時會因電阻而損失，所以他們想要使用變電裝置來達(dá)到不損失電力的目標(biāo)。每個變電裝置有不同的容量。並且連接變電裝置之間的電線也是有一定的容量的。DESA 想要知道在沒有電力損失的情況下，最多可以傳輸?shù)碾娏κ嵌嗌佟＿@就是你的任務(wù)。例題很火的程式設(shè)計師你老闆把你資遣了，所以你很火。你決定要展開報復(fù)，讓你老闆再也連不上網(wǎng)路打Heuristic Game。你老闆會經(jīng)由很多IP分享器才連上公司的數(shù)據(jù)機(jī)，IP分享器之間會有線路，破壞每個IP分享器以及每條

12、線路都會有一定的成本，你最少要花多少成本才可以阻止你老闆打Heuristic Game呢？多個源點(diǎn)與匯點(diǎn)一般網(wǎng)路流的只會有一個源點(diǎn)及一個匯點(diǎn)，但如果有多個呢？解決方法很簡單，只要額外設(shè)置一個就好了，將源點(diǎn)看成從一個點(diǎn)發(fā)出，最後匯點(diǎn)則將流量全部匯集到一個點(diǎn)，需要注意容量設(shè)定成無限大。最小費(fèi)用最大流問題在一般的網(wǎng)路模型中，我們在每條弧上額外定義弧的單位成本Cost(u, v)，整個網(wǎng)路所花費(fèi)的成本為Cost(u, v)xFlow(u, v)，而最小費(fèi)用最大流問題則是要我們在最大流情況找出流量網(wǎng)路的最小成本。最小費(fèi)用最大流問題這與最短路徑問題相當(dāng)類似，只不過最短路徑只有一輛車，但最小費(fèi)用最大流卻是很

13、多輛車，這又讓我們聯(lián)想到當(dāng)我們在找增廣路徑使flow流過去的時候，不就像是開好多臺車(該次增廣的流量)穿過去嗎？所以我們的得到了一個演算法：每次找增廣路徑的時候，都用單源最短路徑演算法(SSSP)找到一條成本最低的最短路徑來增廣，直到找不到增廣路徑為止。因?yàn)槌杀究赡苁秦?fù)的，另外也有逆流的問題，所以搭配的SSSP必須要能夠處理負(fù)邊才行(像是Bellman-Ford, Johnsons等)，不過當(dāng)然，要一開始用APSP預(yù)處理也是可以的，但必須要注意的是，若圖上會出現(xiàn)負(fù)圈，就必須將圈消掉，簡言之就是沿圈增廣至殘餘網(wǎng)路不含負(fù)圈為止。例題最小花費(fèi)你是一個貨物經(jīng)銷商，你銷售著K種商品，現(xiàn)在有N份訂單與M個

14、倉庫，對於不同的商品從不同的倉庫到不同的送貨地點(diǎn)的運(yùn)輸單位成本是不一樣的，所以你希望在滿足條件下讓你的運(yùn)輸成本越小越好。建圖的技巧網(wǎng)路流最困難的部分就是如何將一般的問題轉(zhuǎn)化成網(wǎng)路流模型。首先是源點(diǎn)及匯點(diǎn)的構(gòu)造，必須要找到一個能讓問題得以開始的起始點(diǎn)以及一個能夠統(tǒng)整問題的解答的終點(diǎn)，若有多個，則額外設(shè)置一個。建圖的技巧第二步是點(diǎn)的構(gòu)造，必須要找到能代表點(diǎn)的事物，可能是一個狀態(tài)或者是一個個體之類的，若點(diǎn)上有限制流量，則使用點(diǎn)容量拆點(diǎn)法解決。接下來是弧的構(gòu)造，我們要找到點(diǎn)與點(diǎn)之間的關(guān)聯(lián)，並且設(shè)置一條條的弧，最困難的地方就在這裡，要如何連線以及設(shè)置容量，是網(wǎng)路流的最大重點(diǎn)。最後就讓flow流過去即可。

15、例題出題者的問題你要出一張考卷，涉及了N個領(lǐng)域的題目，每個領(lǐng)域需要出Pi題(i=1.N)，你有一個總共有M題的題庫，每一題都和Ri個領(lǐng)域相關(guān)(i=1.M, Ri=N)。所謂與某個領(lǐng)域相關(guān)，指的是該題可以被歸類於該領(lǐng)域，並非該題可以同時視為不同的領(lǐng)域，且考卷中不能有重覆的題目，問你對於每個類別，該出哪些題目？例題會議有一個城市, 每個人都恰屬於一個party, 但每個人可以參加不只一個club(0個亦可)?，F(xiàn)在這個城市要舉辦一個會議, 每個club都要推派一名該club的成員參加會議。但是, 在會議中任何一個party的總?cè)藬?shù)必需少於會議人數(shù)的一半。另外, 每個club推派的人不能重覆, 即一個

16、人只能代表一個club。請找出一份與會名單, 列出參加會議的人及他們各自代表的club，如果無解, 請輸出 Impossible。圖匹配圖匹配(Graph Matching)，通常簡稱匹配(Matching)，指的是在一個無向圖G=(V, E)中，令匹配M為邊集E的一個互不相交的子集亦即M中的任兩邊都沒有共用點(diǎn)，而從點(diǎn)的角度來看，我們?nèi)稳蓚€有連線的點(diǎn)配對進(jìn)M中，且每個點(diǎn)最多只能選進(jìn)一次。匹配的定義飽和點(diǎn)(Saturated Vertex)：若一個點(diǎn)被匹配過了，稱為飽和點(diǎn)，反之則不飽和點(diǎn)。極大匹配(Maximal Matching)：若一個匹配M使得G M已無法再找出任何邊加入M仍可維持匹配，

17、也就是說，若無法再抓兩個未飽和點(diǎn)的連線進(jìn)M，則稱M為一極大匹配(可能不只一個)。匹配的定義最大匹配(Maximum Matching)：若使得匹配M裡面含的邊數(shù)是圖G所有的匹配中最多的，也就是說，盡量挑出最多組兩兩不飽和點(diǎn)進(jìn)M，稱M為最大匹配(可能不只一個)。完美匹配(Perfect Matching)：若一個匹配M中包含了所有的頂點(diǎn)，也就是說，每個點(diǎn)都是飽和點(diǎn)，稱M為一個完美匹配(可能不只一個)。二分圖匹配二分圖(Bipartite Graph)有很多性質(zhì)，使得我們可以較容易做出他的匹配，而他的一些性質(zhì)也可以幫助我們解決一些看似不相關(guān)的問題。最大流的二分匹配由於一個點(diǎn)只能匹配一次的限制，且匹

18、配時會與另外一不飽和點(diǎn)有連線，所以我們很容易想到了網(wǎng)路流的容量限制。最大流的二分匹配因?yàn)閳D是二分圖，所以我們可以輕易將點(diǎn)分為A與B兩個不會與同點(diǎn)集相連的點(diǎn)集接著我們設(shè)置一個源點(diǎn)S連向點(diǎn)集A的每個點(diǎn)，容量為1，象徵只能匹配一次，同樣的，我們將點(diǎn)集B的所有點(diǎn)連到一個匯點(diǎn)T，容量為1，而AB之間的連線則設(shè)為由A到B的有向弧，容量也為1，如此一般，最後讓flow流過去，因?yàn)榱髁康南拗疲飨騾R點(diǎn)的流量就是匹配過的邊數(shù)量，所以最大流就是最大匹配了！最大流的二分匹配ABCDstabcd其餘同最大流運(yùn)算過程匈牙利演算法交錯軌(Alternating Path)：若一個路徑P上的點(diǎn)是匹配邊與未匹配邊交錯出現(xiàn)的，

19、稱其為交錯軌。增廣路(Augmenting Path)：若一個交錯軌P的起點(diǎn)與終點(diǎn)都是不飽和點(diǎn)，稱其為增廣路。匈牙利演算法透過兩種路徑，Claude Berge於1958年提出了一個Berge定理(Berges Lemma)：匹配M中不存在任何增廣路 若且唯若 目前的匹配M是最大匹配因?yàn)榧僭O(shè)存在一條增廣路P，我們就可以對這條增廣路增廣，方式為反轉(zhuǎn)增廣路P上的每一條邊，匹配數(shù)會增加1。匈牙利演算法也就是說，每一次找到一條增廣路並增廣後，匹配數(shù)會加1，而一個匈牙利數(shù)學(xué)家Edmonds提出了匈牙利演算法：不斷尋找增廣路，直到找不到增廣路的時候，目前的匹配就會是最大匹配了！依據(jù)這個演算法，我們可以使用

20、遞迴方式構(gòu)造出一個O(mn)的二分匹配匈牙利演算法！（那一般圖會變什麼樣子呢？）更有效率地找到增廣路既然知道了匈牙利演算法的核心，那就我們還一個問題了：要如何更有效率地尋找增廣路。假設(shè)從一個點(diǎn)u出發(fā)要找增廣路，因?yàn)樵鰪V路是一條交錯軌，所以會找到很多條交錯軌（但不一定能找到增廣路），而這棵由u為根並由交錯軌所構(gòu)成的搜尋樹我們稱為交錯樹(alternating path tree)。更有效率地找到增廣路我們可以從交錯樹上注意到一件事情，如果交錯樹出現(xiàn)了一條由根而下的增廣路，就會結(jié)束在一個不飽和點(diǎn)的葉子上也就是說，我們只要在交錯樹上找一個不飽和的葉子回溯到根就會是一條增廣路！所以我們透過逐漸成長交錯

21、樹（從根及葉子不斷接上交錯軌），直到找到增廣路(不飽和葉子)為止。更有效率地找到增廣路一直重複尋找，當(dāng)所有的葉子都無法再接上交錯軌（交錯樹無法成長）且無法找到增廣路(所有葉子都不是不飽和葉子)時，該根已經(jīng)無法找到任何增廣路了，我們稱此時的交錯樹為匈牙利樹。而匈牙利樹有一個顯而易見的性質(zhì)：目前匹配M中不存在任何經(jīng)過匈牙利樹的增廣路這使得我們再找到一個匈牙利樹之後，可以將整棵匈牙利樹拔掉而不影響匹配的進(jìn)行。這種利用交錯樹成長尋找增廣路的方法叫做匈牙利樹演算法(Hungarian Tree Algorithm)。二分圖最大匹配的應(yīng)用除了一般的匹配問題，二分圖因?yàn)槠湟恍┨貏e的性質(zhì)，使得在做出最大匹配的

22、問題時也一併解決了其他看似繁瑣的問題。二分圖的最小點(diǎn)覆蓋二分圖的最大獨(dú)立集點(diǎn)數(shù) DAG的最小路徑覆蓋數(shù) 二分圖最小點(diǎn)覆蓋=最大匹配數(shù)最小點(diǎn)覆蓋問題(Minimum Vertex Cover Problem)要求用最少的點(diǎn)覆蓋所有的邊（只要屬於一邊就算覆蓋了）也就是說，要讓每條邊至少跟一個點(diǎn)關(guān)連，Dnes Knig在1916年證明出在二分圖的情況下最小點(diǎn)覆蓋會等於最大匹配，所以這也被稱為Knig定理(Knigs theorem)。Knig定理證明透過匈牙利演算法，我們不斷找出在二分圖上的交錯軌，直到找到增廣路，由於Berge定理，所以當(dāng)我們找到最大匹配時，圖中已經(jīng)找不到任何這樣的增廣路了。雖然沒

23、有增廣路，但是還是會存在許多沒有終點(diǎn)的增廣路(單純的交錯軌)我們從二分圖的A集合沒有匹配過的點(diǎn)出發(fā)尋找交錯軌，並且在軌上的點(diǎn)標(biāo)記，最後A集合未標(biāo)記的點(diǎn)加上B集合標(biāo)記的點(diǎn)就是最小點(diǎn)覆蓋集合。Knig定理證明為什麼這樣會對呢？首先，因?yàn)檫@樣選起來的點(diǎn)都會是標(biāo)記過的，A集合未被匹配的點(diǎn)會被當(dāng)作起點(diǎn)標(biāo)記、B集合則為不存在增廣路而不可能被標(biāo)記。而同一個匹配邊只會有一個點(diǎn)被選中，因?yàn)閷ふ医诲e軌的關(guān)係，所以不可能發(fā)生在A集合的邊未被標(biāo)記，但B集合卻標(biāo)記了的情況，因此每一個匹配邊可以找到一個覆蓋點(diǎn)。Knig定理證明又因?yàn)樵贏集合未匹配的點(diǎn)一定會當(dāng)作起點(diǎn)開始尋找交錯軌，所以不可能有邊的A集合點(diǎn)沒有標(biāo)記，而B集合

24、點(diǎn)卻是有標(biāo)記的，所以未匹配邊依然可以全部覆蓋到。而光是要覆蓋最大匹配就需要花最大匹配數(shù)個點(diǎn)了，所以這當(dāng)然是最小的。例題山姆我是現(xiàn)在有一個n x m的矩陣裡有一些很奇怪的石頭，你可以放大絕讓某一行或某一列的石頭消失，但放大絕是要花費(fèi)SP的，所以你希望放越少次越好，並且提出施放方案。二分圖的最大獨(dú)立集二分圖的最大獨(dú)立集點(diǎn)數(shù) = 二分圖點(diǎn)數(shù) - 二分圖的最大匹配數(shù)最大獨(dú)立集問題(Maximum Independent Sets Problem)要求從圖G中選出m個點(diǎn)，使這些點(diǎn)中任兩個點(diǎn)沒有邊相連，且要求m最大。例題 因數(shù)與倍數(shù)給A,B兩組數(shù)，在這兩組數(shù)中各刪掉一些數(shù)，使得任一個B中的數(shù)皆不是任一個A

25、中的數(shù)的倍數(shù)問最少需要刪掉幾個數(shù)？DAG的最小路徑覆蓋數(shù)DAG的最小路徑覆蓋數(shù)= 拆等於點(diǎn)數(shù) -拆點(diǎn)成二分圖後的最大匹配數(shù)最小路徑覆蓋問題(Minimum Path Cover)要求在一個DAG中，用盡量少的簡單路徑覆蓋所有點(diǎn)。我們把每個點(diǎn)u拆成u與u，若在圖中有一條弧(u,v)，則在新圖中加上一條(u,v)，而經(jīng)由出入度以及奇偶性，我們可以證明：原圖中的最小路徑覆蓋數(shù)會等於點(diǎn)數(shù) - 拆點(diǎn)成二分圖後的最大匹配數(shù)最小路徑覆蓋證明如果在G中增加一條匹配邊u v，那麼在圖G的路徑覆蓋中就存在一條由u連接v的邊，也就是說u與v 在一條路徑上，於是路徑覆蓋數(shù)就可以減少1。如此繼續(xù)增加匹配邊，每增加一條，路徑覆蓋數(shù)就減少一條，直到匹配邊不能繼續(xù)增加時，路徑覆蓋數(shù)也不能再減少了，但是這只是說明了每條匹配邊對應(yīng)於路徑覆蓋中的一條路徑上的一條連接兩個點(diǎn)之間的有向邊。與前面類似，對於路徑覆蓋中的每條連接兩個頂點(diǎn)之間的每條有向邊u v，我們可以在匹配圖中對應(yīng)做一條連接u與v的邊，顯然這樣做出來圖的是一個匹配圖(如果得到的圖