Definition:Path (Graph Theory)

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 $G$ be an undirected graph.

A path in $G$ is a trail in $G$ in which all vertices (except perhaps the first and last ones) are distinct.


A path between two vertices $u$ and $v$ is called a $u$-$v$ path.


Subgraph

The set of vertices and edges which go to make up a path in a graph $G$ form a subgraph of $G$.

This subgraph itself is also referred to as a path in $G$.


Open Path

An open path is a path in which the first and last vertices are distinct.


Path in Digraph

In the context of a digraph the definition is similar:

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$.


Also defined as

Some sources define a path as:

a walk in which all vertices (except perhaps the first and last ones) are distinct.


By this definition it would appear that a path is automatically a trail, because if an edge were to be retraced in any walk, then the vertices at either end of it would necessarily be visited more than once.


However, under this looser definition, the walk $u \to v \to u$ for two adjacent vertices $u$ and $v$, for example, would fit the definition of a path, and therefore be a cycle.

But such a walk is not a trail, as the edge $u v$ would be traversed twice.

Hence, on $\mathsf{Pr} \infty \mathsf{fWiki}$, it is insisted that a path be defined as a type of trail.


Also known as

Some sources refer to what $\mathsf{Pr} \infty \mathsf{fWiki}$ calls a path as a simple path, and use the term path to define what $\mathsf{Pr} \infty \mathsf{fWiki}$ defines as a walk.

A path in a graph $G$ can be referred to as a $G$-path.

Some sources use the word chain.

Some sources refer to this as a Hamiltonian walk for William Rowan Hamilton.

Some sources are not careful to distinguish between a walk and a path, glossing over the possibility of repetition of vertices.


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Path_(Graph_Theory)&oldid=734648"