斷開圖中的最大二分配匹配

Question

當圖有幾個組件時，如何找到最大二分配匹配？每個組件都可以通過兩種方式着色。你如何確定兩組X和Y以運行最大匹配程序？

Answer 1

我不知道斷開連接的圖，但如果你有一個完整的圖像，我可能會對你有興趣：http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html。它使用改進的Floyd-Warshall算法來查找最大匹配。我不知道這個和匈牙利算法的區別。

Answer 2

如果您的圖有幾個不同的連接組件，只需在每個組件中找到最大匹配並返回它們的聯合即可找到圖中的最大匹配。

至於如何確定集合X和Y，有很多算法用於檢測特定圖形是否是雙邊的，如果是，則爲節點分配標籤以恢復這兩個組。您可以很容易地使用修改後的DFS或BFS來做到這一點。因此，針對您的問題的算法可能是

1. 在整個圖上運行DFS以將其分解爲連接的組件。
2. 對於每個這些部分組成：
   1. 上的那些組件運行DFS來恢復哪些節點是在基團X和Y
   2. 使用的最大二分匹配算法來查找在該組件的最大匹配。
3. 將所有結果組合在一起得到整體答案。

希望這會有所幫助！

Answer 3

不要從邊緣的角度來看匹配，看看是作爲一組邊緣。這個觀點使得更清楚的是，不管你如何加入子結果，後面的結果仍然可以。

1. 獨立的圖形插入連接部件

2. 查找每個圖組件的最大匹配，使用選擇的算法。

3. 找到的匹配的聯合是整個圖的最大匹配。