主要定理二分圖的最大匹配算法二分圖的帶權(quán)重的最大匹配.ppt

1、2020/8/10,第6章 圖與網(wǎng)絡分析,6.7 最大匹配問題,2020/8/10,山東大學 軟件學院,2,最大對集（匹配）問題,二分圖的對集，基本概念，主要定理 二分圖的最大匹配算法 二分圖的帶權(quán)重的最大匹配分派問題及算法,2020/8/10,山東大學 軟件學院,3,基本概念,2020/8/10,山東大學 軟件學院,4,使用最大流算法求二分圖上的最大匹配,給定二分圖G = (V, U, E)，構(gòu)造流網(wǎng)絡。 增加一個源點 s，從 s 到 V 中每個頂點引一條有向邊。 增加一個目標頂點 t，從 U 中每個頂點向 t 引一條有向邊。 E中的邊均從 V 指向 U。 記得到的流網(wǎng)絡為G = (V, E

2、)。G中的每條邊均為單位容量。 計算G上從 s 到 t 的最大流。 E 中的飽和邊即構(gòu)成 G 上的一個最大匹配。,2020/8/10,山東大學 軟件學院,5,例子,2020/8/10,山東大學 軟件學院,6,定理,定理：記G上的最大流為f*，流值為|f*|。G上的最大匹配為M*。則|f*| = |M*|。 證明：首先證|f*| |M*|。 給定最大匹配M*，令G上M*中的邊的流值為1，s到M*匹配的V一側(cè)點的各條邊上流值為1，M*匹配的U一側(cè)點到t的各條邊上流值為1，則構(gòu)造了一個流值為|M*|的流f。 因此，顯然有|f*| |M*|。 再證|f*| |M*|。 設(shè)f*為G上的最大流。 由整流定

3、理，G上每條邊上的流值為整數(shù)。由于每條邊的容量均為1，因此G上每條邊的流值不是0就是1。,2020/8/10,山東大學 軟件學院,7,證明,再由流守恒約束，V中每個頂點最多有一條出去的邊流值為1。同理，U中每個頂點最多有一條進來的邊流值為1。 記M = e E | e上的流值 0，因此M中的任何兩條邊均不共享頂點，即，M是一個匹配，且|f*| = |M|。 因此，顯然有|f*| |M|。,2020/8/10,山東大學 軟件學院,8,基本概念,2020/8/10,山東大學 軟件學院,9,頂點覆蓋,2020/8/10,山東大學 軟件學院,10,定理6.8.1,2020/8/10,山東大學 軟件學院

4、,11,證明,2020/8/10,山東大學 軟件學院,12,通過增廣路求二分圖上的最大匹配,2020/8/10,山東大學 軟件學院,13,二分圖上最大匹配的標號算法,2020/8/10,山東大學 軟件學院,14,二分圖上最大匹配的標號算法,2020/8/10,山東大學 軟件學院,15,二分圖上最大匹配的標號算法,2020/8/10,山東大學 軟件學院,16,例子,2020/8/10,山東大學 軟件學院,17,例子,找到一條增廣路(1, 7)。更新M。,1,2020/8/10,山東大學 軟件學院,18,例子,找到一條增廣路(2, 8)。更新M。,2,2,2020/8/10,山東大學 軟件學院,1

5、9,例子,找到一條增廣路(3, 10)。更新M。,3,3,3,3,2020/8/10,山東大學 軟件學院,20,例子,找到一條增廣路(4, 10, 3, 9)。更新M。,4,10,3,3,2020/8/10,山東大學 軟件學院,21,例子,找不到增廣路，結(jié)束。,5,5,5,10,8,7,2020/8/10,山東大學 軟件學院,22,例子,紅邊為最大匹配，藍色頂點為頂點覆蓋。,5,5,5,10,8,7,2020/8/10,山東大學 軟件學院,23,時間復雜度分析,2020/8/10,山東大學 軟件學院,24,解釋,從S中未匹配的頂點開始，標號找M-增廣路的過程，實際上是一個從S中未匹配的頂點開始

