algorithm - 如何判断一个图是否是二分图？

Question

我一直在努力理解二分图。据我了解，它是一个图 G，可以分为两个子图 U 和 V。因此 U 和 V 的交集是一个空集，并集是图 G。我正在尝试使用 BFS 查找图是否是二分图。我仍然不清楚我们如何使用 BFS 找到它。

假设我们有如下定义的图形。

a:e,f
b:e
c:e,f,h
d:g,h
e:a,b,c
f:a,c,g
g:f,d
h:c,d

我在这里需要的是逐步解释这个图如何是二分图或不使用 BFS。

Answer 1

取自GeeksforGeeks

以下是使用广度优先搜索 (BFS) 确定给定图是否为二分图的简单算法:-

1. 将红色分配给源顶点(放入集合 U)。
2. 用蓝色给所有的邻居上色(放入集合 V)。
3. 用红色给所有邻居的邻居着色(放入集合 U)。
4. 这样，将颜色分配给所有顶点，使其满足 m 路着色问题的所有约束条件，其中 m = 2。
5. 在分配颜色时，如果我们找到一个与当前顶点颜色相同的邻居，则该图不能用 2 个顶点着色(或者图不是二分图)。

A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.

此外，注意:-

-> 可以使用两种颜色为具有偶数循环的循环图着色。

-> 用两种颜色给奇数圈的圈图上色是不可能的。

编辑:-

如果一个图没有连接，它可能有多个二分图。您需要使用上述算法分别检查所有这些组件。

因此，对于同一图的各种断开连接的子图，您需要使用上面讨论的相同算法分别对所有子图执行此二分检查。所有那些同一个图的各种断开连接的子图将解释它自己的一组二分图。

并且，该图将被称为二分图，当且仅当，其连接的每个分量都被证明是二分的。