# Chapter 16. Directed Graphs

# Chapter 16. Directed Graphs

A directed graph is a graph in which each edge has a direction. Instead of merely saying that two vertices are adjacent, a directed graph records an ordered relation from one vertex to another.

Directed graphs are also called digraphs. Their directed edges are often called arcs. Formally, a directed graph is an ordered pair

$$
D = (V, A),
$$

where \(V\) is a set of vertices and \(A\) is a set of ordered pairs of vertices. An ordered pair \((u,v)\) represents an arc from \(u\) to \(v\). The first vertex is the tail, source, or initial vertex of the arc. The second vertex is the head, target, or terminal vertex of the arc. This ordered-pair definition is the standard distinction between directed and undirected graphs, where undirected edges are unordered pairs.

## 16.1 From Undirected Graphs to Directed Graphs

In an undirected graph, the edge \(\{u,v\}\) has no direction. It connects \(u\) and \(v\) symmetrically. If \(u\) is adjacent to \(v\), then \(v\) is adjacent to \(u\).

In a directed graph, the arc \((u,v)\) has direction. It goes from \(u\) to \(v\). The existence of \((u,v)\) does not imply the existence of \((v,u)\).

Thus the two arcs

$$
(u,v)
\qquad \text{and} \qquad
(v,u)
$$

are distinct.

This distinction is essential. Many relations are asymmetric. A web page may link to another page without receiving a link back. A person may follow another person on a social network without being followed in return. A task may depend on another task without the reverse dependence being true. A directed graph records such one-way structure.

## 16.2 Arcs

Let \(D = (V,A)\) be a directed graph. If \((u,v) \in A\), then there is an arc from \(u\) to \(v\).

The vertex \(u\) is called the tail of the arc. The vertex \(v\) is called the head of the arc. We also say that the arc leaves \(u\) and enters \(v\).

$$
u \longrightarrow v
$$

The vertex \(v\) is an out-neighbor or successor of \(u\). The vertex \(u\) is an in-neighbor or predecessor of \(v\). These terms are common in directed graph terminology and follow directly from the orientation of an arc.

For a vertex \(v\), we define its out-neighborhood by

$$
N^+(v) = \{u \in V : (v,u) \in A\}.
$$

This is the set of vertices reached by arcs leaving \(v\).

We define its in-neighborhood by

$$
N^-(v) = \{u \in V : (u,v) \in A\}.
$$

This is the set of vertices that have arcs entering \(v\).

## 16.3 In-Degree and Out-Degree

In an undirected graph, the degree of a vertex counts incident edges. In a directed graph, incident arcs must be counted with direction.

The out-degree of a vertex \(v\), denoted \(\deg^+(v)\), is the number of arcs leaving \(v\):

$$
\deg^+(v) = |N^+(v)|.
$$

The in-degree of \(v\), denoted \(\deg^-(v)\), is the number of arcs entering \(v\):

$$
\deg^-(v) = |N^-(v)|.
$$

A vertex with in-degree zero is called a source. A vertex with out-degree zero is called a sink. In the usual terminology, a source has no incoming arcs, while a sink has no outgoing arcs.

For example, suppose

$$
V = \{a,b,c,d\}
$$

and

$$
A = \{(a,b), (a,c), (b,c), (c,a), (c,d)\}.
$$

Then

$$
N^+(a) = \{b,c\},
\qquad
N^-(a) = \{c\}.
$$

Therefore,

$$
\deg^+(a) = 2,
\qquad
\deg^-(a) = 1.
$$

The total out-degree over all vertices equals the total in-degree over all vertices:

$$
\sum_{v \in V} \deg^+(v) =
\sum_{v \in V} \deg^-(v) =
|A|.
$$

Each arc contributes one to the out-degree of its tail and one to the in-degree of its head.

## 16.4 Simple Directed Graphs, Loops, and Multiple Arcs

A simple directed graph usually has no loops and no repeated arcs. A loop is an arc of the form

$$
(v,v).
$$

It begins and ends at the same vertex.

A directed multigraph allows multiple arcs with the same tail and head. For example, it may contain several copies of \((u,v)\). Such graphs are useful when arcs represent distinct objects: several flights from one city to another, several communication channels, or several transitions between two states.

A directed graph with loops allows arcs from a vertex to itself. Whether loops are allowed depends on the convention of the text or application. For this book, unless otherwise stated, a directed graph means a finite directed graph without repeated arcs. Loops will be allowed only when explicitly mentioned.

## 16.5 Underlying Undirected Graph