6、進行廣度優(yōu)先搜索的過程。 該過程與標準的廣度優(yōu)先搜索不完全相同。 設(shè)搜索樹的根位于第1層。區(qū)別僅在于，在搜索過程中，奇數(shù)層頂點（在S一側(cè)）按廣度優(yōu)先展開；偶數(shù)層頂點（在T一側(cè)）按M中的（唯一一條）邊順延（而不是按廣度優(yōu)先展開）。,2020/8/10,山東大學 軟件學院,25,解釋,2020/8/10,山東大學 軟件學院,26,標號，找增廣路,v2,v2,u2,u6,v3,v5,v5,u3,u4,u5,v1,2020/8/10,山東大學 軟件學院,27,找增廣路過程中形成的搜索樹,虛線表示v5, u3相鄰， 但在對v5進行檢查的過程中， u3已經(jīng)標號，因此從v5不能 對u3標號。,2020/8/

7、10,山東大學 軟件學院,28,增廣，得到一個更大的匹配,2020/8/10,山東大學 軟件學院,29,廣度優(yōu)先搜索的觀點,構(gòu)造的輔助圖,從輔助圖上入度為0 的點v2開始的廣度 優(yōu)先搜索,2020/8/10,山東大學 軟件學院,30,輔助圖的構(gòu)造,頂點集 = V。 從v1到v2有一條有向邊，當且僅當 v2是從v1開始的增廣路上下一個V中的頂點。,2020/8/10,山東大學 軟件學院,31,Hall定理,2020/8/10,山東大學 軟件學院,32,證明,2020/8/10,山東大學 軟件學院,33,證明,2020/8/10,山東大學 軟件學院,34,證明,2020/8/10,山東大學 軟件學

8、院,35,Knig定理,2020/8/10,山東大學 軟件學院,36,Knig定理,2020/8/10,山東大學 軟件學院,37,Knig定理,2020/8/10,山東大學 軟件學院,38,指派問題：二分圖上帶權(quán)重的最大匹配,實例：二分圖G = (S, T, E)，邊上定義有非負權(quán)重we。 詢問：圖G上的一個匹配M，使得總權(quán)重e M we最大。,2020/8/10,山東大學 軟件學院,39,將指派問題歸約到最小費用流問題,1. 先進行預處理。 通過增加權(quán)重為0的邊，可以假定G是完全二分圖。這是因為權(quán)重為0的邊對最大權(quán)重匹配不產(chǎn)生影響。 若S一側(cè)和T一側(cè)的頂點數(shù)目不一樣多，比如|S| = m |

9、T| = n，則向S一側(cè)增加n m個頂點，以及這些頂點到T一側(cè)所有頂點權(quán)重為0的邊。這樣，可以假定S和T的頂點數(shù)目一樣多。 經(jīng)過上面兩個步驟，G是一個S和T的頂點數(shù)目相等的完全二分圖。,2020/8/10,山東大學 軟件學院,40,將指派問題歸約到最小費用流問題,2. 再將最大權(quán)重匹配問題變換到最小權(quán)重完美匹配問題。 由于G是S和T大小相等的完全二分圖，因此可以假定G上的最大權(quán)重匹配是一個完美匹配。 定義W = maxwij | 1 i, j n。對G上的每條邊(i, j)，定義wij = W wij。 于是在(G, w)上計算最大權(quán)重完美匹配M等價于在(G, w)上計算最小權(quán)重完美匹配M，因

10、為w(M) = nW w(M)。,2020/8/10,山東大學 軟件學院,41,將指派問題歸約到最小費用流問題,3. 最后將最小權(quán)重完美匹配問題變換到最小費用流問題。 新增加的邊費用都為0。所有邊的容量都為1。 由最小費用流的整流定理和流守恒約束，S T中流值大于0的邊構(gòu)成一個最小權(quán)重完美匹配。,wij, 1,S,T,s,t,0, 1,0, 1,2020/8/10,山東大學 軟件學院,42,求解指派問題的匈牙利算法,The Hungarian method is a combinatorial optimization algorithm which solves the assignment

11、 problem in polynomial time and which anticipated later primal-dual methods. It was developed and published by Harold Kuhn in 1955, who gave the name Hungarian method because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dnes Knig and Jen Egervry.,2020/8/10,山東

12、大學 軟件學院,43,求解指派問題的匈牙利算法,James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as KuhnMunkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was O(n4), however Edmonds and Karp

