§ Remembering Eulerian and Hamiltonian cycles
I used to keep forgetting the difference. Here's how I remember it now.
We know that an euler tour always exists for a tree. Indeed, it's
a handy data structure
that can be used to convet LCA (lowest common ancestor) into RMQ(range minimum query).
So, the "Euler tour" must exist for a tree. See that when we perform a tour
on the tree, we definitely walk a vertex twice (once when entering, once when
exiting). It seems like we walk the (undirected) edges twice as well.
However, if we consider the edges as directed edges , then we're only walking
the edges once.
- So an euler tour must correspond to a tour where we walk over each edge exactly once.
- A hamiltonian tour must (by complementarity) correspond to a tour where we over each vertex exactly once.