Chemins et cycles hamiltoniens

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Chaque sommet, exactement une fois

Un chemin hamiltonien est un chemin qui visite chaque sommet d'un graphe exactement une fois. Un cycle hamiltonien fait de même, puis revient à son sommet de départ par une arête supplémentaire. Un graphe qui possède un cycle hamiltonien est dit hamiltonien, et un graphe qui possède un chemin hamiltonien est parfois dit traçable. Tout graphe hamiltonien est traçable, puisque supprimer une arête d'un cycle hamiltonien laisse un chemin hamiltonien, mais la réciproque est fausse, comme le montrent les exemples ci-dessous.

La question semble proche parente de celle à laquelle Euler a répondu en 1736, et le guide des chemins eulériens raconte cette histoire. Un parcours eulérien emprunte chaque arête une fois ; un chemin hamiltonien visite chaque sommet une fois. La différence de difficulté est énorme. La question d'Euler se règle en comptant les degrés impairs, ce qui prend un temps linéaire. Pour la question de Hamilton, aucun test comparable n'est connu, et l'on ne s'attend pas à ce qu'il en existe un.

Dans le graphe en forme de maison ci-dessus, le sommet A est de degré 2, B et C sont de degré 4, et D et E sont de degré 3. Exactement deux degrés sont impairs, donc un parcours eulérien va de D à E, et les degrés seuls le prouvent. Le cycle hamiltonien A, B, D, E, C existe aussi, mais la seule manière générale de le savoir est de le trouver.

2. Du jeu icosien au graphe de Petersen

Le nom vient de William Rowan Hamilton, qui a présenté en 1857 le jeu icosien : un plateau dessiné en forme de dodécaèdre, le solide à 12 faces pentagonales et 20 sommets, sur lequel le joueur devait visiter les 20 sommets et revenir au départ en suivant les arêtes. Hamilton en a vendu les droits pour 25 livres à la maison londonienne John Jaques and Son, qui a mis le jeu en vente en 1859. La question elle-même est plus ancienne : Thomas Kirkman avait demandé, dans un article publié en 1856, quels polyèdres possèdent un circuit passant par tous leurs sommets.

Le dodécaèdre possède exactement 30 cycles hamiltoniens, chaque cycle étant compté une seule fois quels que soient son sens et son sommet de départ. Le graphe de Petersen, décrit par Julius Petersen en 1898, est le contrepoint classique. Il a 10 sommets et 15 arêtes, chaque sommet est de degré 3, il est connexe et n'a aucun sommet d'articulation, et pourtant il n'a aucun cycle hamiltonien. Il possède en revanche un chemin hamiltonien. Plus étrange encore, supprimer n'importe lequel de ses sommets laisse un graphe qui, lui, possède un cycle hamiltonien, une propriété qui le rend hypohamiltonien. Tous les tests simples qui suggèrent qu'un graphe devrait être hamiltonien sont satisfaits par le graphe de Petersen, ce qui explique qu'il apparaisse comme contre-exemple dans toute la théorie des graphes.

3. Prouver qu'aucun cycle n'existe

L'exemple suivi est un musée de 9 salles, de A à I, reliées par 14 portes. Un visiteur veut voir chaque salle exactement une fois et, idéalement, terminer là où il a commencé :

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

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

Un chemin hamiltonien existe : A, B, C, E, G, H, F, D, I visite chaque salle une fois. Il n'existe en revanche aucun cycle hamiltonien, et la raison se voit sur un dessin. Fermez les salles D et E, et le reste du musée se divise en trois morceaux séparés : {A, B, C}, {F, G, H} et la salle isolée I.

L'argument vaut pour tout graphe. Supprimez k sommets d'un cycle et il se brise en au plus k arcs ; donc, si un graphe possède un cycle hamiltonien, supprimer n'importe quels k de ses sommets laisse au plus k morceaux connexes. Un chemin se brise en au plus k + 1 morceaux, donc un graphe traçable en laisse au plus k + 1. Le musée possède un ensemble de 2 salles dont la suppression laisse 3 morceaux, ce qui est trop pour un cycle mais permis pour un chemin. Chvátal a étudié cette mesure en 1973 sous le nom de ténacité.

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):
    """Nombre de morceaux connexes restant après suppression des sommets 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 ensemble S dont la suppression laisse plus de |S| morceaux : preuve qu'aucun cycle hamiltonien n'existe."""
    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))            # aucun certificat, et pourtant aucun cycle hamiltonien non plus
# None

