Network Flow and Graph Matching

Presentation on theme: "Network Flow and Graph Matching"— Presentation transcript:

1 Network Flow and Graph Matching
網路流與圖匹配

2 網路流的歷史 網路流(Network Flow)是近年來在圖論中相當熱門的問題，在1955年 ，T.E. Harris在研究鐵路最大通量時，首先提出在一個給定的網路上尋求兩點間最大運輸量的問題。1956年，L.R. Ford和D.R. Fulkerson給出解決這類問題的演算法，從而建立了網路流理論。

3 網路流的定義 網路(Network)： 圖G = ( V, A )為一有向圖，稱為網路
源點與匯點(Source and Sink)： 令一點S為源點、一點T為匯點，其餘為中間點 容量(Capacity)： 每條弧上定義一個非負數C(u, v)為該弧的容量 流量(Flow)： 每條弧上定義一個非負數F(u, v)為流量，所有流量的集合則稱為網路的一個流。

4 網路流的定義 剩餘容量(Residual Capacity)： 每條弧上定義一個非負數 Cf(u, v) = C(u, v) – F(u, v) 為該弧的剩餘容量，而剩餘容量的集合則稱為剩餘網路(Residual Network) 網路的流量(Flow of Network)： 由源點發出，匯點匯集的總流量，若其為該網路能產生的最大流量，則稱其為最大流(Maximum Flow)。

5 網路流的限制 可行流(Positive Flow)： 若一流符合上述三點限制，則稱其為可行流。
容量限制(Capacity Constraints)： 所有的F(u, v) ≤ C(u, v) (流量不大於容量) 流量守恆(Flow Conservation)： 對非源點或匯點的點，流入的流量和等於流出的流量和 源點流出的總流量等於流進匯點的總流量 斜對稱(Skew Symmetry) ： 對於所有的F(u, v) + F(v, u) = 0， 由u到v淨流量加上由v到u的淨流量必須為零。 可行流(Positive Flow)： 若一流符合上述三點限制，則稱其為可行流。

6 網路流的弧 飽和弧： 若一條弧的流量恰好等於容量，則稱其為飽和弧。 不飽和弧： 若一條弧的流量小於容量，則稱其為不飽和弧。
零流弧： 若弧的流量為零，稱其零流弧，反之稱非零流弧。 前向弧與後向弧： 設W為一由源點到匯點的有向路徑，並定義由源點到匯點的方向為該路徑的方向，若路徑上的弧方向與路徑相同，稱其為前向弧，反之為後向弧。

7 增廣路徑 設f是一個可行流，W是源點到匯點的一條有向路徑，如果W滿足下列的兩個條件，稱之為關於可行流f的一條增廣路徑： 每條前向弧是非飽和弧
每條後向弧是非零流弧 也就是說，整條增廣路徑上的Cf(uk,uk+1)大於零，這就代表我們一定可以在這條增廣路徑上的每一條弧上加一流量d，使整個流仍然是可行流並使網路的總流量增加d。

8 割集 割集設流量網路G=(V,A)的頂點集V是兩不交的部分S, S’的聯集，使源點S，匯點在S’中。
若A’是A的最小的子集，使得G中去掉A’後成為兩個不相交的子圖，分別以S, S’為頂點集，則稱A’是關於(S,S’)的割集，而A’裡的總容量則稱為割的容量。 而若A’為G所能產生的割集中容量和最小的，則稱A’為最小割(Minimum Cut)

9 網路最大流問題 給定一個流量網路 G = ( V , A )，並指定一點為源點，一點為匯點，要求求出此網路的最大流量為何。 1 12 3
20 16 s 10 t 4 9 7 4 13 2 4 14

10 Ford-Fulkerson方法 利用殘餘網路的概念每次隨意找一條增廣路徑，修正殘餘網路（亦須對後向弧作更正），並增加路徑中最小的容量作為增加流量，直到找不到增廣路徑為止，而先前累積的流量則為最大流量，複雜度為O(Ef)，f為網路的最大流。

