Caminos y ciclos hamiltonianos

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Cada vértice, exactamente una vez

Un camino hamiltoniano es un camino que visita cada vértice de un grafo exactamente una vez. Un ciclo hamiltoniano hace lo mismo y después vuelve a su vértice inicial por una arista más. Un grafo con un ciclo hamiltoniano se llama hamiltoniano, y un grafo con un camino hamiltoniano a veces se llama trazable. Todo grafo hamiltoniano es trazable, ya que al borrar una arista de un ciclo hamiltoniano queda un camino hamiltoniano, pero lo contrario falla, como muestran los ejemplos de abajo.

La pregunta parece pariente cercana de la que Euler respondió en 1736, y la guía sobre caminos eulerianos cuenta esa historia. Un camino euleriano usa cada arista una vez; un camino hamiltoniano visita cada vértice una vez. La diferencia de dificultad es enorme. La pregunta de Euler se resuelve contando los grados impares, lo que lleva tiempo lineal. Para la pregunta de Hamilton no se conoce ninguna prueba comparable, y no se espera que exista.

En el grafo con forma de casa de arriba, el vértice A tiene grado 2, B y C tienen grado 4, y D y E tienen grado 3. Exactamente dos grados son impares, así que un camino euleriano va de D a E, y los grados por sí solos lo prueban. El ciclo hamiltoniano A, B, D, E, C también existe, pero la única forma general de saberlo es encontrarlo.

2. Del juego icosiano al grafo de Petersen

El nombre viene de William Rowan Hamilton, que en 1857 presentó el juego icosiano: un tablero dibujado como un dodecaedro, el sólido de 12 caras pentagonales y 20 esquinas, en el que el jugador tenía que visitar las 20 esquinas y volver al inicio siguiendo las aristas. Hamilton vendió los derechos por 25 libras a la empresa londinense John Jaques and Son, que puso el juego a la venta en 1859. La pregunta en sí es más antigua: Thomas Kirkman había preguntado en un artículo publicado en 1856 qué poliedros tienen un circuito que pasa por todas sus esquinas.

El dodecaedro tiene exactamente 30 ciclos hamiltonianos, contando cada ciclo una sola vez sin importar su sentido ni su esquina de partida. El grafo de Petersen, que Julius Petersen describió en 1898, es el contraste clásico. Tiene 10 vértices y 15 aristas, todos sus vértices tienen grado 3, es conexo y no tiene vértices de corte, y aun así no tiene ciclo hamiltoniano. Sí tiene un camino hamiltoniano. Más extraño todavía, al borrar cualquiera de sus vértices queda un grafo que sí tiene un ciclo hamiltoniano, una propiedad por la que se dice que es hipohamiltoniano. El grafo de Petersen cumple todas las pruebas sencillas que sugieren que un grafo debería ser hamiltoniano, y por eso aparece como contraejemplo en toda la teoría de grafos.

3. Cómo probar que no existe ningún ciclo

El ejemplo que nos acompaña es un museo con 9 salas, de la A a la I, y 14 puertas entre ellas. Un visitante quiere ver cada sala exactamente una vez e, idealmente, terminar donde empezó:

doors = {AB, AC, BC, FG, FH, GH, AD, BD, DF, DI, CE, EH, EI, EG}      9 salas, 14 puertas

deg:   A 3   B 3   C 3   D 4   E 4   F 3   G 3   H 3   I 2

Existe un camino hamiltoniano: A, B, C, E, G, H, F, D, I visita cada sala una vez. Un ciclo hamiltoniano no existe, y el motivo se ve en un dibujo. Cierra las salas D y E, y el resto del museo se separa en tres piezas: {A, B, C}, {F, G, H} y, por sí sola, la sala I.

El argumento sirve para cualquier grafo. Borra k vértices de un ciclo y se rompe en como mucho k arcos, así que si un grafo tiene un ciclo hamiltoniano, al borrar cualesquiera k de sus vértices quedan como mucho k piezas conexas. Un camino se rompe en como mucho k + 1 piezas, así que un grafo trazable deja como mucho k + 1. El museo tiene un conjunto de 2 salas cuya eliminación deja 3 piezas, demasiadas para un ciclo pero permitidas para un camino. Chvátal estudió esta medida en 1973 con el nombre de tenacidad.

