二分圖匹配算法總結
二分圖最大匹配的匈牙利算法
二分圖是這樣一個圖,它的頂點可以分類兩個集合X和Y,所有的邊關聯在兩個頂點中,恰好一個屬於集合X,另一個屬於集合Y。
最大匹配:圖中包含邊數最多的匹配稱為圖的最大匹配。
完美匹配:如果所有點都在匹配邊上,稱這個最大匹配是完美匹配。
最小覆蓋: 最小覆蓋要求用最少的點(X集合或Y集合的都行)讓每條邊都至少和其中一個點關聯。可以證明:最少的點(即覆蓋數)=最大匹配數
最小路徑覆蓋:
用盡量少的不相交簡單路徑覆蓋有向無環圖G的所有結點。解決此類問題可以建立一個二分圖模型。把所有頂點i拆成兩個:X結點集中的i和Y結點集中的i',如果有邊i->j,則在二分圖中引入邊i->j',設二分圖最大匹配為m,則結果就是n-m。
最大獨立集問題:
在N個點的圖G中選出m個點,使這m個點兩兩之間沒有邊.求m最大值.
如果圖G滿足二分圖條件,則可以用二分圖匹配來做.最大獨立集點數 = N - 最大匹配數
一、匈牙利算法
設G=(V,{R})是一個無向圖。如頂點集V可分割為兩個互不相交的子集,並且圖中每條邊依附的兩個頂點都分屬兩個不同的子集。則稱圖G為二分圖。
v 給定一個二分圖G,在G的一個子圖M中,M的邊集{E}中的任意兩條邊都不依附於同一個頂點,則稱M是一個匹配。
v 選擇這樣的邊數最大的子集稱為圖的最大匹配問題(maximal matching problem)
v 如果一個匹配中,圖中的每個頂點都和圖中某條邊相關聯,則稱此匹配為完全匹配,也稱作完備匹配。
最大匹配在實際中有廣泛的用處,求最大匹配的一種顯而易見的算法是:先找出全部匹配,然後保留匹配數最多的。但是這個算法的復雜度為邊數的指數級函數。因此,需要尋求一種更加高效的算法。
匈牙利算法是求解最大匹配的有效算法,該算法用到了增廣路的定義(也稱增廣軌或交錯軌):若P是圖G中一條連通兩個未匹配頂點的路徑,並且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現,則稱P為相對於M的一條增廣路徑。
由增廣路徑的定義可以推出下述三個結論:
v 1. P的路徑長度必定為奇數,第一條邊和最後一條邊都不屬於M。
v 2. P經過取反操作(即非M中的邊變為M中的邊,原來M中的邊去掉)可以得到一個更大的匹配M’。
v 3. M為G的最大匹配當且僅當不存在相對於M的增廣路徑。
從而可以得到求解最大匹配的匈牙利算法:
v (1)置M為空
v (2)找出一條增廣路徑P,通過取反操作獲得更大的匹配M’代替M
v (3)重復(2)操作直到找不出增廣路徑為止