La fonction essaie chaque ensemble de sommets, du plus petit au plus grand, et renvoie le premier qui laisse trop de morceaux. Sur le musée, elle trouve {D, E}, le seul ensemble de ce type. Sur le graphe de Petersen, elle ne trouve rien, alors même que le graphe de Petersen n'a aucun cycle hamiltonien. C'est la limite de toute condition de ce genre : elle peut prouver qu'un cycle est impossible, mais son silence ne prouve rien.

Plusieurs cas particuliers de la même idée méritent d'être connus par leur nom :

• Sommets d'articulation. Un graphe ayant un sommet d'articulation, c'est-à-dire un sommet dont la suppression le déconnecte, n'a aucun cycle hamiltonien. C'est le cas k = 1.
• Sommets de degré 1 ou 2. Un sommet de degré 1 ne peut être qu'une extrémité d'un chemin hamiltonien, jamais une partie d'un cycle. Un sommet de degré 2 impose ses deux arêtes dans tout cycle hamiltonien : dans le musée, les deux portes de la salle I devraient être empruntées.
• Graphes bipartis déséquilibrés. Dans un graphe biparti, un cycle alterne entre les deux côtés ; un cycle hamiltonien exige donc deux côtés de même taille, et un chemin hamiltonien des tailles qui diffèrent d'au plus un. Le graphe biparti complet K2,3 a un chemin hamiltonien mais aucun cycle hamiltonien pour cette raison.

4. Des conditions de degré qui garantissent un cycle

La direction opposée demande ce qui force l'existence d'un cycle hamiltonien. Les réponses les plus célèbres utilisent les degrés, et le guide du degré d'un sommet traite la première d'entre elles en détail.

• Théorème de Dirac (1952). Un graphe simple à n ≥ 3 sommets dans lequel chaque sommet est de degré au moins n / 2 possède un cycle hamiltonien.
• Théorème d'Ore (1960). Il suffit que deg(u) + deg(v) ≥ n pour toute paire de sommets u et v non adjacents. La condition de Dirac est le cas particulier où chaque degré vaut au moins n / 2.
• La fermeture de Bondy–Chvátal (1976). Reliez de façon répétée deux sommets non adjacents quelconques dont la somme des degrés vaut au moins n. Le graphe d'origine est hamiltonien exactement lorsque le graphe final, sa fermeture, est hamiltonien ; si la fermeture est complète, la réponse est oui.
• Le théorème de Chvátal–Erdős (1972). Si la connexité d'un graphe, le plus petit nombre de sommets dont la suppression le déconnecte, est au moins égale à son nombre de stabilité, la taille de son plus grand ensemble indépendant, alors le graphe est hamiltonien. Le guide des cliques et ensembles indépendants explique la seconde quantité.

Ce sont toutes des conditions suffisantes, pas nécessaires. Un cycle à 100 sommets est hamiltonien, et pourtant chaque sommet est de degré 2, bien en dessous de 50. Le musée montre l'autre versant : son plus grand degré est 4, inférieur à 9 / 2, si bien qu'aucune des conditions de degré ne s'applique, ce qui est cohérent avec l'absence de cycle. Si l'on ouvre une porte de plus, entre G et I, le musée devient hamiltonien, et les conditions de degré ne disent toujours rien. Elles décrivent des graphes assez denses pour être hamiltoniens pour des raisons simples ; les graphes creux exigent d'autres outils.

5. Graphes planaires : la conjecture de Tait et la réponse de Tutte

Les cycles hamiltoniens ont un temps semblé mener au théorème des quatre couleurs. En 1884, Peter Guthrie Tait a conjecturé que tout graphe planaire 3-connexe et 3-régulier possède un cycle hamiltonien, ce qui aurait donné une preuve facile que quatre couleurs suffisent pour les cartes dont chaque coin est commun à trois régions. La conjecture était fausse. William Tutte a publié un contre-exemple à 46 sommets en 1946, et Holton et McKay ont montré en 1988 que les plus petits contre-exemples ont 38 sommets.

Un degré de connexité de plus suffit. Whitney a prouvé en 1931 que toute triangulation planaire 4-connexe est hamiltonienne, et Tutte a étendu ce résultat en 1956 à tout graphe planaire 4-connexe. Ces résultats font partie des rares qui garantissent des cycles hamiltoniens dans des graphes creux, où les conditions de degré de la section 4 ne peuvent pas s'appliquer.

6. Trouver un chemin hamiltonien par recherche

