subpaths

Subpaths are contiguous portions of paths in graph theory. If a path P is given as a sequence of vertices v0, v1, ..., vk with edges (v0, v1), (v1, v2), ..., (v_{k-1}, vk), then for any i and j with 0 ≤ i ≤ j ≤ k, the subpath P[i..j] consists of the vertex sequence vi, vi+1, ..., vj and the edges (vi, vi+1), ..., (v_{j-1}, vj). If i = j, the subpath is a trivial subpath containing a single vertex. In directed graphs the subpath must respect the given edge directions; in undirected graphs the order is not important, and a subpath is simply a contiguous segment of the original path.

Subpaths have the path property themselves: a subpath of a path is always a path (no detours beyond the segment). For a path with k edges (k+1 vertices), the number of subpaths including the trivial ones is (k+1)(k+2)/2; the number of proper subpaths (i < j) is (k+1)k/2.

Applications of subpaths appear in various areas of graph algorithms and theory, including dynamic programming on graphs, path decomposition, and subpath queries in graph databases. They also relate to concepts such as simple paths, trails, and walks, and are used to reason about substructures within larger paths.

See also: path, simple path, trail, walk, path decomposition.