Directed Graphs and Arc Incidence

Directed Edges Record Direction

Some relationships are naturally one-way: a web page links to another page, a road permits travel in one direction, or one task must precede another. An undirected edge records only that two vertices are connected. A directed edge also records which endpoint the connection starts from and which it points to. Reading that distinction correctly is the first step in working with directed graphs.

Throughout this tutorial, graphs are finite. We use loopless simple directed graphs: there are no arcs from a vertex to itself, and an ordered pair of vertices occurs at most once as an arc. Both directions between a pair of distinct vertices are allowed. Thus \(u\to v\) and \(v\to u\) are different arcs, and they may both be present.

Definition: A directed graph, or digraph, is \(D=(V,A)\), where \(V\) is a vertex set and \(A\) is a set of ordered pairs of distinct vertices. An element \((u,v)\in A\) is an arc, written \(u\to v\). Its tail is \(u\), where the arc starts, and its head is \(v\), where it ends.

Order matters in an ordered pair: \((u,v)\) and \((v,u)\) are unequal when \(u\ne v\). The arc \(u\to v\) therefore does not imply that \(v\to u\) is an arc. An edge list for a digraph must preserve this order; writing only \(uv\) can conceal which direction is intended.

Adjacency and Incidence in a Digraph

Definition: Vertices \(u\) and \(v\) are adjacent in the directed sense from \(u\) to \(v\) when \(u\to v\in A\). The arc \(u\to v\) is incident with both \(u\) and \(v\): it leaves \(u\), its tail, and enters \(v\), its head. When direction is ignored, the endpoints of the arc are the unordered pair \(\{u,v\}\).

Some contexts use “adjacent” without specifying a direction. To avoid ambiguity here, \(u\) is adjacent to \(v\) in the directed sense exactly when \(u\to v\) is present. If either \(u\to v\) or \(v\to u\) is present, the vertices are adjacent when direction is ignored. These are different questions: adjacency in the directed sense tests an ordered pair, while incidence asks which vertices are endpoints of a particular arc.

For a loopless digraph, every arc has two distinct endpoints: one tail and one head. A vertex can be incident with several arcs, and it can occur as a tail on some arcs and a head on others. For now, we record those roles arc by arc rather than summing them into vertex degrees.

Worked Example: Reading an Edge List

Let \(D=(V,A)\), where \(V=\{a,b,c,d\}\) and \(A=\{a\to b,\ b\to c,\ c\to a,\ c\to d\}\). Identify each arc’s tail, head, and incident vertices, then test several directed-adjacency claims.

Read each arrow from left to right. For \(a\to b\), the tail is \(a\), the head is \(b\), and the incident vertices are \(a,b\). For \(b\to c\), these are \(b,c\). For \(c\to a\), they are \(c,a\). For \(c\to d\), they are \(c,d\).

The directed adjacencies are exactly \(a\) to \(b\), \(b\) to \(c\), \(c\) to \(a\), and \(c\) to \(d\), because these and only these ordered pairs appear in \(A\). In particular, \(a\) is adjacent to \(b\) in the directed sense, but \(b\) is not adjacent to \(a\): \(b\to a\notin A\). The vertices \(a\) and \(c\) are adjacent when direction is ignored, since \(c\to a\in A\), even though \(a\to c\notin A\).

Check: Each of the four listed arcs has two distinct endpoints in \(V\), and the list contains no repeated ordered pair. The arc \(c\to a\) accounts for the incidence between \(c\) and \(a\); it does not create the oppositely directed arc \(a\to c\).

An adjacency table makes the direction explicit. List the possible starting vertices down the rows and the possible ending vertices across the columns. Put a \(1\) in row \(u\), column \(v\) exactly when \(u\to v\) is an arc; otherwise put \(0\). This table is the adjacency matrix when its entries are arranged as a matrix.

Definition: If the vertices are listed as \(v_1,\dots,v_n\), the adjacency matrix \(\mathbf{A}(D)\) has entry \(1\) in row \(i\), column \(j\) if \(v_i\to v_j\in A\), and entry \(0\) otherwise. Rows record tails; columns record heads.

