One may wonder why the topic of bipartite and 2-colourable graphs has anything
to do with a section on graph cycles. Well it turns out that a graph is bipartite
or 2-colourable if and only if the graph does not have any cycles of odd length.
We will shortly present a search algorithm to decide this. First we need to
give some formal definitions.
Definition 22. A graph 
is bipartite if the vertices can
be partitioned into two disjoint sets 
such that each
arc/edge 
of 
has 
and 
or 
and 
.
With this definition we can see that any cycle that starts at any vertex 
must alternate between vertices in 
and 
and hence must
be of even length (on return to again).
Definition 23. A graph is k-colourable if there exists an
labeling of the vertices 
with colours 
such that
for each arc/edge of the colour of and 
differ.
Clearly any graph may be coloured with 
colours. If a graph
is bipartite then we can use just two colours - one colour for each partition
and of .
Below we present a modified BFS algorithm to decide whether a graph is bipartite
or not.
static public boolean isBipartite(Graph Gin)
{
uGraph G = new uGraph(Gin); // color underlying graph
int n = G.order();
int color[] = new int[n]; // will toggle between 1 and 2
for (int v=0; v<n; v++) // start at first vertex
{
if (color[v]>0) continue;
color[v] = 1;
Queue toGrow = new Queue(); // use BFS queue search
toGrow.enque(new Integer(v));
while (!toGrow.empty())
{
int grow = ((Integer) toGrow.deque()).intValue();
Vector nbrs = G.neighbors(grow);
for (int i=0; i<nbrs.size(); i++)
{
int u = ((Integer) nbrs.elementAt(i)).intValue();
if ( color[u] == 0 ) // not colored yet
{
color[u] = 3 - color[grow]; // set to other color
toGrow.enque(new Integer(u));
}
else // check for different color
{
if ( color[u] == color[grow] ) return false;
}
}
} // more nodes in this component
} // while all components have been checked
return true;
}
The only tricky part of the above algorithm is our way of switching between colour 1 and 2, (3 minus ``previous colour''). We use the array color to indicate when all vertices (all components) have been coloured.
Below we give a test program for the three algorithms of this section. This time we read in a le of graphs using the first command-line argument as the filename.
import java.io.*;
public class cycles {
public static void main(String argv[])
{
try {
BufferedReader input = new BufferedReader(new FileReader(argv[0]));
while(true)
{
Graph G = new Graph(input);
int n=G.order(); if ( n == 0 ) break;
System.out.print(G.toStringAdjLists());
if ( GraphAlgs.isAcyclic(G) )
{
System.out.print(&#;`¨Graph is acyclic, &#;`¨);
}
else
{
System.out.print(&#;`¨Graph is not acyclic, &#;`¨);
}
System.out.print(&#;`¨has underlying girth &#;`¨ + GraphAlgs.girth(G));
if ( GraphAlgs.isBipartite(G) )
{
System.out.println(&#;`¨, and is 2-colorable.&#;`¨);
}
else
{
System.out.println(&#;`¨, and is not 2-colorable.&#;`¨);
}
}
} catch ( Exception e ) { System.err.println(&#;`¨Exception: &#;`¨+e); }
} // main
} // class cycles
A sample run on the three graphs of Example 21 is given below. (The $ line
indicates what the author typed at his unix command prompt.)
$ java cycles ex3.lists
9
2
3
0 3
1 2 4 5
3
3 6 7 8
5
5
5
Graph is not acyclic, has underlying girth 10, and is 2-colourable.
7
1 2
4 5
3
6
6
3 6
Graph is acyclic, has underlying girth 3, and is not 2-colourable.
9
1 2
0 4 5
0 3 5
2 6
1 6 7
1 2 7
3 4 8
4 5 8
6 7
Graph is not acyclic, has underlying girth 4, and is 2-colourable.
After printing out an adjacency lists representation of each graph we decide if it is acyclic, what the underlying girth is, and determine if it is bipartite (2-colourable). The first graph of order 9 is a tree (but cyclic as viewed as a digraph). Having girth undefined (denoted by 10) tells us that it is a tree. The second graph is a DAG but does have an underlying 3 cycle (and thus is not bipartite). Our algorithms did correctly find the 4 cycle of the third graph as its girth and concluded that it is 2-colourable (has only even-length cycles).