CHAPTER 9 Directed Graphs
9.1Introduction
Directed graphsare graphs in which the edges are one-way. Such graphs are frequently more useful in various
dynamic systems such as digital computers or flow systems. However, this added feature makes it more difficult
to determine certain properties of the graph. That is, processing such graphs may be similar to traveling in a city
with many one-way streets.
This chapter gives the basic definitions and properties of directed graphs. Many of the definitions will be
similar to those in the preceding chapter on (non-directed) graphs. However, for pedagogical reasons, this chapter
will be mainly independent from the preceding chapter.9.2Directed Graphs
Adirected graph Gordigraph(or simplygraph) consists of two things:(i) A setVwhose elements are calledvertices,nodes,orpoints.(ii) A setEoforderedpairs (u, v) of vertices calledarcsordirected edgesor simplyedges.We will writeG(V, E) when we want to emphasize the two parts ofG. We will also writeV (G)andE(G)to
denote, respectively, the set of vertices and the set of edges of a graphG. (If it is not explicitly stated, the context
usually determines whether or not a graphGis a directed graph.)
Supposee=(u, v)is a directed edge in a digraphG. Then the following terminology is used:(a) e beginsatuandendsatv.
(b) uis theoriginorinitial pointofe, andvis thedestinationorterminal pointofe.
(c) vis asuccessorofu.
(d) uisadjacent tov, andvisadjacent fromu.Ifu=v, theneis called aloop.
The set of all successors of a vertexuis important; it is denoted and formally defined bysucc(u)={v∈V|there exists an edge(u, v)∈E}It is called thesuccessor listoradjacency listofu.201Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.