204 DIRECTED GRAPHS [CHAP. 9
Connectivity
There are three types of connectivity in a directed graphG:(i) Gisstrongly connectedorstrongif, for any pair of verticesuandvinG, there is a path fromutov
and a path fromvtou, that is, each is reachable from the other.
(ii) Gisunilaterally connectedorunilateralif, for any pair of verticesuandvinG, there is a path from
utovor a path fromvtou, that is, one of them is reachable from the other.
(iii) Gisweakly connectedorweakif there is a semipath between any pair of verticesuandvinG.LetG′be the (nondirected) graph obtained from a directed graphGby allowing all edges inGto be nondirected.
Clearly,Gis weakly connected if and only if the graphG′is connected.
Observe that strongly connected implies unilaterally connected which implies weakly connected. We say
thatGisstrictly unilateralif it is unilateral but not strong, and we say thatGisstrictly weakif it is weak but not
unilateral.
Connectivity can be characterized in terms of spanning paths as follows:
Theorem 9.2: LetGbe a finite directed graph. Then:
(i) Gis strong if and only ifGhas a closed spanning path.(ii) Gis unilateral if and only ifGhas a spanning path.(iii)Gis weak if and only ifGhas a spanning semipath.EXAMPLE 9.4 Consider the graphGin Fig. 9-1(a). It is weakly connected since the underlying nondirected
graph is connected. There is no path fromCto any other vertex, that is,Cis a sink, soGis not strongly connected.
However,P=(B,A,D,C)is a spanning path, soGis unilaterally connected.
Graphs with sources and sinks appear in many applications (such as flow diagrams and networks).Asufficient
condition for such vertices to exist follows.
Theorem 9.3: Suppose a finite directed graphGis cycle-free, that is, contains no (directed) cycles. ThenG
contains a source and a sink.
Proof:LetP=(v 0 ,v 1 ,...,vn)be a simple path of maximum length, which exists sinceGis finite. Then the
last vertexvnis a sink; otherwise an edge (vn,u) will either extendPor form a cycle ifu=vi, for somei.
Similarly, the first vertexv 0 is a source.
9.4Rooted Trees
Recall that a tree graph is a connected cycle-free graph, that is, a connected graph without any cycles.Arooted
tree Tis a tree graph with a designated vertexrcalled therootof the tree. Since there is a unique simple path
from the rootrto any other vertexvinT, this determines a direction to the edges ofT. ThusTmay be viewed
as a directed graph. We note that any tree may be made into a rooted tree by simply selecting one of the vertices
as the root.
Consider a rooted treeTwith rootr. The length of the path from the rootrto any vertexvis called thelevel
(ordepth)ofv, and the maximum vertex level is called thedepthof the tree. Those vertices with degree 1, other
than the rootr, are called theleavesofT, and a directed path from a vertex to a leaf is called abranch.
One usually draws a picture of a rooted treeTwith the root at the top of the tree. Figure 9-2(a) shows a rooted
treeT with rootrand 10 other vertices. The tree has five leaves,d,f, h, i, andj. Observe that:level(a)=1,
level(f )=2,level(j )=3. Furthermore, the depth of the tree is 3.
The fact that a rooted treeTgives a direction to the edges means that we can give a precedence relationship
between the vertices. Specifically, we will say that a vertexuprecedesa vertexvor thatvfollows uif there is