11 Ford-Fulkerson方法過程 流量增加4 目前流量為4 4 1 3 12 8 12 16 20 4 5 9 s 10 t 4 7 4
13 2 10 14 4 4 4 流量增加4 目前流量為4

12 Ford-Fulkerson方法過程 流量增加7 目前流量為13 4 1 3 8 12 5 13 20 4 11 5 7 s 10 3 11
t 4 7 7 4 13 2 10 3 4 4 11 4 流量增加7 目前流量為13

13 Ford-Fulkerson方法過程 流量增加8 目前流量為21 12 4 1 3 8 5 13 5 11 5 15 7 s 11 3 11
8 5 13 5 11 5 15 7 s 11 3 11 3 t 7 8 4 13 5 2 3 4 4 11 流量增加8 目前流量為21 13

14 Ford-Fulkerson方法過程 流量增加4 目前流量為25 12 1 3 5 1 5 11 9 5 s 15 19 11 3 t 7
5 1 5 11 9 5 s 15 19 11 3 t 7 12 8 4 5 1 2 3 4 4 11 流量增加4 目前流量為25 14

15 Ford-Fulkerson方法過程 已無法找到增廣路徑。 最大流為25。 12 1 3 5 1 11 9 s 19 11 3 t 7 12
5 1 11 9 s 19 11 3 t 7 12 1 2 3 4 4 11 15

16 實現Ford-Fulkerson方法-Edmonds-Karps算法
算法： 原理與Ford-Fulkerson相同，但是以廣度優先搜尋增廣路徑，效率較隨機找高。 可避免上述情況 s12t以及s21t交替出的話最差須找2,000,000,000次。 1 1,000,000,000 1,000,000,000 s t 1 1,000,000,000 2 1,000,000,000

17 例題 網際網路頻帶 給任兩點間的線路容量，線路是雙向的，且任兩點間可能有不只一條線路，求某兩點之間的最大流量。

18 例題 草地排水 農夫約翰知道每一條排水溝每分鐘可以流過的水量，和排水系統的準確佈局（起點為水潭而終點為小溪的一張網）。需要注意的是，有些時候從一處到另一處不只有一條排水溝。 根據這些信息，計算從水潭排水到小溪的最大流量。對於給出的每條排水溝，雨水只能沿著一個方向流動，注意可能會出現雨水環形流動的情形。

19 最大流最小割定理 在一個流量網路G中，以下三個條件為等價條件 ：
有一流f 為G的最大流 G的殘餘網路沒有增廣路徑 存在一割C，其容量為流量f 假設割集中連接分屬兩點集的u,v，我們可以確定Cf(u, v) = 0 (否則會產生一條增廣路徑使得v在所屬的集合中) 又因為Cf(u, v) = C(u, v) - F (u, v)， 得到C(u, v) = F (u, v)，又因為定理中1.3，所以推得C為最小割 。

20 最大流最小割定理證明 12 若在f的殘餘網路中存在增廣路徑，那麼f就肯定不是最大流，逆否命題成立。
23 假設f的殘餘網路中不存在增廣路徑，就代表說源點及匯點之間沒有路徑，先設立一個集合S代表源點所無法抵達的點，以及集合T代表除了S之外的所有點，設u為S中一點、v為T中一點，uv之間的流量必等於其割值，因此得證。

21 最大流最小割定理證明 31 因為f = F (S,T) = ΣF(u,v) ≦ ΣC(u,v) = C(S,T) 對於每個ST割集 f都不大於C(S,T)，所以當 f = C(S,T)時，f 為該網路的最大流。

22 最小割集的求法 由於最大流等於最小割，因此最小割的弧一定是飽和弧，在剩餘網路的容量則為0。
所以我們可以從源點開始沿著剩餘網路的前向弧搜索，直到找到每條路徑的第一條容量為0的弧，而那些弧就會是最小割集了！

23 例題汙染控制 光明牛奶公司不小心發送了一批壞牛奶。你知道這批牛奶要發給哪個零售商，但是要把這批牛奶送到他手中有許多種途徑。送貨網由一些倉庫和運輸卡車組成，每輛卡車都在各自固定的兩個倉庫之間單向運輸牛奶。停止每輛卡車都會有一定的經濟損失。你的任務是，在保證壞牛奶不送到零售商的前提下，制定出停止卡車運輸的方案，使損失最小。

