如何將二部匹配轉換爲獨立集

Question

我讀過「算法設計」一章，它給出瞭如何將二部匹配轉換爲獨立集問題的簡短描述，我不明白。

有沒有人知道任何詳細的matriel來描述這個過程？謝謝！

Answer 1

最大二分配匹配是一個二分圖中的一組邊，沒有兩個邊相鄰。最大獨立集是圖中的一組節點（頂點），沒有兩個頂點相鄰。

因此，您可以通過將二分圖中的每條邊轉換爲一個節點，然後在所有在原始圖中共享公共端點的新創建節點之間添加一條邊來將二分匹配問題轉換爲獨立集。那麼新圖中的最大獨立集合對應於原始問題中的最大二分配匹配。