Discrete Mathematics for Computer Science

Directed Graphs 393

6.14.1 Basic Definitions

To understand the differences between directed and undirected graphs, we must supply

definitions of directed graphs and of their subgraphs and induced subgraphs.

Definition 1. A directed graph, or digraph, D = (V, E) consists of a finite, nonempty

set V, the elements of V are the vertices of D, and a finite set E of ordered pairs of distinct

elements of V, the elements of E are the directed edges of D. For an edge (a, b) E E, the

vertex a is the tail of the edge, and b is its head. Both a and b are incident to the directed

edge (a, b). The vertex a is adjacent to b, but b is not adjacent to a unless (b, a) E E. Two

directed edges, (a, b) and (c, d), are adjacent if b = c or d = a.

The direction of an edge in a drawing of the graph is normally indicated by attaching

an arrowhead to the head of the edge. For a vertex a in a directed graph, the indegree of

a, denoted indeg(a), is the number of edges with a as the head, and the outdegree of a,

denoted outdeg(a), is the number of edges with a as the tail. When we think of two objects

as being adjacent-say, a is adjacent to b-we feel that we can just as well say that b is

adjacent to a. For undirected graphs, that is indeed true. For directed graphs, however, the

word has a more restricted meaning.

Subgraphs and induced subgraphs of a directed graph are defined very similarly to the

way they were defined for undirected graphs.

Definition 2. Let D = (V, E) be a directed graph. A directed graph D 1 = (VI, El) is

a directed subgraph of D provided that V 1 C V and E 1 CS E and, for each e E E 1 that

both ends of e are in V 1 .An edge in E 1 will have the same head and tail as that edge when

considered as an edge of D. D 1 is an induced subgraph of D if Dt is a subgraph of D

such that E 1 consists of all the edges of D with both head and tail in V 1.

Figure 6.53 illustrates these notions in a directed graph.

• tail
  adjacent
  edges~-. he Iad


• Subgraph Induced Subgraph
  adjacent -- indegree 1
  vertices outdegree^2

Figure 6.53 Directed subgraph and directed induced subgraph.

With each directed graph is an associated undirected graph, called the underlying
graph, that is formed from the same vertices and edges but considers all the edges to be
undirected. The underlying graph contains just one edge joining a to b when the directed
graph contains both the edge (a, b) and the edge (b, a) for some pair of vertices a and b.
A directed graph is called bipartite if the underlying graph is bipartite.