二分圖匹配算法總結
二分圖最大匹配的匈牙利算法
二分圖是這樣一個圖，它的頂點可以分類兩個集合X和Y，所有的邊關聯在兩個頂點中，恰好一個屬於集合Ｘ，另一個屬於集合Ｙ。
最大匹配：圖中包含邊數最多的匹配稱為圖的最大匹配。
完美匹配：如果所有點都在匹配邊上，稱這個最大匹配是完美匹配。
最小覆蓋： 最小覆蓋要求用最少的點（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點關聯。可以證明：最少的點（即覆蓋數）＝最大匹配數
最小路徑覆蓋：
用盡量少的不相交簡單路徑覆蓋有向無環圖Ｇ的所有結點。解決此類問題可以建立一個二分圖模型。把所有頂點i拆成兩個：Ｘ結點集中的i和Y結點集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設二分圖最大匹配為m,則結果就是n-m。
最大獨立集問題：
在Ｎ個點的圖G中選出m個點，使這m個點兩兩之間沒有邊．求m最大值．
如果圖Ｇ滿足二分圖條件，則可以用二分圖匹配來做．最大獨立集點數 = 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)操作直到找不出增廣路徑為止
