Informally ...
Given a network, or graph, an Euler Cycle is a tour from vertex to vertex,
finishing where it started, and traversing every edge exactly once.
In contrast:
- An Euler Path traverses every edge but need not finish where it started;
- A Hamilton Cycle visits every vertex exactly once and finishes where it started
- ... so the start/end vertex is, in some sense, visited twice
- ... except that starting at a vertex is not regarded as "a visit"; and
- A Hamilton Path includes every vertex exactly once,
- ... and need not finish where it started.
|
|
More formally ...
Given a graph $G=(V,E)$ where $|E|=m,$ an Euler Cycle is a list $L=[v_0,v_1,...,v_m]$
of vertices such that:
- $v_0=v_m$
- That is, the cycle ends where it started
- For every $i\in{1,2,...,m},$ $(v_{i-1},v_i)\in{E}$
- That is, going from vertex to vertex is along an edge
- For all $e=(u,v)\in{E},$ there exists exactly one $i$ such that either $u=v_i$ and $v=v_{i+1}$ or vice versa.
- That is, every edge is traversed exactly once.
A graph with an Euler Cycle is said to be "Eulerian."
|