二部圖

二分圖的範例

二部圖(bipartite)又稱雙分圖、二分圖，指頂點可以分成兩個不相交的集使得在同一個集內的頂點不相鄰（沒有共同邊）的圖。

[编辑] 特性

• 最小頂點覆蓋集的基數等於最大獨立集的基數
• 最大獨立集的基數與最大匹配的基數之和，等於頂點數目
• 連通的二部圖：
  • 最小頂點覆蓋集的基數等於最大匹配的基數

[编辑] 圖為二部圖若且唯若……

• 沒有奇數圈
• 點色數為2

[编辑] 參見

• 完全二部圖
• 因子圖
• Tanner圖
• Petri網