La méthode directe prolonge un chemin un sommet à la fois. À chaque étape, elle essaie tour à tour les voisins non visités du dernier sommet ; quand le chemin ne peut plus être prolongé alors qu'un sommet reste non visité, elle revient en arrière et essaie le choix suivant. Si le chemin finit par couvrir tous les sommets, c'est un chemin hamiltonien, et si ses deux extrémités sont adjacentes, il se referme aussi en cycle.

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):
    """Retour arrière : prolonger un chemin un sommet à la fois et annuler à chaque impasse."""
    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                           # toutes les suites ont échoué : revenir en arrière
    starts = [min(adj)] if cycle else sorted(adj)   # un cycle peut partir de n'importe où
    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))                    # visiter chaque salle une fois
# ['A', 'B', 'C', 'E', 'G', 'H', 'F', 'D', 'I']
print(hamiltonian(museum, cycle=True))        # ... et revenir au départ
# None
museum['G'].add('I'); museum['I'].add('G')    # ouvrir une porte de plus
print(hamiltonian(museum, cycle=True))
# ['A', 'B', 'C', 'E', 'H', 'F', 'G', 'I', 'D']

La première ligne est la visite de la section 3. La deuxième confirme qu'aucune visite ne peut revenir à son point de départ, comme l'obstruction l'a prouvé. La troisième montre qu'ouvrir une porte de plus, entre G et I, rend un cycle hamiltonien possible. Quand elle cherche un cycle, la fonction part d'un seul sommet, car un cycle passe par tous les sommets et peut être lu à partir de n'importe lequel d'entre eux. La fonction a été vérifiée par comparaison avec la force brute sur 1 136 graphes aléatoires d'au plus 8 sommets.

La recherche avec retour arrière pure est exponentielle : dans le pire des cas, elle explore une grande partie des n! ordres possibles des sommets, et 20! vaut environ 2,4 × 1018. Les solveurs pratiques ajoutent de l'élagage. Ils abandonnent une branche dès que les sommets non visités sont déconnectés, qu'un sommet n'a plus assez de voisins non visités pour être traversé, ou que les arêtes imposées d'un sommet de degré 2 sont bloquées. Ils essaient aussi d'abord le voisin le plus contraint, la même idée que la règle de Warnsdorff pour les tours du cavalier de la section 9.

7. Programmation dynamique sur les sous-ensembles

