Testing Bipartiteness

A bipartite graph G = (V, E) is a graph whose vertex set V can be partitioned into two disjoint sets X and Y such that every edge in E has one endpoint in X and the other in Y. Informally, a graph is bipartite if we can color its vertices red or black such that each edge connects a red vertex to a black vertex.

If G is bipartite, then it cannot contain any odd-length cycles. In fact, the converse is also true. If a graph G does not contain any odd-length cycles, then it is bipartite. Thus, odd cycles are the only obstacle to bipartiteness.

We can determine whether a graph is bipartite in linear time by doing a single BFS or DFS traversal. The pseudocode below checks bipartiteness with BFS.

Take a look at C++ implementation.

Try your hand at problem BUGLIFE which uses this idea.

Reference: Algorithm Design by Kleinberg and Tardos

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s