[2/6] Euler contre Hamilton : du critère local au casse-tête global

Repères de la série. L’article d’ouverture consacré à l’héritage d’Euler a posé le rôle fondateur des ponts de Königsberg. L’ article 1/6 sur Hamilton et le jeu icosien a ensuite déplacé la question des arêtes vers les sommets. Ce deuxième article s’intéresse maintenant à une autre différence : la manière dont on décide si le parcours existe.

Après les objets parcourus, la manière de décider

Dans l’article précédent, la comparaison portait surtout sur les objets imposés au parcours : les arêtes chez Euler, les sommets chez Hamilton. Cette distinction est essentielle, mais elle n’épuise pas le sujet. Une autre différence, plus discrète et plus profonde, apparaît lorsque l’on cherche à décider si le parcours existe.

Chez Euler, la réponse se lit dans les degrés des sommets. Pour obtenir un cycle eulérien, tous les sommets doivent avoir un degré pair : chaque fois que le parcours entre dans un sommet, il doit pouvoir en ressortir. Pour obtenir un simple chemin eulérien, on peut accepter deux sommets de degré impair : l’un sert de départ, l’autre d’arrivée.

Autrement dit, dans le monde d’Euler, la distinction entre chemin et cycle se décide localement. On examine les sommets un par un, on compte les degrés impairs, puis on peut conclure.

Chez Hamilton, rien d’aussi direct n’existe. Même en connaissant les degrés de tous les sommets, on ne sait pas forcément s’il est possible de les organiser en un chemin ou en un cycle passant une seule fois par chacun d’eux. La décision ne se lit plus sommet par sommet : elle dépend de l’organisation globale du graphe.

C’est ce changement d’échelle que cet article met en avant : Euler permet souvent de décider avant même de construire le parcours ; Hamilton oblige à chercher une organisation complète pour savoir si elle existe.

Chemin ou cycle : une nuance qui change la question

Une autre distinction mérite d’être posée clairement : cherche-t-on un chemin ou un cycle ? Dans un chemin, le point de départ et le point d’arrivée peuvent être différents. Dans un cycle, le parcours doit revenir à son point de départ.

Cette nuance existe aussi bien chez Euler que chez Hamilton, mais elle ne produit pas les mêmes effets. Du côté d’Euler, elle modifie simplement le critère sur les degrés : un cycle eulérien exige que tous les sommets aient un degré pair, tandis qu’un chemin eulérien autorise deux sommets de degré impair, qui jouent alors le rôle de départ et d’arrivée.

Du côté de Hamilton, la différence entre chemin et cycle est moins facile à lire. Un chemin hamiltonien demande d’ordonner tous les sommets de manière à passer une seule fois par chacun d’eux. Un cycle hamiltonien demande en plus que le dernier sommet puisse être relié au premier. Cette contrainte supplémentaire peut tout changer.

Ainsi, les quatre questions se ressemblent dans leur formulation, mais elles ne se décident pas de la même manière.

Euler : repérer les sommets qui posent problème

Dans un problème eulérien, les arêtes sont les objets à parcourir. On peut donc passer plusieurs fois par un même sommet, mais chaque arête doit être utilisée une seule fois. Cette règle donne un critère très efficace : il suffit d’observer les degrés des sommets.

Un sommet de degré pair ne pose pas de difficulté particulière. Chaque fois que le parcours y arrive par une arête, il peut en repartir par une autre. Les arêtes se regroupent naturellement par paires : une entrée, une sortie.

Un sommet de degré impair est différent. Il laisse forcément une arête sans partenaire. Dans un chemin eulérien, cela reste possible pour deux sommets seulement : l’un devient le départ, l’autre l’arrivée. Dans un cycle eulérien, aucun sommet ne peut jouer ce rôle particulier, puisque le parcours doit revenir à son point de départ.

Ainsi, Euler permet un diagnostic local. On ne cherche pas encore le parcours complet : on repère d’abord les sommets qui posent problème. En l’absence de sommet impair, un cycle eulérien est possible. Avec deux sommets impairs, on peut obtenir un chemin eulérien. Au-delà, il faudra modifier le réseau ou accepter de repasser par certaines arêtes.