Un meilleur pire cas vient d'un programme dynamique découvert indépendamment par Bellman et par Held et Karp en 1962, à l'origine pour le problème du voyageur de commerce. Fixez un sommet de départ. Pour chaque sous-ensemble S de sommets qui le contient et chaque sommet v de S, enregistrez combien de chemins partent du sommet fixé, visitent exactement les sommets de S et se terminent en v. Chaque entrée est construite à partir de sous-ensembles plus petits, et l'ensemble complet donne les chemins hamiltoniens, qui se referment en cycles lorsque leur dernier sommet est adjacent au départ.

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):
    """Programmation dynamique sur les sous-ensembles (Bellman ; Held et Karp), temps 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] : chemins partant de V[0], passant exactement par S et finissant 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                       # chaque cycle est trouvé une fois dans chaque sens

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 porte supplémentaire de tout à l'heure
print(count_hamiltonian_cycles(museum))
# 4
print(count_hamiltonian_cycles(graph(combinations(range(6), 2))))   # K6 : (6 - 1)! / 2
# 60

Le musée n'a aucun cycle hamiltonien, le musée avec la porte supplémentaire en a exactement 4, et le graphe complet K6 en a (6 − 1)! / 2 = 60, ce qui correspond à la formule pour les graphes complets. Le programme examine 2n sous-ensembles ayant chacun n sommets terminaux possibles, et essaie jusqu'à n voisins pour chaque entrée ; il s'exécute donc en temps O(2n n2). Pour 20 sommets, cela fait 20 971 520 entrées de table, beaucoup mais tout à fait faisable, alors qu'énumérer un par un les cycles hamiltoniens de K20 reviendrait à en parcourir 60 822 550 204 416 000. L'algorithme le plus rapide connu pour les graphes non orientés, une méthode probabiliste de Björklund publiée en 2014, s'exécute en temps O*(1,657n), où l'étoile masque des facteurs polynomiaux.

8. Quelle est la difficulté du problème ?

Décider si un graphe possède un cycle hamiltonien est NP-complet, pour les graphes non orientés comme pour les graphes orientés ; les deux versions figuraient sur la liste de 21 problèmes NP-complets établie par Karp en 1972. Le problème du chemin hamiltonien est lui aussi NP-complet. La difficulté résiste à de fortes restrictions : Garey, Johnson et Tarjan ont prouvé en 1976 que le problème reste NP-complet pour les graphes planaires 3-connexes et 3-réguliers, exactement la classe de la conjecture de Tait, et Itai, Papadimitriou et Szwarcfiter ont prouvé en 1982 que la recherche de chemins hamiltoniens dans les graphes grilles est elle aussi NP-complète, bien que les grilles rectangulaires complètes soient faciles.

Le contraste avec le problème d'Euler est l'exemple le plus net, en théorie des graphes, de deux questions qui se ressemblent et se situent de part et d'autre de la frontière entre P et NP. Le problème du cycle hamiltonien est aussi au cœur du problème du voyageur de commerce : un graphe possède un cycle hamiltonien exactement lorsque, après avoir donné à ses arêtes la longueur 1 et à chaque arête manquante la longueur 2, la plus courte tournée passant par tous les sommets a pour longueur n. Ainsi, tout algorithme rapide pour le problème du voyageur de commerce permettrait aussi de décider si un graphe est hamiltonien.

9. Des familles qui en ont toujours un

Certaines familles de graphes sont hamiltoniennes pour des raisons structurelles, et plusieurs d'entre elles sont célèbres à part entière.

• Graphes complets. Tout ordre des sommets de Kn est un chemin hamiltonien, et pour n ≥ 3 il y a (n − 1)! / 2 cycles hamiltoniens.
• Tournois. Un tournoi est un graphe orienté avec exactement une flèche entre deux sommets quelconques, comme les résultats d'une compétition où chacun rencontre tous les autres. Rédei a prouvé en 1934 que tout tournoi possède un chemin hamiltonien, de sorte que les joueurs peuvent toujours être rangés de façon que chacun ait battu le suivant, et Camion a prouvé en 1959 qu'un tournoi possède un cycle hamiltonien dès que chaque joueur peut atteindre tous les autres par une chaîne de victoires.
• Hypercubes et codes de Gray. Le graphe du cube, dont les sommets sont les chaînes binaires de longueur n, deux sommets étant reliés lorsqu'ils diffèrent d'un bit, est hamiltonien pour n ≥ 2. Un cycle hamiltonien de ce graphe est un code de Gray : une liste des 2n chaînes dans laquelle deux chaînes consécutives diffèrent d'un seul bit. Frank Gray a breveté le code binaire réfléchi en 1953 pour la transmission de signaux.
• Tours du cavalier. Un cavalier qui visite une fois chaque case d'un échiquier trace un chemin hamiltonien dans le graphe des sauts du cavalier. Euler a étudié de tels parcours en 1759, Warnsdorff a proposé en 1823 la règle consistant à toujours aller sur la case offrant le moins de coups suivants, et Schwenk a déterminé en 1991 exactement quels échiquiers rectangulaires admettent un tour fermé.

10. Graphes aléatoires : quand les cycles hamiltoniens apparaissent-ils ?

Les obstructions de la section 3 sont pour la plupart locales : un sommet avec une seule arête, ou quelques sommets qui isolent un morceau du graphe. Dans les graphes aléatoires, l'obstruction locale s'avère être la seule qui compte. Pósa a prouvé en 1976 qu'un graphe aléatoire à n sommets avec environ C n log n arêtes, pour une constante convenable C, est presque sûrement hamiltonien. Komlós et Szemerédi ont trouvé le seuil exact en 1983 : il se situe là où le nombre moyen de sommets de degré inférieur à 2 tombe à zéro.

La forme la plus fine est un énoncé sur un graphe qui grandit d'une arête aléatoire à la fois. Bollobás en 1984 et, indépendamment, Ajtai, Komlós et Szemerédi en 1985 ont prouvé qu'avec une probabilité tendant vers 1, le graphe devient hamiltonien exactement au moment où disparaît son dernier sommet de degré inférieur à 2. Dans un graphe aléatoire, dès que plus rien ne bloque manifestement un cycle hamiltonien, il en existe un.

11. Où servent les chemins hamiltoniens

• Itinéraires et tournées. Toute tournée de livraison, tout circuit d'inspection ou toute séquence de perçage qui doit visiter chaque site une fois est un problème de cycle hamiltonien assorti de distances, c'est-à-dire le problème du voyageur de commerce.
• Assemblage de génomes. Les premiers assembleurs modélisaient les lectures d'ADN comme des sommets reliés par leurs chevauchements et cherchaient un chemin hamiltonien qui les traverse. Idury et Waterman ont proposé en 1995 de reformuler l'assemblage comme un problème de chemin eulérien dans un graphe de de Bruijn, et Pevzner, Tang et Waterman ont développé cette approche en 2001, ce qui explique pourquoi les assembleurs modernes résolvent le problème facile d'Euler plutôt que le problème difficile de Hamilton.
• Codeurs et codes de Gray. Les codeurs de position rotatifs et linéaires utilisent des codes de Gray afin que le passage d'une position à la suivante ne change qu'un seul bit, ce qui évite de grosses erreurs de lecture pendant les transitions.
• Tests et ordonnancement. Visiter une fois chaque état d'un système, ou ordonner des tâches de sorte que chacune suive un prédécesseur compatible, sont des problèmes de chemin hamiltonien sur le graphe des transitions autorisées.
• Casse-tête. Le jeu icosien, les tours du cavalier et de nombreux casse-tête de tracé de chemins demandent, sous un déguisement, des chemins ou cycles hamiltoniens.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

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 à 337. Daté de 1759, imprimé en 1766. Tours du cavalier.
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 à 418.
4. Tait, P. G. (1884). "Listing's Topologie." Philosophical Magazine, 5e série, 17, 30 à 46.
5. Petersen, J. (1898). "Sur le théorème de Tait." L'Intermédiaire des Mathématiciens 5, 225 à 227.
6. Whitney, H. (1931). "A Theorem on Graphs." Annals of Mathematics 32(2), 378 à 390.
7. Rédei, L. (1934). "Ein kombinatorischer Satz." Acta Litterarum ac Scientiarum Szeged 7, 39 à 43.
8. Tutte, W. T. (1946). "On Hamiltonian Circuits." Journal of the London Mathematical Society 21(2), 98 à 101.
9. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2, 69 à 81.
10. Gray, F. (1953). "Pulse Code Communication." Brevet américain 2,632,058.
11. Tutte, W. T. (1956). "A Theorem on Planar Graphs." Transactions of the American Mathematical Society 82, 99 à 116.
12. Camion, P. (1959). "Chemins et circuits hamiltoniens des graphes complets." Comptes Rendus de l'Académie des Sciences 249, 2151 à 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 à 63.
15. Held, M. et Karp, R. M. (1962). "A Dynamic Programming Approach to Sequencing Problems." Journal of the Society for Industrial and Applied Mathematics 10(1), 196 à 210.
16. Chvátal, V. et Erdős, P. (1972). "A Note on Hamiltonian Circuits." Discrete Mathematics 2(2), 111 à 113.
17. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." Dans Complexity of Computer Computations, sous la direction de R. E. Miller et J. W. Thatcher, 85 à 103. New York : Plenum.
18. Chvátal, V. (1973). "Tough Graphs and Hamiltonian Circuits." Discrete Mathematics 5(3), 215 à 228.
19. Bondy, J. A. et Chvátal, V. (1976). "A Method in Graph Theory." Discrete Mathematics 15(2), 111 à 135.
20. Garey, M. R., Johnson, D. S. et Tarjan, R. E. (1976). "The Planar Hamiltonian Circuit Problem is NP-Complete." SIAM Journal on Computing 5(4), 704 à 714.
21. Pósa, L. (1976). "Hamiltonian Circuits in Random Graphs." Discrete Mathematics 14(4), 359 à 364.
22. Itai, A., Papadimitriou, C. H. et Szwarcfiter, J. L. (1982). "Hamilton Paths in Grid Graphs." SIAM Journal on Computing 11(4), 676 à 686.
23. Komlós, J. et Szemerédi, E. (1983). "Limit Distribution for the Existence of Hamiltonian Cycles in a Random Graph." Discrete Mathematics 43(1), 55 à 63.
24. Bollobás, B. (1984). "The Evolution of Sparse Graphs." Dans Graph Theory and Combinatorics, sous la direction de B. Bollobás, 35 à 57. Londres : Academic Press.
25. Ajtai, M., Komlós, J. et Szemerédi, E. (1985). "First Occurrence of Hamilton Cycles in Random Graphs." Annals of Discrete Mathematics 27, 173 à 178.
26. Holton, D. A. et 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 à 319.
27. Schwenk, A. J. (1991). "Which Rectangular Chessboards Have a Knight's Tour?" Mathematics Magazine 64(5), 325 à 332.
28. Idury, R. M. et Waterman, M. S. (1995). "A New Algorithm for DNA Sequence Assembly." Journal of Computational Biology 2(2), 291 à 306.
29. Pevzner, P. A., Tang, H. et Waterman, M. S. (2001). "An Eulerian Path Approach to DNA Fragment Assembly." Proceedings of the National Academy of Sciences 98(17), 9748 à 9753.
30. Björklund, A. (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM Journal on Computing 43(1), 280 à 299.
31. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.