from itertools import combinations

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def pieces(adj, removed):
    """Número de piezas conexas que quedan tras borrar los vértices de removed."""
    seen, count = set(removed), 0
    for s in adj:
        if s in seen:
            continue
        count += 1
        stack = [s]
        seen.add(s)
        while stack:
            for w in adj[stack.pop()] - seen:
                seen.add(w)
                stack.append(w)
    return count

def cycle_obstruction(adj):
    """Un conjunto S cuya eliminación deja más de |S| piezas: prueba de que no existe ciclo hamiltoniano."""
    for k in range(1, len(adj)):
        for S in combinations(sorted(adj), k):
            if pieces(adj, S) > k:
                return list(S), pieces(adj, S)
    return None

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(cycle_obstruction(museum))
# (['D', 'E'], 3)
outer = [(i, (i + 1) % 5) for i in range(5)]
spokes = [(i, i + 5) for i in range(5)]
star = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
petersen = graph(outer + spokes + star)
print(cycle_obstruction(petersen))            # no hay certificado, pero tampoco hay ciclo hamiltoniano
# None

La función prueba todos los conjuntos de vértices, de menor a mayor, y devuelve el primero que deja demasiadas piezas. En el museo encuentra {D, E}, el único conjunto así. En el grafo de Petersen no encuentra nada, aunque el grafo de Petersen no tiene ciclo hamiltoniano. Ese es el límite de toda condición de este tipo: puede probar que un ciclo es imposible, pero su silencio no prueba nada.

Varios casos particulares de la misma idea merecen conocerse por su nombre:

• Vértices de corte. Un grafo con un vértice de corte, uno cuya eliminación lo desconecta, no tiene ciclo hamiltoniano. Es el caso k = 1.
• Vértices de grado 1 o 2. Un vértice de grado 1 solo puede ser un extremo de un camino hamiltoniano, nunca parte de un ciclo. Un vértice de grado 2 obliga a que sus dos aristas estén en cualquier ciclo hamiltoniano: en el museo, habría que usar las dos puertas de la sala I.
• Grafos bipartitos desequilibrados. Un ciclo en un grafo bipartito alterna entre los dos lados, así que un ciclo hamiltoniano necesita lados del mismo tamaño, y un camino hamiltoniano necesita tamaños que difieran como mucho en uno. El grafo bipartito completo K2,3 tiene un camino hamiltoniano pero ningún ciclo hamiltoniano por este motivo.

4. Condiciones de grado que garantizan un ciclo

La dirección opuesta pregunta qué obliga a que exista un ciclo hamiltoniano. Las respuestas más famosas usan los grados, y la guía sobre el grado de un vértice trata la primera de ellas en detalle.

• Teorema de Dirac (1952). Un grafo simple con n ≥ 3 vértices en el que todo vértice tiene grado al menos n / 2 tiene un ciclo hamiltoniano.
• Teorema de Ore (1960). Basta con que deg(u) + deg(v) ≥ n para todo par de vértices u y v no adyacentes. La condición de Dirac es el caso particular en el que todos los grados son al menos n / 2.
• La clausura de Bondy–Chvátal (1976). Une repetidamente dos vértices no adyacentes cualesquiera cuyos grados sumen al menos n. El grafo original es hamiltoniano exactamente cuando el grafo final, su clausura, es hamiltoniano; si la clausura es completa, la respuesta es sí.
• El teorema de Chvátal–Erdős (1972). Si la conectividad de un grafo, el menor número de vértices cuya eliminación lo desconecta, es al menos su número de independencia, el tamaño de su mayor conjunto independiente, entonces el grafo es hamiltoniano. La guía sobre cliques y conjuntos independientes explica la segunda magnitud.

Todas estas son condiciones suficientes, no necesarias. Un ciclo de 100 vértices es hamiltoniano, y sin embargo todos sus vértices tienen grado 2, muy por debajo de 50. El museo muestra el otro lado: su mayor grado es 4, por debajo de 9 / 2, así que no se aplica ninguna de las condiciones de grado, lo cual es coherente con que no tenga ciclo. Tras abrir una puerta más, entre G e I, el museo se vuelve hamiltoniano, y las condiciones de grado siguen sin decir nada. Describen grafos lo bastante densos como para ser hamiltonianos por razones sencillas; los grafos dispersos necesitan otras herramientas.