24 點容量 一般網路流的限制只在邊上做限制，對點只要符合流量守恆就好了，但是如果給定一個點的流量限制呢？做法很簡單，既然只能在邊上做限制，那就把點當作邊吧，我們把一個點拆成兩個點連結的邊，並在上面做限制，如此一般就可以輕易做到在點上的容量了！ s s s’

25 例題電力輸送 DESA正在進行一項電力傳輸的計畫。由於 Dhaka 的人口數相當多，DESA 希望盡可能透過網路傳輸最大的電力給它。但是電力在傳輸時會因電阻而損失，所以他們想要使用變電裝置來達到不損失電力的目標。每個變電裝置有不同的容量。並且連接變電裝置之間的電線也是有一定的容量的。DESA 想要知道在沒有電力損失的情況下，最多可以傳輸的電力是多少。這就是你的任務。

26 例題很火的程式設計師 你老闆把你資遣了，所以你很火。你決定要展開報復，讓你老闆再也連不上網路打Heuristic Game。
你老闆會經由很多IP分享器才連上公司的數據機，IP分享器之間會有線路，破壞每個IP分享器以及每條線路都會有一定的成本，你最少要花多少成本才可以阻止你老闆打Heuristic Game呢？

27 多個源點與匯點 一般網路流的只會有一個源點及一個匯點，但如果有多個呢？
解決方法很簡單，只要額外設置一個就好了，將源點看成從一個點發出，最後匯點則將流量全部匯集到一個點，需要注意容量設定成無限大。

28 最小費用最大流問題 在一般的網路模型中，我們在每條弧上額外定義弧的單位成本Cost(u, v)，整個網路所花費的成本為ΣCost(u, v)xFlow(u, v)，而最小費用最大流問題則是要我們在最大流情況找出流量網路的最小成本。

29 最小費用最大流問題 這與最短路徑問題相當類似，只不過最短路徑只有一輛車，但最小費用最大流卻是很多輛車，這又讓我們聯想到當我們在找增廣路徑使flow流過去的時候，不就像是開好多台車(該次增廣的流量)穿過去嗎？所以我們的得到了一個演算法：每次找增廣路徑的時候，都用單源最短路徑演算法(SSSP)找到一條成本最低的最短路徑來增廣，直到找不到增廣路徑為止。

30 因為成本可能是負的，另外也有逆流的問題，所以搭配的SSSP必須要能夠處理負邊才行(像是Bellman-Ford, Johnson’s…等)，不過當然，要一開始用APSP預處理也是可以的，但必須要注意的是，若圖上會出現負圈，就必須將圈消掉，簡言之就是沿圈增廣至殘餘網路不含負圈為止。

31 例題最小花費 你是一個貨物經銷商，你銷售著K種商品，現在有N份訂單與M個倉庫，對於不同的商品從不同的倉庫到不同的送貨地點的運輸單位成本是不一樣的，所以你希望在滿足條件下讓你的運輸成本越小越好。

32 建圖的技巧 網路流最困難的部分就是如何將一般的問題轉化成網路流模型。
首先是源點及匯點的構造，必須要找到一個能讓問題得以開始的起始點以及一個能夠統整問題的解答的終點，若有多個，則額外設置一個。

33 建圖的技巧 第二步是點的構造，必須要找到能代表點的事物，可能是一個狀態或者是一個個體之類的，若點上有限制流量，則使用點容量拆點法解決。
接下來是弧的構造，我們要找到點與點之間的關聯，並且設置一條條的弧，最困難的地方就在這裡，要如何連線以及設置容量，是網路流的最大重點。 最後就讓flow流過去即可。

34 例題出題者的問題 你要出一張考卷，涉及了N個領域的題目，每個領域需要出Pi題(i=1...N)，你有一個總共有M題的題庫，每一題都和Ri個領域相關(i=1...M, Ri<=N)。所謂與某個領域相關，指的是該題可以被歸類於該領域，並非該題可以同時視為不同的領域，且考卷中不能有重覆的題目，問你對於每個類別，該出哪些題目？

