Eulerian cycle
Definition
- A eulerian cycle is an ordinary cycle in a directed or undirected graph that contains each edge/arc exactly once.
- A directed or undirected graph is called eulerian if it admits a eulerian cycle.
Remark: It is easy to see (and follows from the classical algorithm) that a graph [math]\displaystyle{ G }[/math] is eulerian if, and only if:
- Undirected case: [math]\displaystyle{ G }[/math] is connected, and each node has even degree.
- Directed case: [math]\displaystyle{ G }[/math] is strongly connected, and for each node [math]\displaystyle{ v }[/math], the indegree of [math]\displaystyle{ v }[/math] equals the outdegree of [math]\displaystyle{ v }[/math].
Input
A strongly connected directed or connected undirected graph.
Output
A eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that the graph is not eulerian.
Known algorithms
Classical eulerian cycle algorithm
Historical Approach
The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology. The problem was to find a walk through the city that would cross each bridge once and only once. Euler reformulate the oriblem in abstracts terms (laying the foundation of graph theory). So Euler replaces each land mann with an abstract node, aka vertex, and each brigde with an abstract connection, aka edge. TBC...