5. Grafos planos: la conjetura de Tait y la respuesta de Tutte

Hubo un tiempo en que los ciclos hamiltonianos parecían un camino hacia el teorema de los cuatro colores. En 1884 Peter Guthrie Tait conjeturó que todo grafo plano 3-conexo y 3-regular tiene un ciclo hamiltoniano, lo que habría dado una demostración fácil de que cuatro colores bastan para los mapas en los que todas las esquinas tocan tres regiones. La conjetura era falsa. William Tutte publicó un contraejemplo de 46 vértices en 1946, y Holton y McKay demostraron en 1988 que los contraejemplos más pequeños tienen 38 vértices.

Un grado más de conectividad es suficiente. Whitney demostró en 1931 que toda triangulación plana 4-conexa es hamiltoniana, y Tutte lo extendió en 1956 a todo grafo plano 4-conexo. Estos resultados están entre los pocos que garantizan ciclos hamiltonianos en grafos dispersos, donde las condiciones de grado de la sección 4 no pueden aplicarse.

6. Encontrar un camino hamiltoniano mediante búsqueda

El método directo extiende un camino de vértice en vértice. En cada paso prueba por turno los vecinos no visitados del último vértice; cuando el camino no se puede extender y aún queda algún vértice sin visitar, retrocede y prueba la siguiente opción. Si el camino llega a cubrir todos los vértices, es un camino hamiltoniano, y si sus dos extremos son adyacentes, también se cierra en un ciclo.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def hamiltonian(adj, cycle=False):
    """Búsqueda con retroceso: extiende un camino de vértice en vértice y deshazlo en un callejón sin salida."""
    n = len(adj)
    def extend(path, seen):
        if len(path) == n:
            return path if not cycle or path[0] in adj[path[-1]] else None
        for w in sorted(adj[path[-1]] - seen):
            found = extend(path + [w], seen | {w})
            if found:
                return found
        return None                           # todas las continuaciones fallaron: retrocede
    starts = [min(adj)] if cycle else sorted(adj)   # un ciclo puede empezar en cualquier vértice
    for s in starts:
        found = extend([s], {s})
        if found:
            return found
    return None

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(hamiltonian(museum))                    # visita cada sala una vez
# ['A', 'B', 'C', 'E', 'G', 'H', 'F', 'D', 'I']
print(hamiltonian(museum, cycle=True))        # ... y vuelve al inicio
# None
museum['G'].add('I'); museum['I'].add('G')    # abre una puerta más
print(hamiltonian(museum, cycle=True))
# ['A', 'B', 'C', 'E', 'H', 'F', 'G', 'I', 'D']

La primera línea es el recorrido de la sección 3. La segunda confirma que ningún recorrido puede volver a su inicio, como probó la obstrucción. La tercera muestra que abrir una puerta más, entre G e I, hace posible un ciclo hamiltoniano. Al buscar un ciclo, la función empieza desde un único vértice, porque un ciclo pasa por todos los vértices y se puede leer desde cualquiera de ellos. La función se comprobó contra la fuerza bruta en 1136 grafos aleatorios de hasta 8 vértices.

La búsqueda con retroceso simple es exponencial: en el peor caso explora una gran parte de las n! ordenaciones de los vértices, y 20! es aproximadamente 2,4 × 1018. Los programas prácticos añaden poda. Abandonan una rama en cuanto los vértices no visitados quedan desconectados, o a un vértice le quedan demasiado pocos vecinos sin visitar para poder atravesarlo, o un vértice de grado 2 tiene bloqueadas sus aristas forzadas. También prueban primero el vecino más restringido, la misma idea que la regla de Warnsdorff para los recorridos del caballo de la sección 9.

7. Programación dinámica sobre subconjuntos

