给定一个图 G,其中每条边连接偶数度节点和奇数度节点。如何证明该图是二分图?
提前致谢
最佳答案
这是 Welsh-Powell 图着色算法:
所有顶点在列表V中根据其度数的递减值排序
颜色在列表 C 中排序
V 中的第一个非着色顶点 v 被 C 中的第一个可用颜色着色。“可用”表示该算法之前未使用过的颜色
遍历有序列表V的剩余部分,并为每个没有相邻顶点具有相同颜色的顶点分配相同的颜色
迭代应用步骤 3 和 4,直到所有顶点都已着色
如果一个图是 2-colourable 的,则它是二分图。这个直观的事实在 Cambridge Tracts in Mathematics 131 中得到了证明。
当然,这是用来射蚊子的大炮。一个图是二分的当且仅当它的顶点可以分为两组,这样每条边都将集合 1 中的一个顶点连接到集合 2 中的一个顶点。您已经有了这样的划分:每条边连接奇数顶点集合中的一个顶点, 到偶数度顶点集合中的一个顶点。
关于algorithm - 证明图是二分图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34856765/