Yesterday at midnight was the deadline for the El País math challenge, which consisted of finding a Hamiltonian path in a given graph (or providing a proof that none existed, as was the case here).
A friend of mine shared a simple and elegant proof based on graph coloring, which is the one explained in the video (the video is in Spanish, but I bet there are similar explanations in English online).
If you understand Spanish, I encourage you to watch it. It’s short, entertaining, and easy to follow.
This small Python program finds a Hamiltonian path for a given graph and prints the solution (or None if no such path exists, as in this challenge).
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# vim:ts=4:et:sw=4
class Vertex:
def __init__(self, node, *node_list):
self.i = node
self.node_list = list(node_list)
def __hash__(self):
return self.i
def reaches(self, vertex):
"""Can receive an integer or a Vertex."""
if isinstance(vertex, int):
return vertex in self.node_list
return self.reaches(vertex.i)
def __str__(self):
return f'<{self.i}>'
def __repr__(self):
return self.__str__()
class Graph:
def __init__(self):
self.v_list = {}
def add(self, node, *node_list):
vertex = Vertex(node, *node_list)
self.v_list[node] = vertex
def hamiltonian(self, current=None, pending=None, destiny=None):
"""Returns a list of nodes representing a Hamiltonian path, or None if not found."""
if pending is None:
pending = list(self.v_list.values())
result = None
if current is None:
for current in pending:
result = self.hamiltonian(
current,
[x for x in pending if x is not current],
current,
)
if result is not None:
break
else:
if not pending:
if current.reaches(destiny):
return [current]
return None
for x in [self.v_list[v] for v in current.node_list]:
if x in pending:
result = self.hamiltonian(x, [y for y in pending if y is not x], destiny)
if result is not None:
result = [current] + result
break
return result
if __name__ == '__main__':
G = Graph()
G.add(1, 2, 8, 11)
G.add(2, 1, 6, 9)
G.add(3, 6, 7, 9, 10)
G.add(4, 5, 7, 10)
G.add(5, 4, 8, 11)
G.add(6, 2, 3, 8)
G.add(7, 3, 4, 8)
G.add(8, 1, 6, 7, 5)
G.add(9, 2, 3, 11)
G.add(10, 3, 4, 11)
G.add(11, 1, 9, 10, 5)
print(G.hamiltonian())