二分圖筆記

今天我研究了二分圖，整理了以下兩件事。

第一個是二分圖判定，有兩種方式可以判斷一張”連通圖”是否為二分圖。一個是DFS或BFS，首先把一個點標記為1，那麼與它相鄰的點都要標示為-1，當遍歷到-1的點，就要把它相鄰的點標記為1，以此類推，如果發現有不合規定的，那麼就不是二分圖了。第二種方式是用並查集，相鄰的點為兩個不同陣營，用並查集維護這件事情，如果遇到矛盾，那麼就不是二分圖了。

第二個是二分圖的性質，先講幾個圖論中常遇見的問題。

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

這些問題在二分圖中有很好的性質，利用這些性質可以加快解題思考的時間。

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

筆記在寫到這裡，至於code暫時沒有要放上這篇文章，但之後會有關於二分圖的題目。

---

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