Un peor caso mejor se obtiene con un programa dinámico que encontraron de forma independiente Bellman, por un lado, y Held y Karp, por otro, en 1962, originalmente para el problema del viajante de comercio. Fija un vértice inicial. Para cada subconjunto S de vértices que lo contenga y cada vértice v en S, registra cuántos caminos empiezan en el vértice fijado, visitan exactamente los vértices de S y terminan en v. Cada entrada se construye a partir de subconjuntos más pequeños, y el conjunto completo da los caminos hamiltonianos, que se cierran en ciclos cuando su último vértice es adyacente al inicial.

from itertools import combinations

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def count_hamiltonian_cycles(adj):
    """Programación dinámica sobre subconjuntos (Bellman; Held y Karp), tiempo O(2^n * n^2)."""
    V = sorted(adj)
    n, index = len(V), {v: i for i, v in enumerate(V)}
    ways = [[0] * n for _ in range(1 << n)]   # ways[S][v]: caminos desde V[0] que pasan exactamente por S y terminan en v
    ways[1][0] = 1
    for S in range(1 << n):
        for v in range(n):
            if ways[S][v]:
                for w in adj[V[v]]:
                    j = index[w]
                    if not S >> j & 1:
                        ways[S | 1 << j][j] += ways[S][v]
    full = (1 << n) - 1
    closing = sum(ways[full][index[w]] for w in adj[V[0]])
    return closing // 2                       # cada ciclo se encuentra una vez en cada sentido

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(count_hamiltonian_cycles(museum))
# 0
museum['G'].add('I'); museum['I'].add('G')    # la puerta extra de antes
print(count_hamiltonian_cycles(museum))
# 4
print(count_hamiltonian_cycles(graph(combinations(range(6), 2))))   # K6: (6 - 1)! / 2
# 60

El museo no tiene ciclo hamiltoniano, el museo con la puerta extra tiene exactamente 4, y el grafo completo K6 tiene (6 − 1)! / 2 = 60, lo que coincide con la fórmula para grafos completos. El programa comprueba 2n subconjuntos con n vértices finales cada uno, y prueba hasta n vecinos para cada entrada, así que se ejecuta en tiempo O(2n n2). Para 20 vértices eso son 20.971.520 entradas de la tabla, una cifra grande pero totalmente asumible, mientras que listar los ciclos hamiltonianos de K20 uno por uno supondría recorrer 60.822.550.204.416.000 ciclos. El algoritmo más rápido conocido para grafos no dirigidos, un método aleatorizado de Björklund publicado en 2014, se ejecuta en tiempo O*(1,657n), donde el asterisco oculta factores polinómicos.

8. ¿Cuán difícil es el problema?

Decidir si un grafo tiene un ciclo hamiltoniano es NP-completo, tanto para grafos no dirigidos como dirigidos; ambas versiones estaban en la lista de Karp de 1972 de 21 problemas NP-completos. El problema del camino hamiltoniano también es NP-completo. La dificultad sobrevive a restricciones fuertes: Garey, Johnson y Tarjan demostraron en 1976 que el problema sigue siendo NP-completo para grafos planos 3-conexos y 3-regulares, exactamente la clase de la conjetura de Tait, e Itai, Papadimitriou y Szwarcfiter demostraron en 1982 que los caminos hamiltonianos en grafos de rejilla también son NP-completos, aunque las rejillas rectangulares completas son fáciles.

El contraste con el problema de Euler es el ejemplo más limpio de la teoría de grafos de dos preguntas que se parecen y viven en lados opuestos de la frontera entre P y NP. El problema del ciclo hamiltoniano es también el núcleo del problema del viajante de comercio: un grafo tiene un ciclo hamiltoniano exactamente cuando, tras dar longitud 1 a sus aristas y longitud 2 a cada arista ausente, el recorrido más corto por todos los vértices tiene longitud n. Así que cualquier algoritmo rápido para el problema del viajante de comercio también decidiría la hamiltonicidad.

9. Familias que siempre tienen uno

Algunas familias de grafos son hamiltonianas por razones estructurales, y varias de ellas son famosas por derecho propio.

