Discrete Mathematics for Computer Science

Connectivity in Directed Graphs 403

The property of having two directed paths joining a pair of vertices, one path in each

direction, defines a relation on the vertices of a directed graph. This relation helps us to

understand strong connectivity in directed graphs.

Definition 1. Let D = (V, E) be a directed graph. For all v, w e V define v STCONN

w if and only if there is a directed path in D from v to w and a directed path in D from w

to V.

Although STCONN may seem to be an abstract way to approach the notion of connect-

edness for directed graphs, use of this relation makes it easier to find the strongly connected

components of a directed graph-that is, the largest strongly connected subgraphs.

Theorem 1. STCONN is an equivalence relation.

Proof. Show that the relation STCONN is reflexive, symmetric, and transitive. Let D -

(V, E) be a directed graph. For each v E V, the vertex itself is a directed path from v to

v. Thus, v STCONN v for each v E V, and the relation is reflexive. For vertices v, w e V

such that v STCONN w, there is a directed path in D from v to w and a directed path from

w to v. Since there is a directed path from w to v and a directed path from v to w, it follows

that w STCONN v. This proves that STCONN is symmetric.

Finally, for vertices u, v, w E V such that u STCONN v and v STCONN w, it will

follow that u STCONN w. Since u STCONN v, there are directed paths in D from u to v

and from v to u. Since v STCONN w, there are directed paths in D from v to w and from

w to v. Using the directed paths from u to v and v to w, form a directed trail that starts

at u and ends at w. If a vertex occurs twice in this path, it is easily eliminated so that a

path results. Similarly, form a directed trail from w to u. Delete any directed cycles from

these newly formed directed trails to form directed paths. Therefore, u STCONN w, and

the relation STCONN is transitive.

Since STCONN is reflexive, symmetric, and transitive, STCONN is an equivalence

relation. 0

The induced subgraphs determined by the equivalence classes of D relative to

STCONN are the strongly connected components of D. The example in Figure 6.63 shows

that the strongly connected components may not include all the edges of the directed graph.

In particular, (h, g) and (h, i) are such edges. A directed graph that has exactly one strongly

connected component is called strongly connected.

b h b

a a c gh

a f f

e d e d

D Strongly connected components

Figure 6.63 Strongly connected components.