13、, and independently Tomizawa noticed that it can be modified to achieve an O(n3) running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had bee

14、n published posthumously in 1890 in Latin.,2020/8/10,山東大學 軟件學院,44,指派問題的LP及其對偶,2020/8/10,山東大學 軟件學院,45,基本思想（原始-對偶算法）,算法從可行對集M = 和可行對偶解ui = maxjwij, vj = 0開始。這時(6.8.5)和(6.8.7)全都滿足，(6.8.6)都不滿足。 算法總是在僅由滿足 ui + vj = wij的邊(i, j)構(gòu)成的子網(wǎng)絡上，找S中從ui 0的頂點i出發(fā)的增廣路。 若這樣的增廣路能夠找到，則用它更新當前的M后，(6.8.5)和(6.8.7)仍然是滿足的，而(6.8.

15、6)比以前多一些被滿足。 若這樣的增廣路找不到，則算法調(diào)整ui和vj的值。 當沒有匹配的點的ui調(diào)整到0時，(6.8.6)全部滿足，算法求到最優(yōu)解。,2020/8/10,山東大學 軟件學院,46,匈牙利算法,Harold Kuhn, 1955 1 M ；i S, ui maxwij；j T, vj 0, j +。 2 給S中未匹配的頂點標“”。 3 while S中有未檢查的標號點 或 (*) T中有j = 0的未檢查的標號點 (*) do 4 找一個符合(*)或(*)的頂點k。 5 if k S then 6 對于每條邊(k, j) M，若uk + vj wij j， 則對j標號“i”，并令

16、j uk + vj wij。,2020/8/10,山東大學 軟件學院,47,匈牙利算法,7 else /* k T，j = 0 */ 8 if k V(M) then 9 設(shè)(i, k) M。對i標號“k”。 10 else /* k V(M) */ 11 從頂點k反向追蹤到標號為“”的點， 得到一條增廣路P。用P更新M。 12 j T， j +。 抹去所有點上的標號，回到第2步。 13 endif 14 endif 15 endwhile,2020/8/10,山東大學 軟件學院,48,匈牙利算法,16 1 minui | i S，2 minj | j 0, j S， min1, 2。 17

17、對S中的每個有標號的頂點，ui ui ；對T中每個 j = 0的頂點， vj vj + ；對T中每個有標號且j 0的頂點， j j 。 18 若 1，則回到第3步。 19 /* 否則，找到了最大權(quán)重匹配 */return M。,2020/8/10,山東大學 軟件學院,49,例子,ui,vj,標號,標號,j,_,_,_,_,4,4,4,4,0,0,0,0,+,+,+,+,第1階段，初始化。,2020/8/10,山東大學 軟件學院,50,例子,ui,vj,標號,標號,j,1,1,_,_,4,4,4,4,0,0,0,0,3,2,+,+,第1階段，處理頂點1。,2020/8/10,山東大學 軟件學院,

18、51,例子,ui,vj,標號,標號,j,2,1,2,_,4,4,4,4,0,0,0,0,1,2,2,+,第1階段，處理頂點2。,2020/8/10,山東大學 軟件學院,52,例子,ui,vj,標號,標號,j,2,3,2,3,4,4,4,4,0,0,0,0,1,1,2,2,第1階段，處理頂點3。,2020/8/10,山東大學 軟件學院,53,例子,ui,vj,標號,標號,j,2,4,2,4,4,4,4,4,0,0,0,0,1,0,2,1,第1階段，處理頂點4。,2020/8/10,山東大學 軟件學院,54,例子,ui,vj,標號,標號,j,2,4,2,4,4,4,4,4,0,0,0,0,1,0,

19、2,1,第1階段，處理頂點6，找到一條增廣路(4, 6)。,2020/8/10,山東大學 軟件學院,55,例子,ui,vj,標號,標號,j,_,_,_,_,_,4,4,4,4,0,0,0,0,+,+,+,+,第2階段，初始化。,2020/8/10,山東大學 軟件學院,56,例子,ui,vj,標號,標號,j,_,1,1,_,_,4,4,4,4,0,0,0,0,3,2,+,+,第2階段，處理頂點1。,2020/8/10,山東大學 軟件學院,57,例子,ui,vj,標號,標號,j,_,2,1,2,_,4,4,4,4,0,0,0,0,1,2,2,+,第2階段，處理頂點2。,2020/8/10,山東大學

