二分圖

定義

二分圖，又稱二部圖，英文名叫 Bipartite graph。

二分圖是什麼？節點由兩個集合組成，且兩個集合內部沒有邊的圖。

換言之，存在一種方案，將節點劃分成滿足以上性質的兩個集合。

性質

• 如果兩個集合中的點分別染成黑色和白色，可以發現二分圖中的每一條邊都一定是連接一個黑色點和一個白色點。

• 二分圖不存在長度為奇數的環

  Note

  因為每一條邊都是從一個集合走到另一個集合，只有走偶數次才可能回到同一個集合。

判定

如何判定一個圖是不是二分圖呢？

換言之，我們需要知道是否可以將圖中的頂點分成兩個滿足條件的集合。

顯然，直接枚舉答案集合的話實在是太慢了，我們需要更高效的方法。

考慮上文提到的性質，我們可以使用 DFS（圖論） 或者 BFS 來遍歷這張圖。如果發現了奇環，那麼就不是二分圖，否則是。

應用

二分圖最大匹配

詳見 二分圖最大匹配 頁面。

二分圖最大權匹配

詳見 二分圖最大權匹配 頁面。

一般圖最大匹配

詳見 一般圖最大匹配 頁面。

一般圖最大權匹配

詳見 一般圖最大權匹配 頁面。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用