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

228 DIRECTED GRAPHS [CHAP. 9

SupplementaryProblems

GRAPH TERMINOLOGY

9.18. Consider the graphGin Fig. 9-28(a).

(a) Find the indegree and outdegree of each vertex. (d) Find all cycles inG.

(b) Are there any sources or sinks? (e) Find all paths of length 3 or less fromv 1 tov 3.

(c) Find all simple paths fromv 1 tov 4 .(f)IsGunilaterally or strongly connected?

Fig. 9-28

9.19. Consider the graphGin Fig. 9-28(b).

(a) Are there any sources or sinks? (c) Find a non-simple path fromv 1 tov 4.

(b) Find all simple paths fromv 1 tov 4. (d) Find all cycles inGwhich includev 4.

9.20. Consider the graphGin Fig. 9-28(b).

(a) Find: succ(v 1 ), succ(v 3 ), succ(v 5 ), succ(v 7 ).

(b) Find the subgraphHofGgenerated by: (i) {v 1 ,v 3 ,v 5 ,v 6 }; (ii) {v 2 ,v 3 ,v 6 ,v 7 }.

9.21. Let G be the graph with vertex setV (G)={A, B, C, D, E}and edge set

E(G)={(A, D), (B, C), (C, E), (D, B), (D, D), (D, E), (E, A)}

(a) ExpressGby its adjacency table.

(b) DoesGhave any loops or parallel edges?

(c) Find all simple paths fromDtoE.

(d) Find all cycles inG.

(e) IsGunilaterally or strongly connected?

(f) Find the number of subgraphs ofGwith verticesC, D, E.

(g) Find the subgraphHofGgenerated byC, D, E.

9.22. Let G be the graph with vertex setV (G)={a, b, c, d, e}and the following successor lists:

succ(a)=[b, c], succ(b)=
, succ(c)=[d,e], succ(d)=[a, b, e], succ(e)=

(a) List the edges ofG. (b) IsGweakly, unilaterally, or strongly connected?

9.23. LetGbe the graph in Fig. 9-29(a).

(a) ExpressGby its adjacency table. (d) Find all cycles inG.

(b) DoesGhave any sources or sinks? (e) Find a spanning path ofG.

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