二分图

二分圖的範例

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

特性

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

圖為二分图若且唯若

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

參見

• 完全二分图
• 因子圖
• Tanner圖
• Petri網