Hamilton : trouver un ordre qui ne bloque pas

Dans un problème hamiltonien, ce ne sont plus les arêtes qu’il faut toutes parcourir, mais les sommets qu’il faut tous visiter. Les arêtes indiquent seulement les déplacements autorisés. La question devient donc : peut-on ranger tous les sommets dans un ordre compatible avec les arêtes du graphe ?

Pour un chemin hamiltonien, il faut trouver une liste de sommets dans laquelle deux sommets consécutifs sont toujours reliés. Pour un cycle hamiltonien, il faut en plus que le dernier sommet de la liste soit relié au premier. Cette dernière contrainte peut faire échouer une organisation qui semblait pourtant prometteuse.

La difficulté vient du fait qu’un bon choix local ne garantit pas une bonne solution globale. On peut choisir une arête parfaitement valide, puis une autre, puis encore une autre, et découvrir trop tard qu’un sommet devient impossible à intégrer sans en répéter un autre. Le problème n’est donc pas seulement d’avancer : il faut avancer sans enfermer la suite du parcours.

Les degrés des sommets peuvent donner des indications. Un sommet isolé rend évidemment impossible un chemin hamiltonien. Un sommet de degré 1 ne peut pas appartenir à un cycle hamiltonien. Mais ces observations ne forment pas un critère général comparable à celui d’Euler. Même si chaque sommet semble suffisamment relié, il reste à construire un ordre complet.

Dans le monde de Hamilton, la décision ne se lit donc pas sommet par sommet. Elle dépend de la manière dont tous les choix locaux s’assemblent dans une seule organisation globale.

Euler permet de diagnostiquer le graphe ; Hamilton oblige à le mettre à l’épreuve.

Python : quatre tests sur un même graphe

Pour rendre la comparaison plus concrète, on peut poser les quatre questions au même graphe. Le graphe choisi ici n’a pas d’importance historique : il sert seulement de terrain d’essai pour distinguer chemin eulérien, cycle eulérien, chemin hamiltonien et cycle hamiltonien.

La partie eulérienne se teste directement avec les degrés. La partie hamiltonienne, au contraire, demande de chercher un ordre possible des sommets. Le contraste apparaît donc dans le code lui-même.

from itertools import permutations

# Un petit graphe pour comparer les quatre questions
aretes = [
    ("A", "B"),
    ("B", "C"),
    ("C", "D"),
    ("D", "A"),
    ("A", "C")
]

def construit_graphe(aretes):
    """Construit un graphe non orienté sous forme de dictionnaire de voisins."""
    graphe = {}

    for sommet_1, sommet_2 in aretes:
        if sommet_1 not in graphe:
            graphe[sommet_1] = set()
        if sommet_2 not in graphe:
            graphe[sommet_2] = set()

        graphe[sommet_1].add(sommet_2)
        graphe[sommet_2].add(sommet_1)

    return graphe

def degre(graphe, sommet):
    """Renvoie le degré d'un sommet."""
    return len(graphe[sommet])

def degres_des_sommets(graphe):
    """Renvoie les degrés de tous les sommets."""
    return {
        sommet: degre(graphe, sommet)
        for sommet in graphe
    }

def sommets_de_degre_impair(graphe):
    """Renvoie la liste des sommets de degré impair."""
    return [
        sommet
        for sommet in graphe
        if degre(graphe, sommet) % 2 == 1
    ]

def graphe_connexe(graphe):
    """Vérifie que tous les sommets appartiennent au même morceau du graphe."""
    if not graphe:
        return True

    depart = next(iter(graphe))
    sommets_vus = {depart}
    sommets_a_explorer = [depart]

    while sommets_a_explorer:
        sommet = sommets_a_explorer.pop()

        for voisin in graphe[sommet]:
            if voisin not in sommets_vus:
                sommets_vus.add(voisin)
                sommets_a_explorer.append(voisin)

    return len(sommets_vus) == len(graphe)

