Path (graph theory)

Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy & Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs.

Definitions

Walk, trail, and path

• A walk is a finite or infinite sequence of edges which joins a sequence of vertices.

Let G = (V, E, Φ) be a graph. A finite walk is a sequence of edges (e₁, e₂, ..., e_{n − 1}) for which there is a sequence of vertices (v₁, v₂, ..., v_n) such that Φ(e_i) = {v_i, v_{i + 1}} for i = 1, 2, ..., n − 1. (v₁, v₂, ..., v_n) is the vertex sequence of the walk. The walk is closed if v₁ = v_n, and it is open otherwise. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or ray) has a first vertex but no last vertex.

• A trail is a walk in which all edges are distinct.
• A path is a trail in which all vertices (and therefore also all edges) are distinct.

If w = (e₁, e₂, ..., e_{n − 1}) is a finite walk with vertex sequence (v₁, v₂, ..., v_n) then w is said to be a walk from v₁ to v_n. Similarly for a trail or a path. If there is a finite walk between two distinct vertices then there is also a finite trail and a finite path between them.

Some authors do not require that all vertices of a path be distinct and instead use the term simple path to refer to such a path where all vertices are distinct.

A weighted graph associates a value (weight) with every edge in the graph. The weight of a walk (or trail or path) in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words cost or length are used instead of weight.

Directed walk, directed trail, and directed path

• A directed walk is a finite or infinite sequence of edges directed in the same direction which joins a sequence of vertices.

Let G = (V, E, Φ) be a directed graph. A finite directed walk is a sequence of edges (e₁, e₂, ..., e_{n − 1}) for which there is a sequence of vertices (v₁, v₂, ..., v_n) such that Φ(e_i) = (v_i, v_{i + 1}) for i = 1, 2, ..., n − 1. (v₁, v₂, ..., v_n) is the vertex sequence of the directed walk. The directed walk is closed if v₁ = v_n, and it is open otherwise. An infinite directed walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite directed walk (or ray) has a first vertex but no last vertex.

• A directed trail is a directed walk in which all edges are distinct.
• A directed path is a directed trail in which all vertices are distinct.

If w = (e₁, e₂, ..., e_{n − 1}) is a finite directed walk with vertex sequence (v₁, v₂, ..., v_n) then w is said to be a walk from v₁ to v_n. Similarly for a directed trail or a path. If there is a finite directed walk between two distinct vertices then there is also a finite directed trail and a finite directed path between them.

A "simple directed path" is a path where all vertices are distinct.

A weighted directed graph associates a value (weight) with every edge in the directed graph. The weight of a directed walk (or trail or path) in a weighted directed graph is the sum of the weights of the traversed edges. Sometimes the words cost or length are used instead of weight.