二分圖,也稱為雙圖,是一組圖頂點的集合,這些頂點被分解成兩個不相交的集合,使得同一集合內的任意兩個圖頂點都不相鄰。二分圖是 k-部圖 的一個特例,其中 。上面的圖示展示了一些二分圖,每個圖中的頂點都根據它們所屬的兩個不相交的集合進行了著色。
二分圖等價於可二著色圖。所有無環圖都是二分圖。一個有環圖是二分圖當且僅當其所有環的長度均為偶數 (Skiena 1990, p. 213)。
二分圖族包括
2. 書圖 ,
3. 交叉稜柱圖,
4. 冠圖 ,
5. 環圖 ,
6. 齒輪圖,
7. 網格圖,
8. Haar 圖,
9. Hadamard 圖,
10. 超立方體圖 ,
11. 騎士圖,
12. 梯形圖,
13. 梯級圖 (它們是森林)。
14. 路徑圖 (它們是樹),
15. 蒙古包圖,
16. 謝爾賓斯基地毯圖,
17. 堆疊書圖,
18. 星圖 (它們是樹)。
柯尼希線著色定理指出,每個二分圖都是 1 類圖。柯尼希-艾格瓦里定理指出,對於二分圖,匹配數(即最大獨立邊集的大小)等於頂點覆蓋數(即最小最小頂點覆蓋的大小)。
可以使用 Wolfram 語言測試一個圖是否為二分圖,方法是使用BipartiteGraphQ[g],並且可以使用以下方法找到二分圖的其中一個分量的索引FindIndependentVertexSet[g][[1]]。
節點數為 , 2, ... 的二分圖的數量是 1, 2, 3, 7, 13, 35, 88, 303, ... (OEIS A033995)。
節點數為 , 2 ... 的連通二分圖的數量是 1, 1, 1, 3, 5, 17, 44, 182, ... (OEIS A005142)。