Most graph terminology applies equally well to digraphs,e.g., subgraph,
self-loop, bipartite, isomorphic, empty. The definitions below are special to
digraphs or take on a somewhat different meaning for digraphs. In context, where
it is clear that only digraphs are being discussed, “directedness” is often an
implicit attribute of an “edge”, “path”, and other terms.
Definitions:
A directed graph, or digraph, consists of:
• a
set V , whose elements
are called vertices,
• a
set E, whose elements
are called directed edges or arcs, and
• an
incidence
function that assigns to each edge a tail and a head.
The tail of an arc is the vertex it leaves, and the head is the vertex it enters.
A strict digraph has no self-loops or multi-arcs.
The underlying graph of a digraph is the graph obtained from the digraph by replacing every directed edge
by an undirected edge.
The out-degree of vertex v, denoted deg-v, is the number of arcs with tail at v.
The in-degree of vertex v, denoted deg+v,
is the number of arcs with head at v.
A digraph D
is transitive if whenever it
contains an arc from u to v and an arc from v to w, it also contains an arc from u
to w.
Facts:
1. Strict-digraph terminology: In a context focusing primarily on strict digraphs, there is often a
different terminological convention:
• “digraph” refers to a strict digraph;
• a
directed graph with multi-arcs is called a multidigraph;
• a
directed graph with self-loops is called a pseudodigraph;
• an
arc with tail u and head v is designated uv.
2. Alternative “path” terminology: There is an alternative convention in which a (directed)
“path” may use vertices and arcs more than once, but an “elementary
path” does not repeat arcs, and a “simple path” does not repeat vertices (and, hence,
does not repeat arcs either).
3. The incidence structure
of a digraph is frequently represented by an arc list, in which each arc is represented by an ordered pair uv, where u is its tail and v is its head. For each arc with tail u and head v, there is a separate entry, so that uv
occurs as often as the number of such arcs. A
list of the isolated vertices plus such an arc list completely specifies a
digraph.
4. Another common
specification of a digraph is the lists-of-neighbors
representation. For each vertex u, there is a corresponding row, which has as an entry the head of each arc
whose tail is u. Thus a vertex v occurs in that row as many times as there are
arcs from u to v.
5. The incidence matrix is
another common way to represent a digraph. Since all but one or two of the
entries in every column are zero, the incidence matrix is a highly inefficient
form of representation.
6. The adjacency matrix is
also a common way to specify a digraph in some contexts when there is no reason
to identify the arcs by name.
7. A digraph can be
represented by a 2×|E| incidence table in which the tail and head of each arc e
appear in column e. Direction on an arc can be indicated by a convention as to whether
tail or head appears in the first row, which requires swapping the two column
entries if the direction is changed. Alternatively, direction can be indicated
by marking one of the two entries in each column as the head, and then moving
the marker if the direction changes.
8. A row-sum in a directed
adjacency matrix equals the out-degree of the corresponding vertex. A
column-sum equals the in-degree.
9. In any digraph, the sum
of the in-degrees, the sum of the out-degrees, and the number of edges are all
equal to each other; i.e.,
.
Examples:
1. The following arc list, incidence
table, list-of-neighbors, and adjacency matrix all represent
the digraph G.

|
arc list: uv, vv, vw, xw, xw, ux, xu |
incidence table: e1 e2 e3 e4 e5 e6 e7 u v v x x u x v v w w w x u |
lists-of-neighbors:
; adjacency matrix:
.
2. Civil Engineering: A road network in
which at least some of the roads are oneway can be modeled by a digraph. The nodes are road junctures; each
two-way road is represented by a pair of arcs, one in each direction. Loops are
allowed, and they may represent “circles” that occur in housing developments
and in industrial parks. Similarly, multiarcs may
occur.
3. Operations Research: A large project consists of many smaller tasks with a precedence
relation – some tasks must be completed before certain others can begin.
The vertices represent tasks, and there is an arc from u to v if task u must be completed
before v can begin. For
instance, in the following figure it is necessary both that food is loaded and
the cabin is cleaned before passengers are loaded.

4. Sociology and Sociobiology: A business (or army, or society, or ant colony) has a hierarchical
dominance structure. The nodes are the employees (soldiers, citizens, ants)
and there is an arc from u to v if u dominates v. If the chain of command is unique, with a single leader, and if only
arcs representing immediate authority are included, then the result is a rooted
tree.
5. Computer Software Design: A large program
consists of many subprograms, some of which can invoke others. Let the nodes of
D be the
subprograms, and let there be an arc from u
to v if subprogram u can invoke subprogram v. Then the call graph D
encapsulates all possible ways control can flow
within the program. Directed cycles represent indirect recursion, and serve as
a warning to the designer to ensure against infinite loops. See the following
figure, where subprogram 2 can call itself indirectly.

6. Ecology:
A food
web is a strict digraph in which nodes represent
species and in which there is an arc from u
to v if species u eats species v. The following figure shows a small food web.
