二分图

二分图，也称为双图，是一组图顶点的集合，这些顶点被分解成两个不相交的集合，使得同一集合内的任意两个图顶点都不相邻。二分图是 k-部图 的一个特例，其中 。上面的图示展示了一些二分图，每个图中的顶点都根据它们所属的两个不相交的集合进行了着色。

二分图等价于可二着色图。所有无环图都是二分图。一个有环图是二分图当且仅当其所有环的长度均为偶数 (Skiena 1990, p. 213)。

二分图族包括

1. 无环图（即，树和森林），

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)。