Algorithms: Sequential, Parallel and Distributed 1-1
Chapter 13
Graph Connectivity and Fault Tolerance of Networks
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed 1-2
Lecture Notes
Overview
In Chapter 13 we study various connectivity properties of graphs and digraphs, and include a
discussion of the importance of these concepts in such areas as network design and
maintenance. We introduce the notion of a strongly connected component of a digraph, and
show how various depth-first numberings can be used to determine the strongly connected
components. We also introduce the notion of a biconnected component of a graph, and design
an algorithm to determine the articulation points of a graph. Fault tolerant routing schemes in
digraphs are designed and analyzed.
Chapter Objectives
After completing the chapter the student will know:
• The definition and importance of various connectivity properties in graphs and digraphs,
such as strongly connected components in a digraph, biconnected components and
articulation points in a graph, and fault tolerant routing schemes in a network
Instructor Notes
The graph algorithms presented in this chapter are somewhat more subtle than the minimum
spanning tree and shortest path algorithms presented in Chapter 12. Also, it is important to
stress that merely knowing the articulation points in a graph does not allow one to determine
the biconnected components. Most students will need to work rather harder to grasp the
algorithms in this chapter than those presented in Chapter 12.
Algorithms: Sequential, Parallel and Distributed 1-3
Solutions to Selected Exercises
Section 13.1 Strongly Connected Components
13.1 Choose a vertex r and perform an out-directed depth-first search rooted at r and an in-
13.2 Consider a tree Tj in the forest. Let u be any vertex of Tj and let Lu and Ru denote the left
and right subtrees of Tj rooted at u. Clearly, every vertex of Lu and every vertex of Ru must be
13.3 The following for loop computes the array PostNumInv[0:n – 1] from the array
PostNum[0:n – 1]
13.4
procedure DFTOut(D)
Input: D (a digraph with vertex set V and edge set E)
Output: the arrays PostNum[0:n – 1] and PostNumInv[0:n – 1]
Mark[0:n – 1] a 0/1 array initialized to 0’s
13.5 An out-directed depth-first search starting at a vertex u visits are nodes v for which there is
13.6 In the proof we will refer to a path from u to v simply as a u-v path.
Proof of Theorem 13.2.1
(1 implies 2) Let U denote the set of all vertices that lie in a common cycle with u. If U = V
then we are done. Otherwise, since G is connected there exist adjacent vertices v and w such
that w belongs to U, but v doesn’t. Let C be any cycle which contains both u and w. Since w is
uy and edge wv.
(4 implies 1) Assume that every two edges of G lie in a cycle, but G is not biconnected. Then
G contains an articulation point u, and there are two vertices v and w adjacent to u such that uv
and uw lie in different biconnected components. But, since uv and uw lie in a common cycle,
they must belong to the same biconnected component, a contradiction.
(7) there exists a path joining u and w that does not contain v. Thus, the graph G – v (obtained
13.7 Suppose to the contrary that v is not an ancestor of w in the DFS-tree Tr. Then vw will be
a cross edge, i.e., v and w will lie in two different branches of Tr. Let x be the ancestor of both
13.8 First the root vertex r has exactly one child in Tr. Then, the tree Tr – r obtained from Tr by
deleting r and its incident edge will be a spanning tree of the graph G – r. Thus, G – r is
connected, so that r is not an articulation point. Let u1, …, uc denote the c children in Tr of the
13.9 Suppose c is a vertex of depth at least 2 in Tr. First suppose there exists a bypass edge vw
for c. Then, the path in Tr from c to v, the edge vw and the path in Tr from w to r, from a path
13.10 First suppose u is an articulation point. Then, some child c has no bypass edge. Now
Lowest[c] is the minimum of DFSNum(c) and DFSNum(w) over all edges vw, where v is either
13.11 The result is immediate if v is leaf vertex. We prove the general result by induction on k
(13.2.2) is true for all vertices at level d – k (0 < k < d) and consider any non-leaf vertex v at
Algorithms: Sequential, Parallel and Distributed 1-6
level d – k – 1. Suppose c is any child of v. By induction hypothesis, Lowest[c] is the
13.15 Suppose to the contrary the B1 and B2 have two vertices x and y in common, and let B be
the union of B1 and B2 (i.e., the and vertex set and edge set of B is the union of the vertex and
13.18. We prove the result by induction. Let P0, …, Pq – 1 denote the ears of G where P0 is the
edge st, and Let Gi be the graph consisting of the union of the ears P0, …, Pi, i = 1, …, q – 1.
Since G1 is a cycle it is 2-connected establishing the basis step. Now assume that Gk – 1 is
biconnected, 2 ≤ k ≤ q – 1 and consider the graph Gk. To show that Gk is biconnected it is
13. 19 Consider a topological sorted ordering of an s-t oriented graph, and consider any vertex
v different from either s or t. Since s is the only source vertex and t is the only sink vertex in
13. 20 Suppose the edges are orientated according to algorithm in subsection 13.3.2. To prove
that the orientation generated by the algorithm is an s-t orientation, it is sufficient to show that,
for any vertex v different from s or t, there exists at least one edge directed into v and at least
one edge directed out of v, and that the orientation is acyclic. Let Pi be the ear containing v.
We first verify using induction on the index i (i = 0, …, n – 1) that, at some point in the
13.3.2, we can compute an s-t orientation and s-t ordering. Conversely, suppose there exists an
s-t orientation (s-t ordering). By successively following an edge directed out of each vertex
that is visited starting with vertex u we generate a path P from u to t. Similarly, by following
13. 22 Let u be any node different from s. Consider the path P in T1 from u to s and the path Q
in T2 from u to s. Since the parent of v is lower(v) for each v of T1 different from t and the
13. 23 Let u be any node different from s or t. Consider the path P in T1 from u to t and the path
Q in T2 from u to s. Since the parent in T1 of each vertex v different from s and t is an edge
directed out of v and the parent in T2 of each vertex v different from s and t is an edge directed
Page 4.10 Theorem 13.31. add “open” to “ear decomposition”TopSortLabel – don’t compute
label