Because loops are excluded, every diagonal entry is \(0\). The matrix need not be symmetric: symmetry would require every arc to be accompanied by its reverse.

Proposition: For a loopless simple digraph, \(\mathbf{A}(D)\) is symmetric if and only if, for every pair of distinct vertices \(u,v\), the arc \(u\to v\) is present exactly when \(v\to u\) is present.

Proof. Write \(a_{ij}\) for the entry in row \(i\), column \(j\), corresponding to vertices \(v_i,v_j\). By definition, \(a_{ij}=1\) exactly when \(v_i\to v_j\) is an arc, and \(a_{ji}=1\) exactly when \(v_j\to v_i\) is an arc. If the matrix is symmetric, then \(a_{ij}=a_{ji}\) for every \(i,j\), so each of these two arcs is present exactly when the other is present. Conversely, if that condition holds for every distinct pair, then \(a_{ij}=a_{ji}\) for all \(i\ne j\). On the diagonal, both entries are \(0\), since loops are excluded. Hence all corresponding entries agree and the matrix is symmetric. \(\square\)

Incidence Tables and Matrices

An incidence list answers which arcs touch a vertex. To keep the direction visible, record whether the vertex is the tail or head. A directed incidence matrix is another way to make the same distinction. Fix an order for the vertices and an order for the arcs; use one column for each arc. Put \(-1\) at the tail of an arc, \(+1\) at its head, and \(0\) at every other vertex in that column.

Definition: The directed incidence matrix of a loopless digraph has one row for each vertex and one column for each arc. In the column for \(u\to v\), the entry in row \(u\) is \(-1\), the entry in row \(v\) is \(+1\), and all other entries are \(0\).

Proposition: In the directed incidence matrix of a loopless digraph, each arc column has exactly one \(-1\) and one \(+1\). The row with \(-1\) identifies the tail, and the row with \(+1\) identifies the head.

Proof. Consider any arc \(u\to v\). The graph is loopless, so \(u\ne v\). By the definition of the matrix, its column has entry \(-1\) in row \(u\), entry \(+1\) in row \(v\), and \(0\) in every other row. These are exactly one entry of each sign, at distinct rows. The rule assigning signs puts \(-1\) at the tail and \(+1\) at the head, so the two rows recover the direction. \(\square\)

Worked Example: Adjacency and Incidence Matrices

Let \(D=(V,A)\), where \(V=\{p,q,r,s\}\) and \(A=\{p\to q,\ p\to r,\ r\to q,\ s\to r,\ q\to s\}\). Use vertex order \(p,q,r,s\) and arc order \(p\to q,\ p\to r,\ r\to q,\ s\to r,\ q\to s\).

For the adjacency matrix, the row for \(p\) has \(1\) in the columns for \(q\) and \(r\), since \(p\to q\) and \(p\to r\) are listed. Its other entries are \(0\). The row for \(q\) has \(1\) in the column for \(s\), since \(q\to s\) is listed. The row for \(r\) has \(1\) in the column for \(q\), and the row for \(s\) has \(1\) in the column for \(r\). Thus

\mathbf{A}(D)= \begin{pmatrix} 0&1&1&0\\ 0&0&0&1\\ 0&1&0&0\\ 0&0&1&0 \end{pmatrix}.

For the incidence matrix, the first arc \(p\to q\) gives column \((-1,1,0,0)^{T}\), and \(p\to r\) gives \((-1,0,1,0)^{T}\). The arc \(r\to q\) gives \((0,1,-1,0)^{T}\); \(s\to r\) gives \((0,0,1,-1)^{T}\); and \(q\to s\) gives \((0,-1,0,1)^{T}\). Placing these columns in the stated order gives

\mathbf{B}(D)= \begin{pmatrix} -1&-1&0&0&0\\ 1&0&1&0&-1\\ 0&1&-1&1&0\\ 0&0&0&-1&1 \end{pmatrix}.

Check: In the adjacency matrix, row \(p\) has \(1\)s in the \(q\) and \(r\) columns, matching the two arcs with tail \(p\). In the incidence matrix, the column for \(s\to r\) has \(-1\) in row \(s\) and \(+1\) in row \(r\), so it records tail \(s\) and head \(r\). Each of the five columns has one \(-1\) and one \(+1\), as required.