35 例題會議 有一個城市, 每個人都恰屬於一個party, 但每個人可以參加不只一個club(0個亦可)。
現在這個城市要舉辦一個會議, 每個club都要推派一名該club的成員參加會議。 但是, 在會議中任何一個party的總人數必需少於會議人數的一半。 另外, 每個club推派的人不能重覆, 即一個人只能代表一個club。 請找出一份與會名單, 列出參加會議的人及他們各自代表的club，如果無解, 請輸出 Impossible。

36 圖匹配 圖匹配(Graph Matching)，通常簡稱匹配(Matching)，指的是在一個無向圖G=(V, E)中，令匹配M為邊集E的一個互不相交的子集 亦即M中的任兩邊都沒有共用點，而從點的角度來看，我們任取兩個有連線的點配對進M中，且每個點最多只能選進一次。

37 匹配的定義 飽和點(Saturated Vertex)：若一個點被匹配過了，稱為飽和點，反之則不飽和點。
極大匹配(Maximal Matching)：若一個匹配M使得G – M已無法再找出任何邊加入M仍可維持匹配，也就是說，若無法再抓兩個未飽和點的連線進M，則稱M為一極大匹配(可能不只一個)。

38 匹配的定義 最大匹配(Maximum Matching)：若使得匹配M裡面含的邊數是圖G所有的匹配中最多的，也就是說，盡量挑出最多組兩兩不飽和點進M，稱M為最大匹配(可能不只一個)。 完美匹配(Perfect Matching)：若一個匹配M中包含了所有的頂點，也就是說，每個點都是飽和點， 稱M為一個完美匹配 (可能不只一個)。

39 二分圖匹配 二分圖(Bipartite Graph)有很多性質，使得我們可以較容易做出他的匹配，而他的一些性質也可以幫助我們解決一些看似不相關的問題。

40 最大流的二分匹配 由於一個點只能匹配一次的限制，且匹配時會與另外一不飽和點有連線，所以我們很容易想到了網路流的容量限制。

41 最大流的二分匹配 因為圖是二分圖，所以我們可以輕易將點分為A與B兩個不會與同點集相連的點集
接著我們設置一個源點S連向點集A的每個點，容量為1，象徵只能匹配一次，同樣的，我們將點集B的所有點連到一個匯點T，容量為1，而AB之間的連線則設為由A到B的有向弧，容量也為1，如此一般，最後讓flow流過去，因為流量的限制，流向匯點的流量就是匹配過的邊數量，所以最大流就是最大匹配了！

42 最大流的二分匹配 A a B b 其餘同最大流運算過程 s t C c D d 42

43 匈牙利演算法 交錯軌(Alternating Path)：若一個路徑P上的點是匹配邊與未匹配邊交錯出現的，稱其為交錯軌。
增廣路(Augmenting Path)：若一個交錯軌P的起點與終點都是不飽和點，稱其為增廣路。

44 匈牙利演算法 透過兩種路徑，Claude Berge於1958年提出了一個Berge定理(Berge’s Lemma)：
因為假設存在一條增廣路P，我們就可以對這條增廣路增廣，方式為反轉增廣路P上的每一條邊，匹配數會增加1。

45 匈牙利演算法 也就是說，每一次找到一條增廣路並增廣後，匹配數會加1，而一個匈牙利數學家Edmonds提出了匈牙利演算法：不斷尋找增廣路，直到找不到增廣路的時候，目前的匹配就會是最大匹配了！ 依據這個演算法，我們可以使用遞迴方式構造出一個O(mn)的二分匹配匈牙利演算法！（那一般圖會變什麼樣子呢？）

46 更有效率地找到增廣路 既然知道了匈牙利演算法的核心，那就我們還一個問題了： 要如何更有效率地尋找增廣路。
假設從一個點u出發要找增廣路，因為增廣路是一條交錯軌，所以會找到很多條交錯軌（但不一定能找到增廣路），而這棵由u為根並由交錯軌所構成的搜尋樹我們稱為交錯樹(alternating path tree)。

