Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 9] DIRECTED GRAPHS 221

SolvedProblems

GRAPH TERMINOLOGY

9.1. LetGbe the directed graph in Fig. 9-21(a).

(a) DescribeGformally. (d) Find all cycles inG.

(b) Find all simple paths fromXtoZ.(e)IsGunilaterally connected?

(c) Find all simple paths fromYtoZ.(f)IsGstrongly connected?

(a) The vertex setVhas four vertices and the edge setEhas seven (directed) edges as follows:

V={X, Y, Z, W} and E={(X,Y),(X,Z),(X,W),(Y,W),(Z,Y),(Z,W),(W,Z)}

(b) There are three simple paths fromXtoZ, which are(X, Z), (X, W, Z), and(X,Y,W,Z).

(c) There is only one simple path fromYtoZ, which is (Y, W, Z).

(d) There is only one cycle inG, which is(Y,W,Z,Y).

(e) Gis unilaterally connected since(X,Y,W,Z)is a spanning path.

(f) Gis not strongly connected since there is no closed spanning path.

Fig. 9-21

9.2. LetGbe the directed graph in Fig. 9-21(a).

(a) Find the indegree and outdegree of each vertex ofG.

(b) Find the successor list of each vertex ofG.

(c) Are there any sources or sinks?

(d) Find the subgraphHofGdetermined by the vertex setV′=X, Y, Z.

(a) Count the number of edges ending and beginning at a vertexvto obtain, respectively, indeg(v)and outdeg(v).

This yields the data:

indeg(X)= 0 , indeg(Y )= 2 , indeg(Z)= 2 , indeg(W )= 3

outdeg(X)= 3 , outdeg(Y )= 1 , outdeg(Z)= 2 , outdeg(W )= 1

(As expected, the sum of the indegrees and the sum of the outdegrees each equal 7, the number of edges.)

(b) Add vertexvto the successor list succ(u)ofufor each edge(u, v)inG. This yields:

succ(X)=[Y, Z, W], succ(Y )=[W], succ(Z)=[Y, W], succ(W )=[Z]