20、 軟件學院,58,例子,ui,vj,標號,標號,j,_,2,3,2,3,4,4,4,4,0,0,0,0,1,1,2,2,第2階段，處理頂點3。,2020/8/10,山東大學 軟件學院,59,例子,ui,vj,標號,標號,j,_,2,3,2,3,4,4,4,4,0,0,0,0,1,1,2,2,第2階段，所有點都檢查完畢，計算。,1 = 4,2 = 1, = 1,2020/8/10,山東大學 軟件學院,60,例子,ui,vj,標號,標號,j,_,2,3,2,3,3,3,3,4,0,0,0,0,0,0,1,1,第2階段，所有點都檢查完畢，調(diào)整ui、vj、j。,1 = 4,2 = 1, = 1,202

21、0/8/10,山東大學 軟件學院,61,例子,ui,vj,標號,標號,j,_,2,3,2,3,3,3,3,4,0,0,0,0,0,0,1,1,第3階段，處理頂點5，找到增廣路(2, 5)。,2020/8/10,山東大學 軟件學院,62,例子,ui,vj,標號,標號,j,_,_,_,_,_,_,3,3,3,4,0,0,0,0,+,+,+,+,第4階段，初始化。,2020/8/10,山東大學 軟件學院,63,例子,ui,vj,標號,標號,j,_,_,1,1,_,_,3,3,3,4,0,0,0,0,2,1,+,+,第4階段，處理頂點1。,2020/8/10,山東大學 軟件學院,64,例子,ui,vj

22、,標號,標號,j,_,_,1,3,_,3,3,3,3,4,0,0,0,0,2,0,+,1,第4階段，處理頂點3。,2020/8/10,山東大學 軟件學院,65,例子,ui,vj,標號,標號,j,_,6,1,3,_,3,3,3,3,4,0,0,0,0,2,0,+,1,第4階段，處理頂點6。,2020/8/10,山東大學 軟件學院,66,例子,ui,vj,標號,標號,j,_,6,1,3,4,3,3,3,3,4,0,0,0,0,2,0,2,1,第4階段，處理頂點4。,2020/8/10,山東大學 軟件學院,67,例子,ui,vj,標號,標號,j,_,6,1,3,4,3,3,3,3,4,0,0,0,0

23、,2,0,2,1,第4階段，處理完所有標號的頂點。計算。,1 = 3,2 = 1, = 1,2020/8/10,山東大學 軟件學院,68,例子,ui,vj,標號,標號,j,_,6,1,3,4,3,2,3,2,3,0,1,0,0,1,0,1,0,第4階段，調(diào)整ui、vj、j。,1 = 3,2 = 1, = 1,2020/8/10,山東大學 軟件學院,69,例子,ui,vj,標號,標號,j,_,6,1,3,4,3,2,3,2,3,0,1,0,0,1,0,1,0,第5階段，處理頂點8，找到增廣路(3, 8)。,2020/8/10,山東大學 軟件學院,70,例子,ui,vj,標號,標號,j,_,_,_

24、,_,_,_,_,2,3,2,3,0,1,0,0,+,+,+,+,第6階段，初始化。,2020/8/10,山東大學 軟件學院,71,例子,ui,vj,標號,標號,j,_,_,_,1,1,_,_,2,3,2,3,0,1,0,0,1,1,+,+,第6階段，處理頂點1。,2020/8/10,山東大學 軟件學院,72,例子,ui,vj,標號,標號,j,_,_,_,1,1,_,_,2,3,2,3,0,1,0,0,1,1,+,+,第6階段，處理完所有頂點，計算。,1 = 2,2 = 1, = 1,2020/8/10,山東大學 軟件學院,73,例子,ui,vj,標號,標號,j,_,_,_,1,1,_,_,1,3,2,3,0,1,0,0,0,0,+,+,第6階段，調(diào)整ui、vj、j。,1 = 2,2 = 1, = 1,2020/8/10,山東大學 軟件學院,74,例子,ui,vj,標號,標號,j,5,_,_,1,1,_,_,1,3,2,3,0,1,0,0,0,0,+,+,第7階段，處理頂點