Recall that we defined a graph to be -edge connected if for any edge , is still connected. Another way to define -edge connectivity would be if for every pair of vertices , there are atleast two edge disjoint paths from to . It turns out these two definitions are the same. Notice that one direction is trivial: if every pair of vertices have atleast two edge disjoint paths between them, then removing an edge can destroy at most one of these paths, hence is still connected. The other direction is left as an exercise.
Connectivity in directed graphs
Strongly connected graphs: A directed graph is strongly connected if for every pair of vertices there is a directed path in from to and a directed path from to .
Note that if we ignore arc directions, then a strongly connected graph is also -edge connected. This may be seen for example by observing that strong connectivity implies that for every edge , is still connected.
Algorithm for finding the strongly connected components
Recall that we can use to discover the -edge connected components of an undirected graph. An initial approach might be to convert to an undirected graph and use the algorithm for -edge connectivity on . However, while a strongly connected component is always a subset of a -edge connected component, the converse unfortunately is not true.
Another approach is the following:
- Run on and every time finishes expanding a vertex , add to a stack .
- Let be the graph with the direction of all the arcs reversed.
- While the stack is non-empty, pop a vertex from and perform on starting at . Let be the set of all the vertices visited by . Then is the strongly connected component containing . Remove from and repeat.
This algorithm is known as Kosaraju’s algorithm and gives the strongly connected components of .