Eulerian path

A trail in a graph that uses every edge exactly once; vertices may be revisited. It may start and end at different vertices or return to its start.

Graph theory: The mathematical study of graphs, structures made of vertices connected by edges. Eulerian paths are defined within graphs and concern how their edges can be traversed.
Euler's theorem on Eulerian paths: A graph has an Eulerian circuit when every non-isolated vertex lies in one connected component and every vertex has even degree. This theorem gives the circuit case, a key special case of Eulerian paths.
Seven Bridges of Königsberg: A famous eighteenth-century puzzle asking whether a walk could cross each of Königsberg's seven bridges exactly once. Euler's analysis of this puzzle established the edge-traversal problem behind Eulerian paths.
Route inspection problem: An optimization problem seeking a shortest closed route that traverses every edge of a network at least once. It extends Eulerian traversal to networks where no exact once-only route exists.
Graph (discrete mathematics): A structure consisting of vertices and edges that connect pairs of vertices. The arrangement of vertices and edges determines whether an Eulerian path exists.
Eulerian circuit: A closed trail that uses every edge of a graph exactly once. An Eulerian circuit is an Eulerian path whose starting and ending vertices coincide.
Leonhard Euler: An eighteenth-century Swiss mathematician whose work helped establish graph theory and many other mathematical fields. Euler proved that the Königsberg bridge puzzle had no solution and introduced its structural analysis.
Chinese postman problem: The problem of finding a shortest closed walk that covers every edge of a connected weighted graph. When a graph lacks an Eulerian circuit, this problem finds the least costly repeated-edge route.
Trail (graph theory): A walk in a graph that does not repeat any edge. An Eulerian path is a trail with the additional requirement of using every edge.
Hierholzer's algorithm: An algorithm that finds an Eulerian circuit or path by joining edge-disjoint circuits or trails. It constructs an Eulerian traversal efficiently once the graph satisfies the existence conditions.

Linked from 8 pages