Listen To Part 16-1
23.2-6 Give an efficient algorithm to test if a graph is bipartite.
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?
Listen To Part 17-1
23.4-3 Give an O(n) algorithm to test whether an undirected graph contains a cycle.
Listen To Part 17-7
23.4-5 Show that you can topologically sort in O(n+m) by repeatedly deleting vertices of degree 0.
Listen To Part 17-12
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.
Listen To Part 17-13
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.
Listen To Part 17-14
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?
Listen To Part 17-16
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.