• Grafos completos. Toda ordenación de los vértices de Kn es un camino hamiltoniano, y para n ≥ 3 hay (n − 1)! / 2 ciclos hamiltonianos.
• Torneos. Un torneo es un grafo dirigido con exactamente una flecha entre cada dos vértices, como los resultados de una liga de todos contra todos. Rédei demostró en 1934 que todo torneo tiene un camino hamiltoniano, así que los jugadores siempre se pueden ordenar de modo que cada uno haya ganado al siguiente, y Camion demostró en 1959 que un torneo tiene un ciclo hamiltoniano siempre que cada jugador pueda llegar a cualquier otro mediante una cadena de victorias.
• Hipercubos y códigos Gray. El grafo del cubo cuyos vértices son las cadenas binarias de longitud n, unidas cuando difieren en un bit, es hamiltoniano para n ≥ 2. Un ciclo hamiltoniano suyo es un código Gray: una lista de las 2n cadenas en la que las cadenas consecutivas difieren en un solo bit. Frank Gray patentó el código binario reflejado en 1953 para la transmisión de señales.
• Recorridos del caballo. Un caballo que visita cada casilla de un tablero de ajedrez una vez traza un camino hamiltoniano en el grafo de movimientos del caballo. Euler estudió estos recorridos en 1759, Warnsdorff propuso en 1823 la regla de moverse siempre a la casilla con menos movimientos siguientes, y Schwenk determinó en 1991 exactamente qué tableros rectangulares tienen un recorrido cerrado.

10. Grafos aleatorios: ¿cuándo aparecen los ciclos hamiltonianos?

Las obstrucciones de la sección 3 son sobre todo locales: un vértice con una sola arista, o unos pocos vértices que separan un trozo del grafo. En los grafos aleatorios, la obstrucción local resulta ser la única que importa. Pósa demostró en 1976 que un grafo aleatorio de n vértices con unas C n log n aristas, para una constante adecuada C, es casi seguro hamiltoniano. Komlós y Szemerédi encontraron el umbral exacto en 1983: está donde el número esperado de vértices de grado menor que 2 cae a cero.

La forma más precisa es un enunciado sobre un grafo que crece de arista aleatoria en arista aleatoria. Bollobás en 1984, e independientemente Ajtai, Komlós y Szemerédi en 1985, demostraron que, con probabilidad que tiende a 1, el grafo se vuelve hamiltoniano exactamente en el momento en que desaparece su último vértice de grado menor que 2. En un grafo aleatorio, en cuanto nada bloquea de forma evidente un ciclo hamiltoniano, existe uno.

11. Dónde se usan los caminos hamiltonianos

• Rutas y recorridos. Toda ronda de reparto, ruta de inspección o secuencia de taladrado que deba visitar cada punto una vez es un problema de ciclo hamiltoniano con distancias añadidas, que es el problema del viajante de comercio.
• Ensamblaje de genomas. Los primeros ensambladores modelaban las lecturas de ADN como vértices unidos por solapamientos y buscaban un camino hamiltoniano entre ellas. Idury y Waterman propusieron en 1995 reformular el ensamblaje como un problema de camino euleriano en un grafo de de Bruijn, y Pevzner, Tang y Waterman desarrollaron el enfoque en 2001, por lo que los ensambladores modernos resuelven el problema fácil de Euler en lugar del difícil de Hamilton.
• Codificadores y códigos Gray. Los codificadores de posición rotativos y lineales usan códigos Gray para que pasar de una posición a la siguiente cambie un solo bit, lo que evita grandes errores de lectura durante las transiciones.
• Pruebas y secuenciación. Visitar cada estado de un sistema una vez, u ordenar tareas de modo que cada una siga a una predecesora compatible, son problemas de camino hamiltoniano en el grafo de transiciones permitidas.
• Rompecabezas. El juego icosiano, los recorridos del caballo y muchos rompecabezas de trazar caminos piden caminos o ciclos hamiltonianos disfrazados.

12. Errores comunes

