Ayer a medianoche era la fecha límite para el reto matemático de El País, que consistía en encontrar un camino hamiltoniano en un grafo dado (o demostrar que no existía, como fue el caso).
Un amigo mío me explicó una demostración sencilla y elegante basada en la coloración de grafos, que es la que se explica en el video (el video está en español, pero apuesto a que hay explicaciones similares en inglés en internet).
Si entiendes español, te animo a verlo. Es corto, entretenido y fácil de seguir.
Este pequeño programa en Python encuentra un camino hamiltoniano para un grafo dado e imprime la solución (o None si no existe, como en este reto).
#!/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):
"""Puede recibir un entero o un 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):
"""Devuelve una lista de nodos que representan un camino hamiltoniano,
o None si no se encuentra.
"""
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())