Discrete Mathematics for Computer Science

402 CHAPTER 6 Graph Theory

The induced subgraph D 1 formed from the set of vertices still marked FALSE that

remain will be a dag with fewer than n vertices. Therefore, by the induction hypothesis,

this dag will be topologically sorted correctly. It remains to observe that no vertex in D 1 -

say, v--can be the head of an edge-say, (w, v)-such that w is already on the list. This

is true because if w occurred on the list, then v would have been visited by the depth

first search when w was encountered and, consequently, v would have been put on the

stack before w. This means that each vertex in D, can be placed on the stack after all the

vertices already on the stack without violating any of the constraints represented by D.

Therefore, n E T.

By the Strong Form of Mathematical Induction, 7T = {n E N : n > 11. U

Figure 6.61 shows the resulting order for the dag shown where the depth first search

begins at A and the vertices adjacent to A are put on its adjacency list in the order B, E, D.

B

Figure 6.61 TopSort on a dag. Topological sort order: A, D, E, F, B, C, G. E F

U Connectivity in Directed Graphs

The notion of connectedness for a directed graph is not as simple as the notion of con-

nectedness for undirected graphs. The reason is that directed edges represent an adjacency

between the tail and the head of the edge, but not one between the head and the tail of the

edge. The simplest notion of connectedness for directed graphs, called weakly connected,

holds whenever the underlying graph (that is, the undirected graph formed by omitting the

directions on the edges of the directed graph and eliminating multiple edges if both (a, b)

and (b, a) are in the directed graph for some pair of vertices a and b) is connected. A

directed graph that is not weakly connected is called disconnected.

6.18.1 Strongly Connected Directed Graphs

A second notion of connectedness for directed graphs depends on the existence of directed

paths from v to w and from w to v for each pair of vertices v and w. A directed graph with

such paths for each pair of vertices is called strongly connected. A strongly connected

component of a digraph is a directed subgraph that is strongly connected and is not con-

tained in any larger strongly connected subgraph. The graph shown in Figure 6.62(a) is

strongly connected, and the graph shown in Figure 6.62(b) is not. The graph shown in

Figure 6.62(b) actually has three strongly connected components.

1

5 ý2 5 >2

4 3 4 3

(a) (b)

Figure 6.62 Digraphs with and without the path property.