Jan 30. Strong connectivity in directed graphs.

Edge Connectivity

Recall that we defined a graph to be 2-edge connected if for any edge e \in E(G), G\setminus \{e\} is still connected. Another way to define 2-edge connectivity would be if for every pair of vertices i,j \in V(G), there are atleast two edge disjoint paths from i to j. It turns out these two definitions are the same. Notice that one direction is trivial: if every pair of vertices i,j have atleast two edge disjoint paths between them, then removing an edge e \in E(G) can destroy at most one of these paths, hence G\setminus \{e\} is still connected. The other direction is left as an exercise.

Connectivity in directed graphs

Strongly connected graphs:  A directed graph D = (V, A) is strongly connected if for every pair of vertices u, v \in V(G) there is a directed path in D from u to v and a directed path from v to u.

Note that if we ignore arc directions, then a strongly connected graph is also 2-edge connected. This may be seen for example by observing that strong connectivity implies that for every edge e, G\setminus \{e\} is still connected.

Algorithm for finding the strongly connected components

Recall that we can use DFS to discover the 2-edge connected components of an undirected graph. An initial approach might be to convert D to an undirected graph and use the algorithm for 2-edge connectivity on G. However, while a strongly connected component is always a subset of a 2-edge connected component, the converse unfortunately is not true.

Another approach is the following:

  • Run DFS on D and every time DFS finishes expanding a vertex v, add v to a stack S.
  • Let D^R be the graph D with the direction of all the arcs reversed.
  • While the stack S is non-empty, pop a vertex v from S and perform DFS on D^R starting at v. Let U be the set of all the vertices visited by DFS(v). Then U is the strongly connected component containing v. Remove U from S and repeat.

This algorithm is known as Kosaraju’s algorithm and gives the strongly connected components of D.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s