最大點/邊獨立集 最小點/邊覆蓋 最大團 相關性統整-2 二分圖

今天再來說明一次二分圖上有特殊的性質，今天主要會講如何找出這些問題的一組解。

同樣先列出問題：

1. 最大獨立集：是一張圖中，最多有幾個點互不相鄰的最大集合。
2. 最大匹配：為圖上最大的邊集使得每個點至多和一條邊相鄰(又稱最大獨立邊集)。
3. 最小點覆蓋：最小的點集使得圖上每條邊都至少與點集中一個點相鄰。
4. 最小邊覆蓋：最小的邊集使得圖上每個點都至少與邊集中一條邊相鄰。
5. 最大團：一個最大的子圖使得圖中每兩點皆有一條邊連接(完全圖)。

性質為：

1. |最大匹配|=|最小點覆蓋|
2. |最大獨立集|=|最小邊覆蓋|
3. |最大獨立集|=|V|-|最大匹配|
4. |最大圖|=|補圖的最大獨立集|

現在說明找出如何找出在二分圖解出這些問題的方法。

1. 最大匹配：二分圖分兩群，分成x群和y群，對x群每個點做DFS一次，如果找到新的一條邊就紀錄下來。詳細可以看 https://allem40306.github.io/blog/2019/02/12/POJ3692-Kindergarten/ 這篇文章。
2. 最小點覆蓋：根據選到的匹配邊，看邊所連接的的兩點如果有其中一點連接到未匹配的點，那麼該點就是的最小點覆蓋的點。
3. 最大獨立集：剛好跟最小點覆蓋互補。
4. 最大團：轉補圖求最大獨立集
5. 最小邊覆蓋：最大匹配的邊，加上每個未匹配邊所連接的其中一條。

以上如果有錯，歡迎到 https://www.facebook.com/allem40306codeblog/ 糾正我。

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)