§ Image unshredding as hamiltonian path
This was a cool use of hamiltonian path that I saw on hacker news
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).
- 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).