Problems
GRAPH TERMINOLOGY
1. Let G be the directed graph in Fig. 21(a).
(a) Describe G formally. (d ) Find all cycles in G.
(b) Find all simple paths from X to Z. (e) Is G unilaterally connected? (c) Find all simple paths from Y to Z. ( f ) Is G strongly connected?
(a) The vertex set V has four vertices and the edge set E has 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 from X to Z, which are (X, Z), (X, W , Z), and (X, Y, W , Z). (c) There is only one simple path from Y to Z, which is (Y, W , Z).
(d) There is only one cycle in G, which is (Y, W , Z, Y ).
(e) G is unilaterally connected since (X, Y, W , Z) is a spanning path. (f) G is not strongly connected since there is no closed spanning path.
Fig. 21
2. Let G be the directed graph in Fig. 21(a).
(a) Find the indegree and outdegree of each vertex of G.
(b) Find the successor list of each vertex of G.
(c) Are there any sources or sinks?
(d) Find the subgraph H of G determined by the vertex set V = X, Y, Z.
(a) Count the number of edges ending and beginning at a vertex v to 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 vertex v to the successor list succ(u) of u for each edge (u, v) in G. This yields:
succ(X) = [Y, Z, W ], succ(Y ) = [W ], succ(Z) = [Y, W ], succ(W ) = [Z]