Strongly Connected Components
Recall the algorithm that we proposed last time for finding the strongly connected components of a graph . Let be the strongly connected components of . Let be the graph with vertex set and if there exists and such that .
We claim that has no directed cycles, in other words is a directed acyclic graph (often shortened to dag). Suppose not and there is a directed cycle from to . Notice that this means that there is a directed path in from every vertex in to every vertex in and vice versa. This contradicts the hypothesis that and are distinct strongly connected components.
Let us consider the algorithm again:
- Call on from an arbitrary vertex.
- Number vertices according to the order in which finishes examining all out edges from that vertex. This number for vertex is also referred to as .
- Let be with all arcs reversed. Call on in decreasing order of their numbers.
- Output the explored vertices whenever has to start at a new vertex.
We first observe that the strongly connected components of is precisely , i.e. the same as the strongly connected components of .
We also observe that if then the highest number in is larger than the highest number in . If the visits a vertex of before visiting any vertex of then clearly every vertex of will be explored before returning. Thus the highest number in will be larger than the highest number in . If the visits a vertex of first before visiting any vertex of then clearly all of will be explored and no vertex of will be explored when returns. Thus we need to call on a vertex of at some later point in time and so the claim follows.
Thus the vertex with the highest number must be a source strongly connected component in and so a sink strongly connected component in . Thus if we start in the order of decreasing number then from the above observation we will find exactly the strongly connected components of .
Note: At first glance it might appear that we could also run the algorithm on in the order of the lowest numbers. However it is not true that if then the lowest post number in is smaller than the lowest number in . An easy counter example is when is a cycle and is a single vertex . Let where . Suppose was called on and the order of traversal was before returning back to vertex and then exploring . Since , clearly vertex has post number strictly smaller than .
Minimum Spanning Tree
Given a weighted un-directed graph with weights . We wish to compute a minimum weight spanning tree of . Here is a greedy algorithm that solves this problem:
- Initialize .
- Order the edges as such that .
- Pick the lowest weight edge such that has no cycles.
- Set .
- Stop when .
This algorithm is called Kruskal’s algorithm and it produces a minimum weight spanning tree.
Lemma: Every edge is a minimum weight edge in some cut in .