§ 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 edgeexactly once.
- A hamiltonian tour must (by complementarity) correspond to a tour where weover each vertex exactly once.