*
23.2-6 Give an efficient algorithm to test if a graph is bipartite.
*

Bipartite means the vertices can be colored red or black such that no edge links vertices of the same color.

We can augment either BFS or DFS when we first discover a new vertex, color it opposited its parents, and for each other edge, check it doesn't link two vertices of the same color. The first vertex in any connected component can be red or black!

Bipartite graphs arise in many situations, and special algorithms are often available for them. What is the interpretation of a bipartite ``had-sex-with'' graph?

How would you break people into two groups such that no group contains a pair of people who hate each other?

*
23.4-3 Give an O(n) algorithm to test whether an undirected graph
contains a cycle.
*

If you do a DFS, you have a cycle iff you have a back edge. This gives an

*
23.4-5 Show that you can topologically sort in O(n+m) by repeatedly
deleting vertices of degree 0.
*

The correctness of this algorithm follows since in a DAG there must always be a vertex of indegree 0, and such a vertex can be first in topological sort. Suppose each vertex is initialized with its indegree (do DFS on G to get this). Deleting a vertex takes

Time:

Strongly Connected Components

A directed graph is strongly connected iff there is a directed path between any two vertices.

The strongly connected components of a graph is a partition of the vertices into subsets (maximal) such that each subset is strongly connected.

- Call DFS( ) to compute finishing times for each vertex.
- Compute the transpose graph (reverse all edges in G)
- Call DFS( ), but order the vertices in decreasing order of finish time.
- The vertices of each DFS tree in the forest of DFS( ) is a strongly connected component.

This algorithm takes *O*(*n*+*m*), but why does it compute strongly connected
components?

**Lemma**: If two vertices are in the same strong component, no path between
them ever leaves the component.

Proof: Consider the first vertex *v* in the component to be discovered.
Everything in the component is reachable from it, so we will
traverse it before finishing with *v*.

What does DFS( , v) Do?

It tells you what vertices have directed paths to *v*,
while DFS( ,*v*) tells what vertices have directed paths from *v*.
But why must any vertex in the search tree of DFS( , *v*) also
have a path from *u*?

Example of Strong Components Algorithm

5, 6, 8 can reach *5*, oldest remaining is *7*.

7 can reach *7*, oldest remaining is *1*.

1, 2, 3 can reach *1*, oldest remaining is *4*.

4 can reach *4*.

Mon Jun 2 09:21:39 EDT 1997