Directed Graph
1- INTRODUCTION
Directed graphs are 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.
2- DIRECTED GRAPHS
A directed graph G or digraph (or simply graph) consists of two things:
(i) A set V whose elements are called vertices, nodes, or points.
(ii) A set E of ordered pairs (u, v) of vertices called arcs or directed edges or simply edges.
We will write G(V, E) when we want to emphasize the two parts of G. We will also write V (G) and E(G) to
denote, respectively, the set of vertices and the set of edges of a graph G. (If it is not explicitly stated, the context
usually determines whether or not a graph G is a directed graph.)
Suppose e = (u, v) is a directed edge in a digraph G. Then the following terminology is used:
(a) e begins at u and ends at v.
(b) u is the origin or initial point of e, and v is the destination or terminal point of e.
(c) v is a successor of u.
(d) u is adjacent to v, and v is adjacent from u.
If u = v, then e is called a loop.
The set of all successors of a vertex u is important; it is denoted and formally defined by
succ(u) = {v ? V | there exists an edge (u, v) ? E}
It is called the successor list or adjacency list of u.
Apicture of a directed graphGis a representation ofGin the plane. That is, each vertex u ofGis represented
by a dot (or small circle), and each (directed) edge e = (u, v) is represented by an arrow or directed curve from
the initial point u of e to the terminal point v. One usually presents a digraphGby its picture rather than explicitly
listing its vertices and edges.
If the edges and/or vertices of a directed graph G are labeled with some type of data, then G is called
a labeled directed graph.
A directed graph (V, E) is said to be finite if its set V of vertices and its set E of edges are finite.
EXAMPLE 9.1
(a) Consider the directed graph G pictured 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) = {e1, e2, . . . , e7} = {(A,D), (B, A), (B, A), (D,B), (B,C), (D,C), (B, B)}
The edges e2 and e3 are said to be parallel since they both begin at B and end at A. The edge e7 is a loop
since it begins and ends at B.
Suppose three boys, A,B,C, are throwing a ball to each other such that A always throws the ball to B, but
B and C are just as likely to throw the ball to A as 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, A throws the ball to B with
probability 1, B throws the ball to A and C each with probability 1/2, and C throws the ball to A and B each
with probability 1/2.
Subgraphs
Let G = G(V,E) be a directed graph, and let V be a subset of the set V of vertices of G. Suppose E
is
a subset of E such that the endpoints of the edges in E
belong to V
. Then H(V
,E
) is a directed graph, and
it is called a subgraph of G. In particular, if E
contains all the edges in E whose endpoints belong to V
, then
H(V
,E
) is called the subgraph of G generated or determined by V
. For example, for the graph G = G(V,E)
in Fig. 9-1(a), H(V
,E
) is the subgraph of G determine by the vertex set V
where
V
= {B, C, D} and E
=
(
e4, e5, e6, e7
)
= {(D, B), (B, C), (D, C), (B, B)}
3- BASIC DEFINITIONS
This section discusses the questions of degrees of vertices, paths, and connectivity in a directed
graph.
Degrees
Suppose G is a directed graph. The outdegree of a vertex v of G, written outdeg(v), is the number of edges
beginning at v, and the indegree of v, written indeg(v), is the number of edges ending at v. Since each edge begins
and ends at a vertex we immediately obtain the following theorem.
Theorem 9.1: The sum of the outdegrees of the vertices of a digraph G equals the sum of the indegrees of the
vertices, which equals the number of edges in G.
A vertex v with zero indegree is called a source, and a vertex v with zero outdegree is called a sink.
EXAMPLE 9.2 Consider the graph G in Fig. 9-1(a).We have:
outdeg (A) = 1, outdeg (B)= 4, outdeg (C) = 0, outdeg (D)= 2,
indeg (A) = 2, indeg (B)= 2, indeg (C) = 2, indeg (D) = 1.
As expected, the sum of the outdegrees equals the sum of the indegrees, which equals the number 7 of edges.
The vertex C is a sink since no edge begins at C. The graph has no sources.
Paths
Let G be a directed graph. The concepts of path, simple path, trail, and cycle carry over from nondirected
graphs to the directed graph G except that the directions of the edges must agree with the direction of the path.
Specifically:
(i) A (directed) path P in G is an alternating sequence of vertices and directed edges, say,
P =
_
v0, e1, v1, e2, v2, . . . , en, vn
_
such that each edge ei begins at vi?1 and ends at vi . If there is no ambiguity, we denote P by its sequence
of vertices or its sequence of edges.
(ii) The length of the path P is n, its number of edges.
(iii) A simple path is a path with distinct vertices. A trail is a path with distinct edges.
(iv) A closed path has the same first and last vertices.
(v) A spanning path contains all the vertices of G.
(vi) A cycle (or circuit) is a closed path with distinct vertices (except the first and last).
(vii) Asemipath is the same as a path except the edge ei may begin at vi?1 or vi and end at the other vertex.
Semitrails and semisimple paths are analogously defined.
Avertex v is reachable from a vertex u if there is a path from u to v. If v is reachable from u, then (by eliminating
redundant edges) there must be a simple path from u to v.
EXAMPLE 9.3 Consider the graph G in Fig. 9-1(a).
(a) The sequence P1 = (D,C,B,A) is a semipath but not a path since (C,B) is not an edge; that is, the direction
of e5 = (C,B) does not agree with the direction of P1.
(b) The sequence P2 = (D,B,A) is a path from D to A since (D, B) and (B, A) are edges. Thus A is reachable
from D. Connectivity
There are three types of connectivity in a directed graph G:
(i) G is strongly connected or strong if, for any pair of vertices u and v in G, there is a path from u to v
and a path from v to u, that is, each is reachable from the other.
(ii) G is unilaterally connected or unilateral if, for any pair of vertices u and v in G, there is a path from
u to v or a path from v to u, that is, one of them is reachable from the other.
(iii) G is weakly connected or weak if there is a semipath between any pair of vertices u and v in G.
Let G be the (nondirected) graph obtained from a directed graph G by allowing all edges in G to be nondirected.
Clearly, G is weakly connected if and only if the graph G
is connected.
Observe that strongly connected implies unilaterally connected which implies weakly connected. We say
that G is strictly unilateral if it is unilateral but not strong, and we say that G is strictly weak if it is weak but not
unilateral.
Connectivity can be characterized in terms of spanning paths as follows:
Theorem 9.2: Let G be a finite directed graph. Then:
(i) G is strong if and only if G has a closed spanning path.
(ii) G is unilateral if and only if G has a spanning path.
(iii) G is weak if and only if G has a spanning semipath.
EXAMPLE 9.4 Consider the graph G in Fig. 9-1(a). It is weakly connected since the underlying nondirected
graph is connected. There is no path from C to any other vertex, that is, C is a sink, soGis not strongly connected.
However, P = (B,A,D,C) is a spanning path, so G is unilaterally connected.
Graphs with sources and sinks appear in many applications (such as flow diagrams and networks).Asufficient
condition for such vertices to exist follows.
Theorem 9.3: Suppose a finite directed graph G is cycle-free, that is, contains no (directed) cycles. Then G
contains a source and a sink.
Proof: Let P = (v0, v1, . . . , vn) be a simple path of maximum length, which exists since G is finite. Then the
last vertex vn is a sink; otherwise an edge (vn, u) will either extend P or form a cycle if u = vi , for some i.
Similarly, the first vertex v0 is a source.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .