修改二部圖，使其完美匹配

Question

給定一個具有相等大小的X和Y邊的二分圖，我們如何有效地找到我們必須添加的最小邊數，從而使圖具有完美的匹配？是否有比遍歷所有2 ^（| X |）子集並添加邊直到霍爾定理滿足的更好的解決方案？

感謝。

Answer 1

如果我正確地理解了這個問題，應該可以通過使用所謂的Hungarian method或模型化作爲網絡流問題來有效地生成初始圖的cardinality-maximal匹配。一旦找到基數最大匹配，任何分區中都必須有相同數量的不匹配節點，可以根據意願使用附加邊進行匹配。

換句話說，如果M是一個基數，最大匹配的基數在原始圖和|X|=|Y|成立，則在至少M-|X|邊緣具有爲了有包含在圖中的完美匹配要被添加​​。