def possede_un_chemin_eulerien(graphe):
    """Teste si le graphe possède un chemin eulérien."""
    if not graphe_connexe(graphe):
        return False

    nombre_impairs = len(sommets_de_degre_impair(graphe))
    return nombre_impairs == 0 or nombre_impairs == 2

def possede_un_cycle_eulerien(graphe):
    """Teste si le graphe possède un cycle eulérien."""
    if not graphe_connexe(graphe):
        return False

    nombre_impairs = len(sommets_de_degre_impair(graphe))
    return nombre_impairs == 0

def sont_relies(graphe, sommet_1, sommet_2):
    """Teste si deux sommets sont reliés par une arête."""
    return sommet_2 in graphe[sommet_1]

def forme_un_chemin_hamiltonien(graphe, ordre):
    """Teste si l'ordre donné forme un chemin hamiltonien."""
    return all(
        sont_relies(graphe, ordre[i], ordre[i + 1])
        for i in range(len(ordre) - 1)
    )

def forme_un_cycle_hamiltonien(graphe, ordre):
    """Teste si l'ordre donné forme un cycle hamiltonien."""
    return (
        forme_un_chemin_hamiltonien(graphe, ordre)
        and sont_relies(graphe, ordre[-1], ordre[0])
    )

def cherche_un_parcours_hamiltonien(graphe, cycle=False):
    """Cherche un chemin ou un cycle hamiltonien par exploration des ordres."""
    sommets = list(graphe)

    for ordre in permutations(sommets):
        if cycle and forme_un_cycle_hamiltonien(graphe, ordre):
            return ordre + (ordre[0],)

        if not cycle and forme_un_chemin_hamiltonien(graphe, ordre):
            return ordre

    return None

graphe = construit_graphe(aretes)

print("Degrés :", degres_des_sommets(graphe))
print("Sommets de degré impair :", sommets_de_degre_impair(graphe))
print("Chemin eulérien :", possede_un_chemin_eulerien(graphe))
print("Cycle eulérien :", possede_un_cycle_eulerien(graphe))
print("Chemin hamiltonien :", cherche_un_parcours_hamiltonien(graphe, cycle=False))
print("Cycle hamiltonien :", cherche_un_parcours_hamiltonien(graphe, cycle=True))

Vous pouvez copier-coller le code dans le bac à sable Python !

Cette différence résume le cœur de l’article. Dans le cas d’Euler, le graphe se diagnostique : les degrés indiquent immédiatement quels sommets posent problème et permettent de distinguer chemin et cycle. Dans le cas de Hamilton, le graphe s’explore : il ne suffit pas que les sommets semblent bien reliés, il faut encore trouver un ordre complet qui les fasse tous entrer dans un même parcours.

Un chemin ou un cycle hamiltonien dépend donc de la compatibilité de tous les choix. Une arête peut être valable localement, mais conduire plus loin à une impasse. C’est pourquoi Hamilton ne se décide pas sommet par sommet : il oblige à vérifier que l’ensemble du parcours tient jusqu’au bout.

Conclusion : le même dessin, pas le même monde

Euler et Hamilton travaillent sur les mêmes objets visuels : des sommets reliés par des arêtes. Pourtant, le changement de question suffit à changer de monde. Dans un cas, les degrés permettent de poser un diagnostic local. Dans l’autre, les degrés ne donnent qu’une information partielle : il faut encore réussir à organiser tous les sommets dans un ordre cohérent.

Cette différence explique pourquoi les problèmes hamiltoniens sont si délicats. On aimerait disposer d’un critère aussi simple que celui d’Euler, mais une telle règle générale ne se lit pas directement dans le graphe. Il existe pourtant des résultats puissants qui donnent des garanties dans certains cas : ils ne résolvent pas tout, mais ils indiquent quand un graphe est assez bien relié pour imposer l’existence d’un cycle hamiltonien.

Ce sera l’objet du prochain article : quitter le simple constat de difficulté pour découvrir les premiers grands critères hamiltoniens, notamment ceux qui relient le degré des sommets à l’existence d’un cycle.