202 DIRECTED GRAPHS [CHAP. 9
Apictureof a directed graphGis a representation ofGin the plane. That is, each vertexuofGis represented
by a dot (or small circle), and each (directed) edgee=(u, v)is represented by an arrow or directed curve from
the initial pointuofeto the terminal pointv. One usually presents a digraphGby its picture rather than explicitly
listing its vertices and edges.
If the edges and/or vertices of a directed graphGare labeled with some type of data, thenGis called
alabeled directed graph.
A directed graph(V, E)is said to befiniteif its setVof vertices and its setEof edges are finite.
EXAMPLE 9.1
(a) Consider the directed graphGpictured in Fig. 9-1(a). It consists of four vertices,A,B,C,D, that is,
V (G)={A, B, C, D}and the seven following edges:E(G)={e 1 ,e 2 ,...,e 7 }={(A, D), (B, A), (B, A), (D, B), (B, C), (D, C), (B, B)}The edgese 2 ande 3 are said to beparallelsince they both begin atBand end atA. The edgee 7 is aloop
since it begins and ends atB.Fig. 9-1(b) Suppose three boys,A, B, C, are throwing a ball to each other such thatAalways throws the ball toB, but
BandCare just as likely to throw the ball toAas they are to each other. This dynamic system is pictured
in Fig. 9-1(b) where edges are labeled with the respective probabilities, that is,Athrows the ball toBwith
probability 1,Bthrows the ball toAandCeach with probability 1/2, andCthrows the ball toAandBeach
with probability 1/2.Subgraphs
LetG=G(V , E)be a directed graph, and letV′be a subset of the setVof vertices ofG. SupposeE′is
a subset ofEsuch that the endpoints of the edges inE′belong toV′. ThenH(V′,E′)is a directed graph, and
it is called asubgraphofG. In particular, ifE′contains all the edges inEwhose endpoints belong toV′, then
H(V′,E′)is called the subgraph ofGgeneratedordeterminedbyV′. For example, for the graphG=G(V , E)
in Fig. 9-1(a),H(V′,E′)is the subgraph ofGdetermine by the vertex setV′where
V′={B, C, D} and E′={
e 4 ,e 5 ,e 6 ,e 7}
={(D, B),(B, C),(D, C),(B, B)}9.3Basic Definitions
This section discusses the questions of degrees of vertices, paths, and connectivity in a directed
graph.