如何判断一个图是否是二部图? [英] How to find if a graph is bipartite?

问题描述

我一直在尝试理解二部图.据我所知，它是一个图 G，它可以分为两个子图 U 和 V.所以 U 和 V 的交集是一个空集，并集是图 G.我试图找出一个图是否是二部图或不使用 BFS.我仍然不清楚我们如何使用 BFS 找到它.

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

a:e,f是c:e,f,hd:g,he:a,b,cf:a,c,gg:f,dh:c,d

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

解决方案

摘自 GeeksforGeeks

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

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

<块引用>

如果可以使用图形着色，则可以使用二部图两种颜色，使得集合中的顶点具有相同的颜色颜色.

另外，注意:-

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

-> 不可能使用两种颜色为奇周期的周期图着色.

-

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

因此，对于同一图的各种不连接子图，您需要使用上述相同的算法分别对所有这些子图进行二分检查.所有那些同一图的各种不连贯子图都将说明其自己的二分集.

而且，该图将被称为二部图，当且仅当，它的每个连接组件都被证明是二部的.

I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union is graph G. I am trying to find if a graph is bipartite or not using BFS. Still it is not clear to me that how can we find this using BFS.

Let us say we have graph defined as below.

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

What i need here is step by step explanation of how this graph is a bipartite or not using BFS.

解决方案

Taken from GeeksforGeeks

Following is a simple algorithm to find out whether a given graph is Birpartite or not using Breadth First Search (BFS) :-

1. Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite).

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.

Also, NOTE :-

-> It is possible to color a cycle graph with even cycle using two colors.

-> It is not possible to color a cycle graph with odd cycle using two colors.

EDIT :-

If a graph is not connected, it may have more than one bipartition. You need to check all those components separately with the algorithm as mentioned above.

So, for various disconnected sub-graph of the same graph, you need to perform this bipartition check on all of them separately using the same algorithm discussed above. All of those various disconnected sub-graph of the same graph will account for its own set of bipartition.

And, the graph will be termed bipartite, IF AND ONLY IF, each of its connected components are proved to be bipartite .

这篇关于如何判断一个图是否是二部图?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！