最大點/邊獨立集 最小點/邊覆蓋 最大團 相關性統整-1 一般圖

昨天有提到一些問題在二分圖上有特殊的性質，其實那些性質在一般圖只有一個是沒有，這幾天就來做統整和簡單說明怎麼找出答案。

先把幾個問題列出來。

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

性質有：

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

以下簡略說明如何解出這些問題。

1. 最大匹配用來縮花演算法(blossom algorithm)算出最大匹配。
2. 求出最大匹配，也可以找出最小點覆蓋，只要將邊匹配的邊，對每個未被匹配的點取一條邊，就是最小邊覆蓋了。
3. 利用枚舉方式求出最大團。
4. 最大獨立集轉成補圖，然後找出最大團，即是最大獨立集。
5. 最小點覆蓋和最大獨立集為互補，求出最大獨立集即可推出最小點覆蓋。

以上就是一般圖求最大點/邊獨立集、最小點/邊覆蓋及最大團的辦法，接下來會說在二分圖和樹上的求法。

參考資源：
http://www.csie.ntnu.edu.tw/~u91029/Domination.html
http://www.csie.ntnu.edu.tw/~u91029/Matching.html
http://www.csie.ntnu.edu.tw/~u91029/ChordalGraph.html

---

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