Digraphs: Walks and Paths

A digraph (directed graph) is a type of graph to represent how things are connected together.
As with many other graphs, digraphs have nodes (or, vertices) and directed edges. That's what gives their name: their edges are directed.

One example is the World Wide Web itself, we can think of webpages as vertices, and the hyperlinks as edges.

A directed edge $e$ starts at what is called a tail vertex, and ends at the head vertex.
If we denote it as $e = \textlangle{u \rightarrow v} \textrangle$, then, $u$ is the tail vertex, and $v$ is the head vertex. We can represent this edge as an ordered pair as well, such as: $(u, \ v)$.

The set of vertices in a directed graph $G$, denoted as $V(G)$, is a binary relation where the domain and the codomain are the same set $V$.

The set of edges in $G$ are denoted as—you guessed it—$E(G)$.

So, we can write the set of vertices of the example graph above as $V = \{1, \ 2, \ 3, \ 4\}$, and the set of edges as $E = \{(1, \ 2), \ (1, \ 3), \ (3, \ 2), \ (3, \ 4), (4, \ 3)\}$.

There are some terms we need to be familiar with.

The in-degree of a vertex is the number of arrows coming into it:

If $G$ is a digraph, and $v \in V(G)$:

The out-degree of a vertex is the number of arrows coming out of it:

The total number of in-degrees and out-degrees will be the number of edges in the graph, $|E(G)|$:

A walk is a sequence of edges you follow. In the above diagram, for example, we can start at 1, go to 3, then go to 4, then go to 3 again. The length of a walk will be the number of edges that we go through (one less than the number of vertices), not the number of vertices we visit.
A path is a special type of walk where you don't visit the same vertex twice. So, if we go back to 3 after visiting 4, it won't be a path.

We can represent a walk $v$ as such:

where $\textlangle{v_i \rightarrow v_{i + 1}} \textrangle \in E(G)$ for $i \in [0, k)$.

In order for this walk to be a path, all $v_i$'s should be different, because if $i \neq j$ then $v_i \neq v_j$.

A walk that begins and ends at the same vertex is called a closed walk.
A cycle is a closed walk where vertices are different except for the beginning and end vertices. Cycles must have a positive length.

What about a single vertex?

If a digraph has only one vertex, its length is zero, as it is considered to begin and end at itself. It is a closed walk as well, but since its length is not positive, it is not a cycle.

When is a walk not a walk?

An example: $\textlangle{c \rightarrow b} \textrangle \ \textlangle{b \leftarrow a} \textrangle \ \textlangle{a \rightarrow d} \textrangle$.
This is not considered a walk because its edges are in a wrong direction.

Just like your daily walk, we can also have rests during these walks, too. For example, if a walk $f$ ends at vertex $v$, and a walk $r$ starts with this same vertex $v$, their merge (denoted as $\textbf{f} \widehat{ \ v \ } \textbf{r}$ ) is the walk starting with $f$, continuing with $r$.

Note that the term merge does not really imply concatenation because the vertex $v$ would appear twice in such case.

The length of a merge is exactly as you thought it would be: the sum of those two walks: $|\textbf{f} \widehat{ \ v \ } \textbf{r}| = |\textbf{f}| + |\textbf{r}|$.

We can represent a digraph using an adjacency matrix.
Simply, we put $1$ where there is an edge between two vertices, and $0$ otherwise.
Let $A_G$ define the adjacency matrix of a graph $G$:

Let's use the diagram example we have at the start of this section.
Remember that its set of edges is $E = \{(1, \ 2), \ (1, \ 3), \ (3, \ 2), \ (3, \ 4), (4, \ 3)\}$.
Its adjacency matrix will then look like this:

One of the questions we can ask of a digraph is whether there is a walk from one vertex to another — in other words, whether they are connected, or whether one is reachable from the other.

We can denote this walk relation as:

Also, a positive walk relation as:

• previous
• next