查找最小頂點給定匹配最大值的二分圖覆蓋

Question

我似乎找到了算法，但無法理解它，我想知道是否有人知道該算法的通用輪廓。

這裏是鏈接到算法I 2頁

http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

Answer 1

上找到你首先應該知道二分圖，兩組頂點和邊，OK，你現在知道了。

那麼你需要從兩組中選擇一些頂點來覆蓋所有的邊。只要選擇一個頂點，就會覆蓋與其鏈接的所有邊。現在你的任務是選擇最小數量的頂點，以覆蓋所有的邊緣。

原理意味着，您需要的最小數量等於最大匹配對的數量。

Answer 2

算法是這麼簡單：

1. 查找匹配頂點，將其標記爲不包括在最低頂點覆蓋。
2. 將該頂點的所有匹配鄰居標記爲包含在最小頂點覆蓋中。
3. 將上一步驟中所有頂點的配合視爲不匹配的頂點並重復步驟1.
4. 如果遞歸結束，則從步驟1（即圖的幾個連接組件的情況）重複。
5. 如果沒有不匹配的頂點，請取所有剩餘的對並以任何喜歡的方式標記它們（請記住，對中的一個頂點必須包含在最小頂點覆蓋中，而另一個頂點必須不包括 ）。

P.S.我知道這是necroposting。