如何查找图表是否为二分图？

Question

我一直试图理解二分图.据我所知,它是一个图G,可以分为两个子图U和V.So U和V的交集是一个空集,并且union是图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)查找给定图表是否为Birpartite的简单算法: -

1. 将RED颜色指定给源顶点(放入集U).
2. 用蓝色为所有邻居着色(放入设置V).
3. 用RED颜色为所有邻居的邻居着色(放入设置U).
4. 这样,为所有顶点指定颜色,使其满足m方式着色问题的所有约束,其中m = 2.
5. 在分配颜色时,如果我们找到与当前顶点颜色相同的邻居,则图形不能用2个顶点着色(或图形不是Bipartite).

如果可以使用两种颜色进行图形着色,使得一组中的顶点用相同颜色着色,则可以使用二分图.

另外,注意: -

- >可以使用两种颜色对均匀循环的循环图进行着色.

- >使用两种颜色无法对具有奇数周期的循环图进行着色.

编辑: -

如果图形未连接,则可能具有多个二分图.您需要使用上面提到的算法分别检查所有这些组件.

因此,对于同一图形的各种断开连接的子图,您需要使用上面讨论的相同算法分别对所有这些子图进行二分检查.所有这些相同图形的各种断开连接的子图将考虑其自己的二分组.

并且,该图将被称为二分,IF和ONLY IF,其每个连接的组件被证明是二分的.