What Is Lost When Direction Is Forgotten?

From a digraph \(D\), one can form an undirected graph by replacing each arc \(u\to v\) with the unordered pair \(\{u,v\}\), and keeping just one undirected edge for a pair even if both directions occur. This resulting graph records which pairs of vertices are connected by at least one arc; it does not record the direction or whether both directions were present.

Proposition: If a digraph has at least one arc, its undirected graph obtained by forgetting directions does not, in general, determine the digraph.

Proof. Consider a vertex set containing distinct vertices \(u,v\) and the undirected graph with the single edge \(\{u,v\}\). It can come from the digraph with the one arc \(u\to v\), or from the digraph with the one arc \(v\to u\). The resulting undirected graph is \(\{u,v\}\) in both cases, but the directed arc sets differ because \((u,v)\ne(v,u)\). Therefore forgetting directions can give the same undirected graph for distinct digraphs, so it cannot always recover the original digraph. \(\square\)

This is why an edge list for a directed graph should use arrows or ordered pairs. An incidence statement that names only the two endpoints is not enough to decide which endpoint is the tail.

Worked Example: Reciprocal Arcs Are Separate

Let \(D=(V,A)\), where \(V=\{1,2,3\}\) and \(A=\{1\to2,\ 2\to1,\ 2\to3\}\). List the directed adjacencies and incidences, and describe the undirected graph obtained by forgetting direction.

The ordered pairs in \(A\) are \((1,2),(2,1),(2,3)\). Thus \(1\) is adjacent to \(2\), and \(2\) is also adjacent to \(1\); both claims hold because both arcs are listed. Vertex \(2\) is the head of \(1\to2\) and the tail of \(2\to1\). For \(2\to3\), vertex \(2\) is the tail and \(3\) is the head.

Forgetting direction turns \(1\to2\) and \(2\to1\) into the same undirected edge \(\{1,2\}\). It turns \(2\to3\) into \(\{2,3\}\). The resulting undirected graph therefore has vertex set \(\{1,2,3\}\) and edge set \(\{\{1,2\},\{2,3\}\}\).

Check: The directed list contains three arcs, while the undirected edge set contains two edges: the two opposite arcs between \(1\) and \(2\) produce one undirected edge, and \(2\to3\) produces the other. The undirected graph alone cannot tell whether one or both directions between \(1\) and \(2\) were present.

Common Pitfalls

Reversing an arc accidentally. Suppose \(A=\{x\to y\}\). The wrong calculation “\(y\) is adjacent to \(x\), because \(x\) and \(y\) are joined” treats a directed arc as an undirected edge. The correction is to test the ordered pair: \(y\) is adjacent to \(x\) in the directed sense only if \(y\to x\in A\). Here \(y\to x\notin A\), so that directed adjacency does not hold. The vertices are incident with the listed arc, and adjacent if direction is ignored, but neither fact reverses the arrow.

Confusing a matrix row with a column. In the adjacency matrix convention used here, the row is the tail and the column is the head. In the incidence matrix, by contrast, each column corresponds to an arc, and its two nonzero entries identify that arc’s tail and head. State the convention before reading either table.

Counting a reciprocal pair as one arc. The arcs \(u\to v\) and \(v\to u\) are distinct ordered pairs. They may produce just one edge after directions are forgotten, but they remain two arcs in the directed graph.

Check Your Understanding

Use the definitions and conventions in this tutorial to answer the following questions.

Let \(V=\{a,b,c\}\) and \(A=\{a\to b,\ c\to b\}\). Which vertices are adjacent to \(b\) in the directed sense, and which arcs are incident with \(b\)?
For \(V=\{1,2,3\}\) and \(A=\{1\to2,\ 2\to1,\ 3\to2\}\), write the \(3\) by \(3\) adjacency matrix in vertex order \(1,2,3\).
In the digraph of Question 2, what undirected edges result from forgetting directions? Which directed information is lost?
Write the directed incidence column for the arc \(c\to a\) using vertex order \(a,b,c\).
State and prove the condition under which the adjacency matrix of a loopless simple digraph is symmetric.