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

A graph is strongly connected if for nodes u and v there is a path from u to v and v to u. This also means they are mutually reachable

(3.16)

If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable.

Proof The first path we take is from u to v and then from v to w. Since v is mutually reachable to w we can then go to the path w to v and then from v to u.

To test if a graph G is strongly connected we run a simple BFS starting from s and then another BFS starting from s in G reversed. If one of the searches fails to reach the node then the graph is not strongly connected.

(3.17)

For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.

Proof Two nodes s and t are mutually reachable so we claim that the strong components containing s and t are identical. So for any node v if s and v are mutually reachable then t and v are mutually reachable (by 3.16). But if s and t are NOT mutually reachable then there cannot be a node v that is in the strong component of each. If there were then s and v and v and t would be mutually reachable so s and t would be.

We can compute the strong components for all nodes in O(m+n)

I thought this section was pretty dry. It was short and easy to read but not that interesting to me. Readability: 8

Directed Acyclic Graphs and Topological Ordering A directed acyclic graph (DAG) has no cycles.

We use DAGs to represent dependencies or precedence relations for example showing a set of tasks where one is dependent on the other or one needs to be performed before the other can. Example: Course prerequisite for CS major. A DAG has a topological ordering which is an ordeing of its nodes so that for every edge (v_i, v_j), i<j. All of the edges must point forward in an ordering. 3.18 If G has a topological ordering, then G is a DAG.

An algorithm for finding a topological ordering:

3.19 In ever DAG, there is a node v with no incoming edges

Proof There is a directed graph G where every node has at least one incoming edge. To show how to find a cycle, we pick a node v and follow the edges backward from v since it has at least one incoming edge we can move to node u. And from u backward to x etc. After n+1 steps we will have visited some node twice which shows there is a cycle