Definition:Path (Graph Theory)/Digraph

From ProofWiki
Jump to navigation Jump to search

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:

Path-in-Digraph.png

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