Yesterday at midnight was the deadline of El País math challenge which consisted in finding the Hamiltonian path of a given graph (or to give a demonstration it hadn't any as it was the case).
A friend of mine told me a simple and elegant demonstration based on graph coloration, which is the one explained in the video (the video is in Spanish but it's my bet there are more demonstrations like this in English on the internet).
If you can understand Spanish, I encourage you to watch the video. It's really short, entertaining and easy to understand.
This tiny python program finds a Hamiltonian path for a given graph and prints the solution
(or None if it doesn't exist, as it happens in this math challenge).
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# vim:ts=4:et:sw=4
class Vertex(object):
def __init__(self, node, *nodeList):
self.i = node
self.nodeList = list(nodeList)
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.nodeList
return self.reaches(vertex.i)
def __str__(self):
return '< ' + str(self.i) + '>'
def __repr__(self):
return self.__str__()
class Graph(object):
def __init__(self):
self.vList = {}
def add(self, node, *nodeList):
vertex = Vertex(node, *nodeList)
self.vList[node] = vertex
def hamiltonian(self, current = None, pending = None, destiny = None):
""" Returns a list of nodes which represent
a hamiltonian path, or None if not found
"""
if pending is None:
pending = self.vList.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 pending == []:
if current.reaches(destiny):
return [current]
else:
return None
for x in [self.vList[v] for v in current.nodeList]:
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()