47 更有效率地找到增廣路 我們可以從交錯樹上注意到一件事情，如果交錯樹出現了一條由根而下的增廣路，就會結束在一個不飽和點的葉子上
也就是說，我們只要在交錯樹上找一個不飽和的葉子回溯到根就會是一條增廣路！ 所以我們透過逐漸成長交錯樹（從根及葉子不斷接上交錯軌），直到找到增廣路(不飽和葉子)為止。

48 目前匹配M中不存在任何經過匈牙利樹的增廣路
更有效率地找到增廣路 一直重複尋找，當所有的葉子都無法再接上交錯軌（交錯樹無法成長）且無法找到增廣路(所有葉子都不是不飽和葉子)時，該根已經無法找到任何增廣路了，我們稱此時的交錯樹為匈牙利樹。而匈牙利樹有一個顯而易見的性質： 目前匹配M中不存在任何經過匈牙利樹的增廣路 這使得我們再找到一個匈牙利樹之後，可以將整棵匈牙利樹拔掉而不影響匹配的進行。 這種利用交錯樹成長尋找增廣路的方法叫做匈牙利樹演算法(Hungarian Tree Algorithm)。

49 二分圖最大匹配的應用 除了一般的匹配問題，二分圖因為其一些特別的性質，使得在做出最大匹配的問題時也一併解決了其他看似繁瑣的問題。
二分圖的最小點覆蓋 二分圖的最大獨立集點數 DAG的最小路徑覆蓋數

50 二分圖最小點覆蓋=最大匹配數 最小點覆蓋問題(Minimum Vertex Cover Problem)要求用最少的點覆蓋所有的邊（只要屬於一邊就算覆蓋了） 也就是說，要讓每條邊至少跟一個點關連， Dénes Kőnig在1916年證明出在二分圖的情況下最小點覆蓋會等於最大匹配，所以這 也被稱為Kőnig定理(Kőnig’s theorem)。

51 Kőnig定理證明 透過匈牙利演算法，我們不斷找出在二分圖上的交錯軌，直到找到增廣路，由於Berge定理，所以當我們找到最大匹配時，圖中已經找不到任何這樣的增廣路了。 雖然沒有增廣路，但是還是會存在許多沒有終點的增廣路(單純的交錯軌) 我們從二分圖的A集合沒有匹配過的點出發尋找交錯軌，並且在軌上的點標記，最後A集合未標記的點加上B集合標記的點就是最小點覆蓋集合。

52 Kőnig定理證明 為什麼這樣會對呢？ 首先，因為這樣選起來的點都會是標記過的，A集合未被匹配的點會被當作起點標記、B集合則為不存在增廣路而不可能被標記。 而同一個匹配邊只會有一個點被選中，因為尋找交錯軌的關係，所以不可能發生在A集合的邊未被標記，但B集合卻標記了的情況，因此每一個匹配邊可以找到一個覆蓋點。

53 Kőnig定理證明 又因為在A集合未匹配的點一定會當作起點開始尋找交錯軌，所以不可能有邊的A集合點沒有標記，而B集合點卻是有標記的，所以未匹配邊依然可以全部覆蓋到。 而光是要覆蓋最大匹配就需要花最大匹配數個點了，所以這當然是最小的。

54 例題山姆我是 現在有一個n x m的矩陣裡有一些很奇怪的石頭，你可以放大絕讓某一行或某一列的石頭消失，但放大絕是要花費SP的，所以你希望放越少次越好，並且提出施放方案。

55 二分圖的最大獨立集 二分圖的最大獨立集點數 = 二分圖點數 - 二分圖的最大匹配數
二分圖的最大獨立集點數 = 二分圖點數 - 二分圖的最大匹配數 最大獨立集問題(Maximum Independent Sets Problem)要求從圖G中選出m個點，使這些點中任兩個點沒有邊相連，且要求m最大。

