graph - 如何删除边以使图二分？

Question

我有一个图，它可能（或可能不）包含一组使其成为二分的边。我怎样才能发现这样的集合是否存在？

在 BFS 遍历期间删除特定级别中的所有边会有所帮助吗？

Answer 1

由于任何二分图也是 2-colorable 的，因此您可以使用任何算法来检查此特征。例如，您可以使用基于回溯的算法使用 BFS 来实现。一般来说，它可能看起来像这样：

假设如果图是二分的，则顶点可以分为 A 组和 B 组。选择一个源顶点，将其涂成红色（A 组）。然后将所有相邻顶点着色为蓝色（B 组），然后将这些邻居的邻居着色为红色。如果在着色过程中您发现一个与当前顶点具有相同颜色的邻居，则它不是 2-colorable 的，因此不是二分的。这可能不会涵盖所有细节，但您应该明白这一点。