13. Glosario

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Euler, L. (1759). "Solution d'une question curieuse qui ne paroît soumise à aucune analyse." Mémoires de l'Académie Royale des Sciences et Belles Lettres de Berlin 15, 310 a 337. Fechado en 1759, impreso en 1766. Recorridos del caballo.
2. Warnsdorff, H. C. von (1823). Des Rösselsprunges einfachste und allgemeinste Lösung. Schmalkalden: Varnhagen.
3. Kirkman, T. P. (1856). "On the Representation of Polyedra." Philosophical Transactions of the Royal Society of London 146, 413 a 418.
4. Tait, P. G. (1884). "Listing's Topologie." Philosophical Magazine, 5.ª serie, 17, 30 a 46.
5. Petersen, J. (1898). "Sur le théorème de Tait." L'Intermédiaire des Mathématiciens 5, 225 a 227.
6. Whitney, H. (1931). "A Theorem on Graphs." Annals of Mathematics 32(2), 378 a 390.
7. Rédei, L. (1934). "Ein kombinatorischer Satz." Acta Litterarum ac Scientiarum Szeged 7, 39 a 43.
8. Tutte, W. T. (1946). "On Hamiltonian Circuits." Journal of the London Mathematical Society 21(2), 98 a 101.
9. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2, 69 a 81.
10. Gray, F. (1953). "Pulse Code Communication." Patente de EE. UU. 2,632,058.
11. Tutte, W. T. (1956). "A Theorem on Planar Graphs." Transactions of the American Mathematical Society 82, 99 a 116.
12. Camion, P. (1959). "Chemins et circuits hamiltoniens des graphes complets." Comptes Rendus de l'Académie des Sciences 249, 2151 a 2152.
13. Ore, O. (1960). "Note on Hamilton Circuits." The American Mathematical Monthly 67(1), 55.
14. Bellman, R. (1962). "Dynamic Programming Treatment of the Travelling Salesman Problem." Journal of the ACM 9(1), 61 a 63.
15. Held, M. y Karp, R. M. (1962). "A Dynamic Programming Approach to Sequencing Problems." Journal of the Society for Industrial and Applied Mathematics 10(1), 196 a 210.
16. Chvátal, V. y Erdős, P. (1972). "A Note on Hamiltonian Circuits." Discrete Mathematics 2(2), 111 a 113.
17. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." En Complexity of Computer Computations, editado por R. E. Miller y J. W. Thatcher, 85 a 103. New York: Plenum.
18. Chvátal, V. (1973). "Tough Graphs and Hamiltonian Circuits." Discrete Mathematics 5(3), 215 a 228.
19. Bondy, J. A. y Chvátal, V. (1976). "A Method in Graph Theory." Discrete Mathematics 15(2), 111 a 135.
20. Garey, M. R., Johnson, D. S. y Tarjan, R. E. (1976). "The Planar Hamiltonian Circuit Problem is NP-Complete." SIAM Journal on Computing 5(4), 704 a 714.
21. Pósa, L. (1976). "Hamiltonian Circuits in Random Graphs." Discrete Mathematics 14(4), 359 a 364.
22. Itai, A., Papadimitriou, C. H. y Szwarcfiter, J. L. (1982). "Hamilton Paths in Grid Graphs." SIAM Journal on Computing 11(4), 676 a 686.
23. Komlós, J. y Szemerédi, E. (1983). "Limit Distribution for the Existence of Hamiltonian Cycles in a Random Graph." Discrete Mathematics 43(1), 55 a 63.
24. Bollobás, B. (1984). "The Evolution of Sparse Graphs." En Graph Theory and Combinatorics, editado por B. Bollobás, 35 a 57. Londres: Academic Press.
25. Ajtai, M., Komlós, J. y Szemerédi, E. (1985). "First Occurrence of Hamilton Cycles in Random Graphs." Annals of Discrete Mathematics 27, 173 a 178.
26. Holton, D. A. y McKay, B. D. (1988). "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." Journal of Combinatorial Theory, Series B 45(3), 305 a 319.
27. Schwenk, A. J. (1991). "Which Rectangular Chessboards Have a Knight's Tour?" Mathematics Magazine 64(5), 325 a 332.
28. Idury, R. M. y Waterman, M. S. (1995). "A New Algorithm for DNA Sequence Assembly." Journal of Computational Biology 2(2), 291 a 306.
29. Pevzner, P. A., Tang, H. y Waterman, M. S. (2001). "An Eulerian Path Approach to DNA Fragment Assembly." Proceedings of the National Academy of Sciences 98(17), 9748 a 9753.
30. Björklund, A. (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM Journal on Computing 43(1), 280 a 299.
31. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.