A bipartite graph GV E is an undirected graph whose vertices

A bipartite graph G(V, E) is an undirected graph whose vertices can be partitioned into two disjoint sets V1 and V2 = V-V_1 with the properties that no two vertices in V1 are adjacent in G and no two vertices in V2 are adjacent in G. All edges go between the two sets V1 and V2. Is the following graph G a bipartite graph? Write your algorithm to determine whether the graph G is bipartite and the two disjoint sets V1 and V2 if it is a bipartite.

Solution

A graph is bipartite if the nodes can be partitioned into 2 sets v1 and v2 such that all edges go only between v1 and v2(no edges go from v1 to v1 or from v2 to v2)

The above graph has v1={1,4,5,6,7,11} and v2={2,3,8,9,10}

so the above graph is a bipartite graph.

Algorithm:

Based on coloring also we can determine the bipartite graph.

In other to determine if a graph G = (V, E) is bipartite, we perform a BFS on it with a little modification such that whenever the BFS is at a vertex u and encounters a vertex v that is already \'gray\' our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[u] and d[v] have the same parity, then the graph is not bipartite.

For each vertex u in V[G] {s}
   do color[u] WHITE
        d[u]
        partition[u] 0
color[s] GRAY
partition[s] 1
d[s] 0
Q [s]
while Queue \'Q\' is non-empty
      do u head [Q]
         for each v in Adj[u] do
                if partition [u] partition [v]
                   then   return 0
                 else
                       if color[v] WHITE then
                            then color[v] gray
                                   d[v] = d[u] + 1
                                   partition[v] 3 partition[u]
                                   ENQUEUE (Q, v)
           DEQUEUE (Q)
Color[u] BLACK
Return 1