Path (graph theory)

A path in a graph is a sequence of distinct vertices in which each consecutive pair is connected by an edge. Its length is the number of edges in the sequence.

Graph (discrete mathematics): A structure consisting of vertices and edges connecting pairs of vertices. A path is a particular sequence of vertices and edges within a graph.
Path length: The number of edges in a path. Length counts the steps between consecutive vertices.
Menger's theorem: A theorem equating the maximum number of internally vertex-disjoint paths with a minimum vertex-cut size. It uses collections of paths to quantify how robustly vertices are connected.
Trail (graph theory): A walk in which no edge is repeated, though vertices may repeat. A trail forbids repeated edges but allows vertex repetition, unlike a simple path.
Longest path problem: The problem of finding a longest simple path between specified vertices in a graph. Unlike shortest paths, maximizing path length is computationally difficult in general.
Vertex (graph theory): An individual element of a graph, often representing an object or state. Each position in a path is occupied by a vertex.
Shortest path problem: The problem of finding a path of minimum total edge weight between specified vertices. A path becomes an optimization object when its length or weight is minimized.
Eulerian path: A trail in a graph that traverses every edge exactly once. It emphasizes edge coverage, whereas an ordinary path emphasizes a vertex sequence.
Closed walk: A walk whose initial and final vertices are the same. Closure is an additional condition absent from a general path.
Hamiltonian path problem: The decision problem of determining whether a graph contains a Hamiltonian path. It asks whether a path can cover every vertex, a central hard path question.

Linked from 19 pages