graph - 二部图和偶数循环

Question

二分图是一个图，其顶点可以分为两个不相交的集合 U 和 V，使得每条边都将 U 中的一个顶点连接到 V 中的一个顶点；也就是说，U 和 V 都是独立的集合。等效地，二分图是不包含任何奇数长度循环的图。

我还可以说，如果在图 G 中所有循环的长度都是偶数，那么它是二分的吗？

我想到了一个偶数周期图，结果证明它是非二分的。

     1----------2
     |          |
     |          |
     |          |
     |          |
     3----------4

Answer 1

如果在图 G 中所有环的长度都是偶数，则它是二分的。

将 BFS 算法应用于图 G。它将 G 的顶点划分为层。集合 U 由奇数层的顶点组成，V 由偶数层的顶点组成。让我们假设（通过矛盾）存在连接来自 U的一些两个顶点x、y的边e 。让r是由 BFS 算法确定的树的根。然后从x到r，从r到y和边e的路径是奇数长度的循环 - 这是矛盾的，因为图 G 不包含奇数长度的循环。（与第 V 组相同）。