证明图是二分图

Prove that a graph is bipartite

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

提前致谢

因为根据定义，您已经有两组不相交的顶点，因此只有边在一组顶点和另一组顶点之间。

偶数度节点为一组，奇数度节点为另一组

选择任何节点，将其放入集合 A。将所有 link 的节点放入集合 B。现在对于添加的每个节点，将其所有邻居添加到相反的集合，并且检查已经属于其中一组的那些，它们是否在正确的集合中。如果出现矛盾，则该图不是二分图。

如果您 运行 没有邻居但仍有节点，请再次选择任何节点并继续算法，直到您没有节点或发现矛盾。

这是Welsh-Powell图形着色算法：

  1. 所有顶点在列表V

    2. 中按照度数递减排序

  2. 颜色在列表 C

    3. 中排序

  3. V中的第一个non-coloured顶点v用C中的第一个可用颜色着色。"Available"表示该算法以前未使用过的颜色

  4. 遍历有序链表V的剩余部分，为所有相邻顶点没有相同颜色的顶点分配相同的颜色

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

如果一个图是二分色的，那么它就是二分图。这个直观的事实在 Cambridge Tracts in Mathematics 131 中得到了证明。

这当然是用来打蚊子的大炮了。一个图是二分的当且仅当它的顶点可以分为两组，这样每条边都将第 1 组中的一个顶点连接到第 2 组中的一个顶点。你已经有了这样的划分：每条边连接 odd-degree 顶点，到 even-degree 个顶点集合中的一个顶点。

如果"prove"，你的意思是"find out"，完整的解决方案在这里

Bipartite.java

它通过保留两个布尔数组来工作。一个标记的数组，用于检查是否已访问节点，以及另一个彩色数组。然后它进行深度优先搜索，用不同的颜色标记邻居。如果邻居用相同的颜色标记，则图不是二分图。