56 例題 因數與倍數 給A,B兩組數，在這兩組數中各刪掉一些數，使得任一個B中的數皆不是任一個A中的數的倍數 問最少需要刪掉幾個數？

57 DAG的最小路徑覆蓋數 DAG的最小路徑覆蓋數= 拆等於點數 -拆點成二分圖後的最大匹配數
最小路徑覆蓋問題(Minimum Path Cover)要求在一個DAG中，用盡量少的簡單路徑覆蓋所有點。 我們把每個點u拆成u與u’，若在圖中有一條弧(u,v)，則在新圖中加上一條(u,v’)，而經由出入度以及奇偶性，我們可以證明：原圖中的最小路徑覆蓋數會等於點數 - 拆點成二分圖後的最大匹配數

58 最小路徑覆蓋證明 如果在G’中增加一條匹配邊u  v‘，那麼在圖G的路徑覆蓋中就存在一條由u連接v’的邊，也就是說u與v 在一條路徑上，於是路徑覆蓋數就可以減少1。 如此繼續增加匹配邊，每增加一條，路徑覆蓋數就減少一條，直到匹配邊不能繼續增加時，路徑覆蓋數也不能再減少了，但是這只是說明了每條匹配邊對應於路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊。

59 與前面類似，對於路徑覆蓋中的每條連接兩個頂點之間的每條有向邊u  v，我們可以在匹配圖中對應做一條連接u與v‘的邊，顯然這樣做出來圖的是一個匹配圖(如果得到的圖不是一個匹配圖，那麼這個圖中必定存在這樣兩條邊 u  v’  及 u  k‘，那麼在路徑覆蓋圖中就存在了兩條邊u-v, u-k，那從u出發的路徑就不止一條了，這與路徑覆蓋圖是矛盾的。

60 例題 機器人 在一個地圖中有很多障礙物，你要派出機器人去清除他們，但是你的機器人只能往右以及往下走，問最少要派多少台機器人才能把所有障礙物清除。

61 一般圖匹配 學會了如何找出二分圖的最大匹配，那一般圖呢？
是否有辦法利用之前利用遞迴找增廣路的匈牙利演算法或是利用交錯樹與匈牙利樹找增廣路的匈牙利樹演算法找到呢？

62 一般圖匹配 首先有一個明顯的性質：圖G為二分圖若且為若圖G不含奇圈(含有奇數個點的cycle)
我們發現在圖中有奇圈的形況下，若使用匈牙利演算法，複雜度會成長為O(n*n!)（因為交錯軌往不同的方向擴展可能會有不同的結果），極為恐怖。

63 一般圖匹配 若使用匈牙利樹演算法，在成長交錯樹的時候，可能會造成一些增廣路雖然存在，但在找到之前卻產生了匈牙利樹，以至於該增廣路永遠無法被找到。 所以，我們必須要想辦法處理奇圈的情況，才有辦法處理一般圖的最大匹配。

64 奇圈與花 為了處理奇圈的情形，我們針對會發生的奇圈定義一個新名詞：花(Blossom) 花為一個長度為2k+1且含有k條匹配邊的奇圈

65 M’是G’的最大匹配 若且為若 M是G的最大匹配
奇圈與花 經由證明，我們可以得到一個消圈定理(Cycle Shrinking Lemma)： 令M為G的一個匹配，B為一朵花，如果一朵花B的點與剩於匹配M - B的點不相交，則把B縮成一個點，而縮點之後的新圖稱為G’，原本的匹配M則變成M’，我們可以證明： M’是G’的最大匹配 若且為若 M是G的最大匹配

66 奇圈與花 所以，經由消圈定理，我們可以得到一個新的縮花演算法： 先縮花，再成長交錯樹。
不過在成長完之後，要注意別忘記把花展開，因為裡面還有k條匹配邊。

67 例題工作排程 有一定數量的夜班警衛保衛當地的倉庫以防止搶劫。這些警衛需要成對地進行安排，使每一對安排在不同的夜晚。倉庫主管要求你寫一程序，確定能夠安排警衛的最大值。注意：每一個警衛人員只能安排一次，警衛人員不能單獨工作。

68 END