Every directed graph has an underlying undirected graph. It is obtained by replacing each arc \((u,v)\) with the undirected edge \(\{u,v\}\), ignoring direction.

If both \((u,v)\) and \((v,u)\) occur, they still correspond to the same undirected edge \(\{u,v\}\) in the underlying graph, unless multiplicities are being kept.

The underlying graph is useful when we want to study ordinary connectivity while temporarily ignoring direction. For example, a directed graph may be weakly connected because its underlying undirected graph is connected, even though not every vertex can reach every other vertex by directed paths.

## 16.6 Orientation of an Undirected Graph

An orientation of an undirected graph is obtained by assigning a direction to each edge.

If \(G = (V,E)\) is an undirected graph, then an orientation of \(G\) replaces each edge \(\{u,v\}\) by exactly one of the arcs

$$
(u,v)
\qquad \text{or} \qquad
(v,u).
$$

The resulting directed graph is called an oriented graph.

An oriented graph has no pair of opposite arcs between the same two vertices. That is, it cannot contain both \((u,v)\) and \((v,u)\). This distinguishes an oriented graph from a general directed graph, where both directions may occur.

Orientations are useful when an undirected relationship receives direction from a rule. A road network may assign directions to streets. A tournament may orient each edge from the winner to the loser. A dependency graph may orient an edge from a prerequisite to a dependent task.

## 16.7 Directed Walks, Paths, and Cycles

A directed walk is a sequence of vertices

$$
v_0, v_1, \ldots, v_k
$$

such that

$$
(v_{i-1}, v_i) \in A
$$

for each \(i = 1,2,\ldots,k\).

The direction of every arc must be followed. It is not enough that the vertices are adjacent in the underlying graph.

A directed path is a directed walk with no repeated vertices. A directed cycle is a directed path together with an arc from the last vertex back to the first.

Thus a directed cycle has the form

$$
v_0 \to v_1 \to \cdots \to v_{k-1} \to v_0.
$$

Directed cycles are important because they represent circular dependence. If \(a\) depends on \(b\), \(b\) depends on \(c\), and \(c\) depends on \(a\), then no object in the cycle can be completed before the others.

## 16.8 Reachability

A vertex \(v\) is reachable from a vertex \(u\) if there exists a directed path from \(u\) to \(v\).

Reachability is directional. It may be true that \(v\) is reachable from \(u\), while \(u\) is not reachable from \(v\).

For example, if

$$
a \to b \to c,
$$

then \(c\) is reachable from \(a\), but \(a\) is not reachable from \(c\).

Reachability is one of the central relations in directed graph theory. It appears in program analysis, dependency resolution, network routing, database queries, automata theory, and scheduling.

## 16.9 Strong and Weak Connectivity

Directed graphs have more than one useful notion of connectivity.

A directed graph is weakly connected if its underlying undirected graph is connected. Direction is ignored.

A directed graph is strongly connected if for every pair of vertices \(u,v \in V\), there is a directed path from \(u\) to \(v\) and also a directed path from \(v\) to \(u\). Standard graph theory distinguishes weak connectivity from strong connectivity in exactly this way.

Strong connectivity is stricter. It says that every vertex can reach every other vertex while respecting directions.

For example, the directed cycle

$$
a \to b \to c \to a
$$

is strongly connected. From any vertex, one can follow directions around the cycle to reach any other vertex.

The directed path

$$
a \to b \to c
$$

is weakly connected but not strongly connected. Its underlying undirected graph is connected, but there is no directed path from \(c\) back to \(a\).

## 16.10 Adjacency Matrix of a Directed Graph

Let \(D = (V,A)\) be a directed graph with vertices

$$
V = \{v_1, v_2, \ldots, v_n\}.
$$

The adjacency matrix of \(D\) is the \(n \times n\) matrix \(M\) defined by

$$
M_{ij} =
\begin{cases}
1, & \text{if } (v_i,v_j) \in A, \\
0, & \text{otherwise.}
\end{cases}
$$

Rows represent tails. Columns represent heads.

For example, if

$$
V = \{a,b,c\}
$$

and

$$
A = \{(a,b), (b,c), (c,a)\},
$$

with vertex order \(a,b,c\), then

$$
M =
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0
\end{bmatrix}.
$$

The entry in row \(a\), column \(b\) is \(1\), because there is an arc from \(a\) to \(b\). The matrix need not be symmetric. Symmetry would mean that whenever \((u,v)\) is present, \((v,u)\) is also present.

