Testing Bipartiteness: An Application of Breadth-First Search

A bipartite graph is a graph where one node V can be partitioned into sets X and Y where X are red and Y are blue. In a bipartite graph it is possible to color all the nodes blue and red so every edge has one red end and one blue end.

(3.14) A graph is not bipartite if it contains an odd-length cycle.

How can we test for bipartiteness?

The Algorithm:

• Assume the graph is connected
• pick any node s in V and color it red
• color all neighbors of S blue
• color all of their neighbors red and so on until the graph is completely colored

The algorithm design is identical to BFS as we are moving outward from s (color odd layers blue and even layers red) The total running time is O(m+n)

(3.15) Claim Let G be a connected graph, and let L₁, L₂,… be the layers produced by BFS starting at node s. Then exactly one of the following two things must hold

1. There is no edge of G joining two nodes of the same layer. In this case G is a bipartite graph in which the nodes in even-numbered layers can be colored red, and the nodes in odd-numbered layers can be colored blue
2. There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite.

The Proof

Consider case 1 where there is no edge joining two nodes of the same layer by theorem 3.4 we know every edge of G joins nodes in either the same or adjacent layer. In this case we assume they never join in the same layer, so every edge joins two nodes in adjacent layers. Because the coloring gives nodes in adjacent layers opposite colors, we know every edge has ends with opposite colors and the graph is bipartite.

Consider case 2 where G must contain an odd cycle so there is an edge that connects two nodes in the same layer. Supposed the two nodes in the same layer, x and y, are in layer L_j. Let z be the node that is in layer L_i, the lowest common ancestor, the node that is directly above x and y, and L_i > L_j. There is a cycle in the path z-x and y-z. The length of the cycle is 2(j-i)+1 which is an odd number.

Connectivity in Directed Graphs

In this section we see what ideas we applied to undirected graphs can apply to directed graphs.

A directed graph has direction to its edges. Say an edge (u, v) has a direction that goes from u to v, its relationship is asymmetric.

How we represent Directed Graphs:

• We use the adjacency list representation but modify it so instead of each node having a single list of neighbors each node has two lists: one that has nodes that is points to and one that has nodes that point to it.

Graph Search Algorithms

BFS search in directed graphs computes the set of all nodes with the property that s has a path to t, not that t has a path to s. It is very similar to BFS of undirected graph and has the same runtime of O(m+n) DFS search also runs in linear time and compute the same set of nodes.

Strong Connectivity