algorithm - 证明图是二分图

Question

给定一个图 G，其中每条边连接偶数度节点和奇数度节点。如何证明该图是二分图？

提前致谢

Answer 1

这是 Welsh-Powell 图着色算法:

1. 所有顶点在列表V中根据其度数的递减值排序

2. 颜色在列表 C 中排序

3. V 中的第一个非着色顶点 v 被 C 中的第一个可用颜色着色。“可用”表示该算法之前未使用过的颜色

4. 遍历有序列表V的剩余部分，并为每个没有相邻顶点具有相同颜色的顶点分配相同的颜色

5. 迭代应用步骤 3 和 4，直到所有顶点都已着色

如果一个图是 2-colourable 的，则它是二分图。这个直观的事实在 Cambridge Tracts in Mathematics 131 中得到了证明。

---

当然，这是用来射蚊子的大炮。一个图是二分的当且仅当它的顶点可以分为两组，这样每条边都将集合 1 中的一个顶点连接到集合 2 中的一个顶点。您已经有了这样的划分:每条边连接奇数顶点集合中的一个顶点, 到偶数度顶点集合中的一个顶点。