§ Image unshredding as hamiltonian path

This was a cool use of hamiltonian path that I saw on hacker news recently.

• The problem is this: given an image where the columns are created by shuffling columns of an original image, we must recreate the original image.
• The reduction: treat each column as a vertex, connect columns that are close to each other in similarity.
• Hamiltonian path will visit each vertex exactly once (ie, pick each column exactly once).

I think this example is striking enough that I'll never forget that in a hamiltonian path, we can visit vertices exactly one, (in contrast to an euler tour, we must visit each edge exactly once).