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

CHAP. 9] DIRECTED GRAPHS 205 Fig. 9-2 a (directed) path fromvtou. In particular, we say thatvimmediately follows uif(u,v)is an e ...

206 DIRECTED GRAPHS [CHAP. 9 Fig. 9-3 identical to the order obtained by moving down the leftmost branch of the tree, then the n ...

CHAP. 9] DIRECTED GRAPHS 207 Then the entries ofAwill be nonnegative integers. Conversely, everym×mmatrixAwith nonnegative integ ...

208 DIRECTED GRAPHS [CHAP. 9 Suppose now that there is a path from vertexvito vertexvjin a graphGwithmvertices. Then there must ...

CHAP. 9] DIRECTED GRAPHS 209 The transitive closureR of the relationRonVmay now be viewed as the set of ordered pairs(u,v)such t ...

210 DIRECTED GRAPHS [CHAP. 9 Fig. 9-6 Shortest-path Algorithm LetGbe a simple directed graph withmvertices,v 1 ,v 2 ,...,vm. Sup ...

CHAP. 9] DIRECTED GRAPHS 211 Fig. 9-7 paths which correspond to the lengths in the matrixQk.) The entries in the matrixQ 0 are t ...

212 DIRECTED GRAPHS [CHAP. 9 memory space will be wasted. Accordingly, whenGis sparse,Gis usually represented in memory by some ...

CHAP. 9] DIRECTED GRAPHS 213 Figure 9-10 shows how the graphGin Fig. 9-9(a) may appear in memory. Here the vertices ofGare maint ...

214 DIRECTED GRAPHS [CHAP. 9 During the execution of our algorithms, each vertex (node)NofGwill be in one of three states, calle ...

CHAP. 9] DIRECTED GRAPHS 215 EXAMPLE 9.10 Consider our test graphGin Fig. 9-11. Suppose we want to find and print all the vertic ...

216 DIRECTED GRAPHS [CHAP. 9 Fig. 9-14 Fig. 9-15 9.9Directed Cycle-Free Graphs, Topological Sort LetSbe a directed graph with th ...

CHAP. 9] DIRECTED GRAPHS 217 Fig. 9-16 A fundamental operation on a dagSis to process the vertices one after the other so that t ...

218 DIRECTED GRAPHS [CHAP. 9 Fig. 9-18 EXAMPLE 9.12 SupposeAlgorithm 9.4 is applied to the graphSin Fig. 9-16. We obtain the fol ...

CHAP. 9] DIRECTED GRAPHS 219 Pruning Algorithm This algorithm finds the shortest path between a vertexuand a vertexwin a weighte ...

220 DIRECTED GRAPHS [CHAP. 9 Fromy:The successive vertices ares, entered for the first time, andt. Thus: (1) Set(s)=(y)+k= 5 + ...

CHAP. 9] DIRECTED GRAPHS 221 SolvedProblems GRAPH TERMINOLOGY 9.1. LetGbe the directed graph in Fig. 9-21(a). (a) DescribeGforma ...

222 DIRECTED GRAPHS [CHAP. 9 (c) Xis a source no edge entersX, that is, indeg(X)=0. There are no sinks since every vertex is the ...

CHAP. 9] DIRECTED GRAPHS 223 (a) List the vertices while proceeding fromRdown the tree to the vertex. The number of vertices, ot ...

224 DIRECTED GRAPHS [CHAP. 9 (a) Find the adjacency matrixAof the graphGand the powersA^2 ,A^3 ,A^4. (b) Find the path matrixPof ...