Definition:Path (Graph Theory)/Digraph
This page is about Path in the context of Graph Theory. For other uses, see Path.
Definition
Let $D = \struct {V, E}$ be a digraph.
A path $P$ in $D$ is:
- a sequence of vertices $v_1, v_2, \ldots, v_n$ in $V$ and a sequence of arcs $e_1, e_2, \ldots{}, e_{n - 1}$ in $E$ such that:
- $P$ begins with $v_1$ and ends with $v_n$
- in which each arc $e_j$ is incident from $v_j$ and incident to $v_{j + 1}$
- all arcs are distinct
- all vertices (except perhaps the first and last ones) are distinct.
A path between two vertices $u$ and $v$ is called a path from $u$ to $v$.
Predecessor
Let $D = \struct {V, E}$ be a digraph.
Let $P$ be a path in $D$ such that the vertices of $P$ are $v_1, v_2, \ldots, v_n$.
Let $v_j$ be a vertex of $P$ such that $j > 1$.
Then the predecessor (vertex) of $v_j$ is the vertex $v_{j - 1}$.
Successor
Let $D = \struct {V, E}$ be a digraph.
Let $P$ be a path in $D$ such that the vertices of $P$ are $v_1, v_2, \ldots, v_n$.
Let $v_j$ be a vertex of $P$ such that $j < n$.
Then the successor (vertex) of $v_j$ is the vertex $v_{j + 1}$.
Examples
Arbitrary Example
Consider the following digraph:
The sequence of vertices $1 \to 2 \to 3 \to 4$ highlighted in $\color { red } {\text {red} }$ is a path from $1$ to $4$.
Also see
- Results about paths in digraphs can be found here.
Sources
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees: Directed Graphs