For directed multigraphs, the entry \(M_{ij}\) may count the number of arcs from \(v_i\) to \(v_j\). This convention is common for multidigraphs and graphs with loops.

## 16.11 Incidence Matrix of a Directed Graph

Another useful representation is the incidence matrix.

Let \(D = (V,A)\), where

$$
V = \{v_1,\ldots,v_n\}
$$

and

$$
A = \{a_1,\ldots,a_m\}.
$$

The incidence matrix is an \(n \times m\) matrix \(B\). Each column corresponds to an arc.

For an arc \(a_k = (u,v)\), one common convention is

$$
B_{ik} =
\begin{cases}
-1, & \text{if } v_i = u, \\
1, & \text{if } v_i = v, \\
0, & \text{otherwise.}
\end{cases}
$$

Thus the tail receives \(-1\), and the head receives \(1\).

This matrix form is useful in flow problems, electrical networks, conservation laws, and optimization. The signs encode direction.

## 16.12 Directed Acyclic Graphs

A directed acyclic graph, or DAG, is a directed graph with no directed cycles.

DAGs are fundamental in scheduling and dependency analysis. If an arc \(u \to v\) means that \(u\) must occur before \(v\), then a directed cycle would mean that some task must occur before itself through a chain of dependencies. This is impossible.

For example,

$$
a \to b,
\qquad
a \to c,
\qquad
b \to d,
\qquad
c \to d
$$

is a DAG. It says that \(a\) must precede both \(b\) and \(c\), and both \(b\) and \(c\) must precede \(d\).

DAGs admit topological orderings, which will be studied in a later chapter. A topological ordering lists the vertices so that every arc goes from an earlier vertex to a later vertex.

## 16.13 Tournaments

A tournament is an orientation of a complete graph.

For every pair of distinct vertices \(u\) and \(v\), exactly one of the arcs

$$
(u,v)
\qquad \text{or} \qquad
(v,u)
$$

is present.

Tournaments model pairwise competitions. If \(u \to v\), then \(u\) defeated \(v\). Since every pair competes, exactly one directed edge is assigned between every two vertices.

Tournaments provide a simple but rich class of directed graphs. They contain many nontrivial questions about ranking, dominance, cycles, and transitive subtournaments.

## 16.14 Directed Graphs as Relations

A directed graph can be viewed as a binary relation on a set.

Let \(V\) be a set. A binary relation \(R\) on \(V\) is a subset of

$$
V \times V.
$$

A directed graph \(D = (V,A)\) has exactly this form, since

$$
A \subseteq V \times V.
$$

Thus directed graphs provide a visual and combinatorial language for relations.

If \((u,v) \in A\), then \(u\) is related to \(v\). Properties of relations correspond to properties of directed graphs:

| Relation property | Graph interpretation |
|---|---|
| Reflexive | Every vertex has a loop |
| Symmetric | Every arc has the reverse arc |
| Antisymmetric | No two distinct vertices have arcs both ways |
| Transitive | If \(u \to v\) and \(v \to w\), then \(u \to w\) |
| Acyclic | No directed cycle |

This connection explains why directed graphs appear throughout discrete mathematics, order theory, logic, and computer science.

## 16.15 Applications

Directed graphs model systems with one-way relations.

| Application | Vertices | Arcs |
|---|---|---|
| Web graph | Web pages | Links |
| Social network | Accounts | Follows |
| Task scheduling | Tasks | Dependencies |
| Compiler analysis | Program blocks | Control flow |
| Automata | States | Transitions |
| Transportation | Locations | One-way routes |
| Knowledge graph | Entities | Directed relations |
| Version control | Commits | Parent relations |
| Build systems | Files or targets | Dependency edges |

In each case, direction carries meaning. Ignoring direction may destroy the structure of the problem.

For example, in a dependency graph, an arc

$$
u \to v
$$

may mean that \(v\) depends on \(u\). Reversing this arc changes the meaning completely.

## 16.16 Summary

A directed graph is a graph whose edges have direction. It is written as

$$
D = (V,A),
$$

where \(V\) is a set of vertices and \(A\) is a set of ordered pairs of vertices.

The main objects are arcs, tails, heads, in-neighbors, out-neighbors, in-degree, out-degree, directed paths, reachability, and directed cycles. Directed graphs support richer connectivity notions than undirected graphs, especially weak and strong connectivity.

Directed graphs are the natural language of asymmetric structure. They describe links, dependencies, flows, transitions, precedence, control, and reachability. Subsequent chapters develop these ideas through directed paths, strong components, acyclic graphs, topological ordering, weighted digraphs, and directed graph algorithms.