[3/6] Dirac et Ore : quand les degrés imposent un cycle hamiltonien

Les épisodes précédents. Après avoir retrouvé l’héritage d’Euler, nous avons suivi Hamilton et son jeu icosien, puis comparé, dans Euler contre Hamilton, un problème que les degrés permettent de diagnostiquer à un autre qui oblige souvent à explorer. Ce troisième volet cherche précisément les situations dans lesquelles la théorie peut malgré tout répondre avant la recherche.

De « L’ascenseur fou fou fou ! » au rêve d’un critère hamiltonien

Malik habite au douzième étage d’un immeuble qui en compte quinze, sans oublier le rez-de-chaussée. L’ascenseur de sa résidence est plutôt capricieux : il ne possède que trois boutons. Le premier permet de monter de quatre étages, le deuxième de monter de dix étages et le dernier de descendre de cinq étages.

Le défi de Malik

En partant de l’étage 12, peut-on rejoindre successivement tous les niveaux de l’immeuble, de 0 à 15, sans jamais s’arrêter deux fois au même endroit ?

• monter de 4 étages ;
• monter de 10 étages ;
• descendre de 5 étages.

Malik affirme que c’est possible et qu’il n’existe qu’une seule solution.

Le début paraît presque trop facile. Depuis l’étage 12, monter de 4 ou de 10 étages ferait traverser le toit. Il faut donc descendre de 5 niveaux et rejoindre l’étage 7.

12 → 7

À l’étage 7, en revanche, le parcours se divise. L’ascenseur peut descendre à l’étage 2 ou monter à l’étage 11. Les deux déplacements sont autorisés. Aucun calcul ne permet, à lui seul, de rejeter l’un des deux.

Un déplacement peut être parfaitement légal et pourtant rendre impossible la visite de tout l’immeuble.

Un changement de nature…

C’est ici que le petit problème d’ascenseur change de nature. Il ne suffit plus de savoir où l’on peut aller au prochain coup. Il faut anticiper les étages que chaque décision risque d’isoler, préserver des portes de sortie et parfois renoncer à un choix séduisant parce qu’il condamnera le parcours plusieurs étapes plus tard.

Un même défi, plusieurs lectures

• Pour l’élève, c’est un jeu de calcul mental, de logique et de persévérance.
• Pour le professeur, c’est une situation où essayer, conjecturer et revenir sur ses choix devient une véritable méthode de recherche.
• Pour l’informaticien, c’est un problème d’exploration : il faut avancer, détecter les impasses, puis revenir au dernier embranchement pour tester une autre possibilité.
• Pour le mathématicien, c’est déjà une question hamiltonienne : existe-t-il un parcours capable de visiter tous les sommets exactement une fois ?

Pour passer d’une lecture à l’autre, il suffit de faire disparaître l’immeuble. Les étages deviennent des sommets et chaque déplacement autorisé devient un arc reliant deux niveaux.

La question de Malik prend alors une autre forme : existe-t-il, à partir du sommet 12, un chemin qui visite exactement une fois chacun des seize sommets du graphe ?

Ce chemin porte un nom désormais familier dans cette série : c’est un chemin hamiltonien. Pourtant, le véritable intérêt du problème ne réside pas seulement dans le vocabulaire. Il tient dans le changement de regard qu’il provoque. Ce qui ressemblait à une succession de petits calculs devient un problème global : chaque choix dépend de tous ceux qui suivront.

Chercher le parcours de Malik

De l’existence…

On peut naturellement résoudre cet exercice en explorant les itinéraires possibles. Depuis l’étage 7, on tente une direction ; si elle mène à une impasse, on revient au dernier choix et l’on emprunte l’autre. La fiche possède une solution unique, mais rien, au premier regard, ne nous dit pourquoi elle existe ni comment la reconnaître sans effectuer cette recherche.

Trouver un parcours est une chose.
Savoir avant de le chercher qu’un parcours doit exister en est une autre.

Imaginons maintenant que l’ascenseur dispose de davantage de boutons. Chaque étage deviendrait accessible depuis un plus grand nombre d’autres niveaux. Les possibilités se multiplieraient, les sommets seraient mieux reliés et les risques d’en isoler un diminueraient.

Mais à partir de quel moment les connexions deviennent-elles suffisamment nombreuses pour rendre un parcours hamiltonien inévitable ? Existe-t-il un seuil au-delà duquel il ne serait plus nécessaire de tester tous les itinéraires pour être certain qu’un cycle passe par chacun des sommets ?

Un graphe peut-il être tellement bien connecté qu’un cycle hamiltonien n’ait plus d’autre choix que d’exister ?

Le problème de Malik ne répond pas directement à cette question. Ses déplacements sont orientés et il recherche un chemin ouvert, tandis que les théorèmes qui vont suivre portent sur des cycles dans des graphes simples non orientés. Il fournit néanmoins le bon point de départ : après avoir éprouvé la difficulté de construire un parcours, nous pouvons chercher des propriétés capables d’en garantir l’existence.

Le théorème de Dirac : quand chaque sommet connaît la moitié du graphe

En 1952, le mathématicien britannique Gabriel Andrew Dirac apporte une réponse spectaculaire à la question que nous venons de poser. Il ne fournit pas une méthode permettant de construire pas à pas le bon parcours. Il établit quelque chose de différent et, d’une certaine manière, de plus vertigineux : dans un graphe suffisamment dense, le cycle hamiltonien ne peut pas manquer.

L’idée tient dans le degré des sommets. Rappelons que le degré d’un sommet est simplement le nombre de ses voisins. Dans l’immeuble de Malik, cela correspondrait au nombre d’étages que l’on peut rejoindre directement depuis un niveau donné — en oubliant un instant le sens des déplacements.

Dirac considère alors le sommet le moins favorisé du graphe : celui qui possède le plus petit nombre de voisins. Si même ce sommet reste fortement connecté, tous les autres le sont au moins autant. Le graphe est alors si riche en liaisons que les impasses finissent par devenir impossibles.

Théorème de Dirac — 1952

Soit un graphe simple non orienté comportant n sommets, avec n supérieur ou égal à 3.

Si chaque sommet possède au moins n ÷ 2 voisins, alors le graphe contient un cycle hamiltonien.

δ(G) ≥ n/2  ⟹  G est hamiltonien

La notation δ(G), appelée « degré minimal de G », désigne le plus petit degré rencontré parmi tous les sommets du graphe.

L’énoncé est court, mais il faut prendre le temps d’en mesurer la force. Dirac ne demande pas que tous les sommets soient reliés entre eux. Il n’exige pas non plus que l’on connaisse déjà une partie du cycle recherché. Il suffit que chaque sommet soit adjacent à au moins la moitié des sommets du graphe.

Comme le degré est nécessairement un nombre entier, une petite précision s’impose lorsque n est impair. Dans un graphe à 7 sommets, avoir un degré au moins égal à 7 ÷ 2 signifie en pratique avoir au moins 4 voisins : trois voisins ne suffisent pas à atteindre le seuil de 3,5.

Pourquoi la moitié ?

Imaginons que l’on commence à construire un très long chemin dans le graphe. À chacune de ses extrémités, de nombreux prolongements sont possibles puisque le sommet concerné possède au moins n ÷ 2 voisins. Si le chemin ne peut plus être allongé, tous ces voisins figurent nécessairement déjà parmi les sommets visités.

Or les deux extrémités possèdent, à elles seules, suffisamment de connexions pour que certaines d’entre elles finissent par se croiser de la bonne manière. Le chemin peut alors se refermer sur lui-même et devenir un cycle. La moitié n’est donc pas un nombre choisi au hasard : c’est le seuil à partir duquel les voisinages deviennent trop importants pour continuer à s’éviter.

Lorsque chaque sommet peut rejoindre au moins la moitié du graphe, les connexions locales finissent par imposer une organisation globale.

Huit sommets, quatre voisins : le cas limite

Considérons huit sommets répartis en deux groupes :

Premier groupe

A₁, A₂, A₃, A₄

Deuxième groupe

B₁, B₂, B₃, B₄

Chaque sommet du premier groupe est relié aux quatre sommets du second, et réciproquement. Aucun sommet n’est relié aux trois autres membres de son propre groupe. Chacun possède donc exactement quatre voisins.

n = 8  et  δ(G) = 4 = n/2

La condition de Dirac est satisfaite de justesse. Le théorème nous garantit donc l’existence d’un cycle hamiltonien avant même que nous ayons essayé de le construire.

Un cycle possible

A₁ → B₁ → A₂ → B₂ → A₃ → B₃ → A₄ → B₄ → A₁

Dans cet exemple, nous pouvons exhiber le cycle. Mais ce n’est pas ce qui fait la puissance du théorème. Avant même d’avoir écrit cette suite, la seule lecture des degrés nous assurait déjà qu’un tel cycle devait exister.

Dirac ne donne pas l’itinéraire.
Il garantit que l’itinéraire existe.

Une garantie, pas un portrait-robot

Il serait tentant de lire le théorème dans les deux sens. Ce serait une erreur. Un graphe peut parfaitement posséder un cycle hamiltonien sans que chacun de ses sommets soit relié à la moitié du graphe.

Le simple cycle formé de huit sommets en fournit un exemple immédiat. Il est hamiltonien par construction : il suffit d’en faire le tour. Pourtant, chacun de ses sommets ne possède que deux voisins, bien loin des quatre exigés par Dirac.

La condition de Dirac est suffisante, mais elle n’est pas nécessaire.

Lorsqu’elle est satisfaite, le cycle est garanti. Lorsqu’elle ne l’est pas, le théorème garde simplement le silence.

Ce silence laisse encore de nombreux graphes dans l’ombre. Que se passe-t-il, par exemple, si un sommet possède un peu moins de voisins que ne l’exige Dirac, mais si les sommets auxquels il n’est pas relié sont, eux, particulièrement bien connectés ? Faut-il renoncer immédiatement à toute garantie ?

Quelques années plus tard, Øystein Ore déplacera subtilement le regard. Au lieu d’examiner séparément le degré de chaque sommet, il s’intéressera aux paires de sommets qui ne sont pas voisins. Cette modification paraît légère. Elle donnera pourtant un critère plus souple et plus puissant.

Le théorème d’Ore : la force des sommets qui ne se connaissent pas

Dirac observait chaque sommet séparément et imposait à tous le même seuil : au moins la moitié du graphe parmi leurs voisins. Huit ans plus tard, le mathématicien norvégien Øystein Ore déplace légèrement le regard.

Il ne demande plus :

« Combien de voisins possède chaque sommet ? »

Il examine plutôt les sommets entre lesquels il manque une arête :

« Lorsque deux sommets ne sont pas voisins, leurs connexions cumulées suffisent-elles à compenser cette absence ? »

Ce changement paraît minime. Il permet pourtant de détecter des graphes hamiltoniens que le théorème de Dirac laissait dans l’ombre.

Théorème d’Ore — 1960

Soit un graphe simple non orienté comportant n sommets, avec n supérieur ou égal à 3.

Si, pour toute paire de sommets non adjacents u et v, la somme de leurs degrés est au moins égale à n, alors le graphe possède un cycle hamiltonien.

u et v non adjacents
d(u) + d(v) ≥ n  ⟹  G est hamiltonien

Le théorème ne s’intéresse donc pas à toutes les paires de sommets. Lorsque u et v sont déjà voisins, aucune vérification n’est demandée. Ce sont les liaisons absentes qui retiennent l’attention d’Ore.

Un sommet peut même posséder moins de n ÷ 2 voisins et manquer ainsi le seuil fixé par Dirac. Ore l’accepte, à condition que chacun des sommets auxquels il n’est pas relié soit suffisamment bien connecté pour que la somme des deux degrés atteigne n.

Chez Dirac, chaque sommet doit être fort.
Chez Ore, une faiblesse locale peut être compensée par la richesse du sommet d’en face.

Un graphe accepté par Ore, mais refusé par Dirac

Considérons un graphe à six sommets, nommés A, B, C, D, E et F.

• Les cinq sommets B, C, D, E et F sont tous reliés entre eux.
• Le sommet A est relié uniquement à B et à C.

Le sommet A ne possède que deux voisins. Comme le graphe compte six sommets, Dirac en exigerait au moins trois.

Condition de Dirac

d(A) = 2 < 3

Le théorème de Dirac ne permet pas de conclure.

Regardons maintenant ce qu’en dit Ore. Les seules paires de sommets non adjacents sont A–D, A–E et A–F. Les degrés valent :

Pour chacune des trois paires non adjacentes, le calcul est donc le même :

d(A) + d(D) = 2 + 4 = 6

Il en va de même avec E et F. La somme atteint chaque fois le nombre total de sommets. La condition d’Ore est satisfaite : le graphe est nécessairement hamiltonien.

Un cycle hamiltonien possible

A → B → D → E → F → C → A

Nous pouvons ici écrire explicitement un cycle. Mais, comme chez Dirac, l’intérêt du résultat se situe en amont : avant d’avoir cherché cet itinéraire, la seule vérification des degrés nous assurait déjà qu’il devait en exister un.

Pourquoi Ore englobe-t-il Dirac ?

Supposons qu’un graphe vérifie la condition de Dirac. Chaque sommet possède alors un degré au moins égal à n ÷ 2.

Pour deux sommets quelconques u et v — et donc en particulier pour deux sommets non adjacents — on obtient :

d(u) + d(v) ≥ n/2 + n/2 = n

Tout graphe qui satisfait Dirac satisfait donc automatiquement Ore. La réciproque est fausse, comme le montre notre graphe à six sommets : Ore peut conclure alors que Dirac ne le peut pas.

Dirac impose un seuil à chaque sommet.
Ore autorise les compensations entre sommets non voisins.

Dirac regarde les sommets.
Ore regarde les absences entre eux.

Ces deux théorèmes réalisent une prouesse remarquable : ils transforment des informations locales sur les degrés en une certitude portant sur un cycle qui traverse tout le graphe. Mais ils ne construisent toujours pas ce cycle, et leur échec ne signifie jamais que le graphe n’est pas hamiltonien.

Pour mesurer exactement ce que ces critères nous apprennent — et surtout ce qu’ils ne nous apprennent pas — il faut maintenant les confronter à quelques graphes qui leur échappent.

Garantir n’est pas caractériser : quand les théorèmes se taisent

Dirac et Ore accomplissent quelque chose de remarquable : à partir de quelques informations sur les degrés, ils garantissent l’existence d’un cycle qui traverse tout le graphe. Mais leur puissance pourrait facilement conduire à une mauvaise interprétation.

Lorsqu’un graphe vérifie Dirac ou Ore, il est hamiltonien.

Lorsqu’il ne les vérifie pas, nous ne savons encore rien.

Ces théorèmes fournissent des conditions suffisantes : elles suffisent pour conclure, mais elles ne sont pas indispensables. Un graphe peut parfaitement posséder un cycle hamiltonien sans atteindre les seuils imposés par Dirac ou Ore.

Un cycle qui échappe aux deux théorèmes

Prenons le cas le plus direct possible : huit sommets disposés sur un cycle.

A → B → C → D → E → F → G → H → A

Ce graphe est évidemment hamiltonien : le cycle est déjà sous nos yeux. Pourtant, chaque sommet ne possède que deux voisins.

Dirac en réclamerait au moins quatre, puisque le graphe compte huit sommets. Sa condition n’est donc pas satisfaite.

Ore échoue lui aussi. Deux sommets non voisins ont chacun un degré égal à 2, donc la somme de leurs degrés ne vaut que 4, bien loin des 8 attendus.

Le graphe est hamiltonien, mais ni Dirac ni Ore ne permettent de le démontrer.

Les deux théorèmes ne se trompent pas. Ils ne prétendent simplement pas reconnaître tous les graphes hamiltoniens.

Le même silence pour deux réalités opposées

Considérons maintenant deux triangles reliés par une seule arête.

Cette arête centrale constitue l’unique passage entre les deux parties du graphe. Pour visiter tous les sommets dans un cycle, il faudrait la franchir afin de rejoindre le second triangle, puis la franchir de nouveau pour revenir au point de départ.

Mais un cycle ne peut pas utiliser deux fois la même arête. Ce graphe n’est donc pas hamiltonien.

Il ne vérifie évidemment ni Dirac ni Ore. Pourtant, cette fois, leur silence cache une absence réelle de cycle hamiltonien.

Lorsque Dirac et Ore échouent, deux situations restent possibles :

• le graphe possède malgré tout un cycle hamiltonien ;
• le graphe n’en possède aucun.

Les degrés seuls ne permettent alors plus de trancher. Il faut observer plus finement la structure du graphe, repérer les passages obligés, rechercher un cycle ou mettre en évidence un obstacle qui interdit son existence.

Quatre situations à ne pas confondre

Cette lecture permet de replacer les deux résultats à leur juste niveau. Dirac est le critère le plus simple à vérifier. Ore est plus souple et englobe Dirac. Mais aucun des deux ne fournit une caractérisation complète.

Condition suffisante et condition nécessaire

Une condition est suffisante lorsqu’elle garantit le résultat :

La condition est vérifiée ⟹ le cycle existe.

Une condition serait nécessaire si tout graphe hamiltonien devait obligatoirement la vérifier :

Le cycle existe ⟹ la condition est vérifiée.

Les conditions de Dirac et d’Ore sont suffisantes, mais elles ne sont pas nécessaires.

Nous retrouvons ainsi la différence profonde entre les mondes d’Euler et de Hamilton. Pour Euler, quelques informations locales fournissent une caractérisation complète. Pour Hamilton, les degrés permettent parfois de conclure avec certitude, mais ils ne disent pas toute l’histoire.

Dirac et Ore sont des certificats d’existence,
pas des détecteurs universels.

Cette distinction a une conséquence très concrète. Lorsqu’un graphe vérifie l’un des deux théorèmes, quelques calculs sur les degrés suffisent. Dans les autres cas, il faut reprendre l’exploration.

Un programme peut précisément organiser ce travail : calculer les degrés, tester d’abord Dirac, examiner ensuite les paires de sommets pour Ore, puis rechercher un cycle seulement si les deux critères restent muets.

Python : garantir d’abord, explorer ensuite

Dans l’article précédent, Python explorait directement les parcours possibles. Cette fois, nous pouvons lui demander de travailler avec davantage de discernement : avant de se lancer dans une recherche potentiellement longue, le programme commence par vérifier si un théorème permet déjà de conclure.

La stratégie suivra trois étapes :

1. tester la condition de Dirac ;
2. si elle échoue, tester celle d’Ore ;
3. si les deux théorèmes restent silencieux, rechercher effectivement un cycle hamiltonien.

Cette organisation respecte exactement la portée des résultats étudiés. Une réponse positive de Dirac ou d’Ore constitue une preuve d’existence. Une réponse négative ne prouve rien : elle oblige simplement le programme à poursuivre son enquête.

Traduire Dirac et Ore en Python

La bibliothèque NetworkX fournit directement le nombre de sommets, les degrés, les voisins et les arêtes du graphe. Les deux théorèmes se traduisent alors presque mot pour mot.

import networkx as nx
from itertools import combinations


def verifier_graphe(G):
    """Vérifie les hypothèses communes à Dirac et Ore."""
    if G.is_directed():
        raise ValueError(
            "Le graphe doit être non orienté."
        )

    if G.is_multigraph():
        raise ValueError(
            "Le graphe ne doit pas contenir d'arêtes multiples."
        )

    if nx.number_of_selfloops(G) > 0:
        raise ValueError(
            "Le graphe ne doit pas contenir de boucle."
        )

    if G.number_of_nodes() < 3:
        raise ValueError(
            "Le graphe doit comporter au moins trois sommets."
        )


def critere_dirac(G):
    """Renvoie True si la condition de Dirac est satisfaite."""
    verifier_graphe(G)

    n = G.number_of_nodes()

    return all(
        degre >= n / 2
        for _, degre in G.degree()
    )


def critere_ore(G):
    """Renvoie True si la condition d'Ore est satisfaite."""
    verifier_graphe(G)

    n = G.number_of_nodes()

    for u, v in combinations(G.nodes, 2):
        if not G.has_edge(u, v):
            if G.degree[u] + G.degree[v] < n:
                return False

    return True

La fonction consacrée à Dirac examine tous les degrés. Dès qu’un sommet possède moins de la moitié des sommets parmi ses voisins, la condition échoue.

Pour Ore, le programme forme toutes les paires de sommets. Il ignore celles qui sont déjà reliées et vérifie seulement les paires non adjacentes. Si l’une d’elles possède une somme de degrés strictement inférieure à n, le critère n’est pas satisfait.

Dans ces deux fonctions, False signifie seulement « ce théorème ne permet pas de conclure ».

Il ne signifie jamais « le graphe n’est pas hamiltonien ».

Lorsque les théorèmes se taisent

Si Dirac et Ore échouent tous les deux, nous retrouvons le monde de l’exploration. Le programme choisit un sommet de départ, avance vers un voisin encore inutilisé et poursuit ainsi jusqu’à avoir visité tout le graphe.

Lorsqu’un choix conduit à une impasse, il efface ce dernier déplacement et revient au sommet précédent. Cette méthode de retour sur trace, souvent appelée backtracking, reproduit la démarche suivie devant « L’ascenseur fou fou fou ! » : avancer, constater un blocage, puis reprendre la recherche au dernier embranchement.

def trouver_cycle_hamiltonien(G):
    """Recherche un cycle hamiltonien par retour sur trace."""
    verifier_graphe(G)

    n = G.number_of_nodes()
    depart = next(iter(G.nodes))

    chemin = [depart]
    visites = {depart}

    def explorer(sommet):
        # Tous les sommets ont été visités.
        if len(chemin) == n:
            return G.has_edge(sommet, depart)

        # On essaie d'abord les voisins les moins connectés.
        voisins = sorted(
            G.neighbors(sommet),
            key=lambda voisin: G.degree[voisin]
        )

        for voisin in voisins:
            if voisin in visites:
                continue

            visites.add(voisin)
            chemin.append(voisin)

            if explorer(voisin):
                return True

            # Impasse : on annule le dernier choix.
            chemin.pop()
            visites.remove(voisin)

        return False

    if explorer(depart):
        return chemin + [depart]

    return None

La condition d’arrêt mérite d’être observée. Visiter tous les sommets ne suffit pas : le dernier sommet du chemin doit encore être relié au point de départ. C’est cette dernière arête qui transforme le chemin hamiltonien en cycle hamiltonien.

L’ordre choisi pour essayer les voisins n’est pas indispensable à la correction du programme. Ici, les sommets de plus faible degré sont examinés en premier. L’idée est de traiter rapidement les sommets qui offrent peu de possibilités, avant qu’ils ne deviennent difficiles à intégrer au cycle.

Un programme qui sait distinguer preuve et recherche

Il reste à réunir les trois étapes dans une seule fonction.

def analyser_graphe(G):
    """Analyse le graphe en privilégiant les théorèmes."""
    dirac = critere_dirac(G)
    ore = critere_ore(G)

    print(f"Dirac : {dirac}")
    print(f"Ore   : {ore}")

    if dirac:
        print(
            "Conclusion : cycle garanti par Dirac."
        )
        return

    if ore:
        print(
            "Conclusion : cycle garanti par Ore."
        )
        return

    print(
        "Les deux théorèmes restent silencieux."
    )
    print(
        "Lancement de la recherche..."
    )

    cycle = trouver_cycle_hamiltonien(G)

    if cycle is None:
        print(
            "Aucun cycle hamiltonien n'a été trouvé."
        )
    else:
        print(
            "Cycle trouvé :",
            " → ".join(map(str, cycle))
        )

La fonction ne cherche donc pas systématiquement un cycle. Si Dirac réussit, elle s’arrête immédiatement. Si Dirac échoue mais qu’Ore réussit, elle s’arrête également. La recherche exhaustive n’intervient qu’en dernier recours.

Les théorèmes répondent à la question « pourquoi le cycle existe-t-il ? »

L’algorithme répond à la question « quel est ce cycle ? »

Le cycle à huit sommets : aucun certificat, mais une solution

Testons le programme sur le cycle à huit sommets rencontré dans la partie précédente.

G = nx.cycle_graph(
    ["A", "B", "C", "D", "E", "F", "G", "H"]
)

analyser_graphe(G)

Le programme affiche :

Dirac : False
Ore   : False
Les deux théorèmes restent silencieux.
Lancement de la recherche...
Cycle trouvé : A → B → C → D → E → F → G → H → A

Ce résultat illustre parfaitement la différence entre l’échec d’un critère et l’absence d’un cycle. Dirac et Ore ne reconnaissent pas ce graphe, car ses sommets ne possèdent que deux voisins. L’exploration retrouve néanmoins immédiatement le cycle qui le constitue.Tester les quatre situations rencontrées dans l’article

Les lignes suivantes construisent successivement le graphe biparti qui satisfait Dirac, le graphe à six sommets accepté seulement par Ore, le cycle à huit sommets et les deux triangles reliés par une arête.

# 1. Le graphe biparti à huit sommets :
#    Dirac et Ore réussissent.

G_dirac = nx.complete_bipartite_graph(4, 4)

noms = {
    0: "A1", 1: "A2", 2: "A3", 3: "A4",
    4: "B1", 5: "B2", 6: "B3", 7: "B4"
}

G_dirac = nx.relabel_nodes(G_dirac, noms)


# 2. Le graphe à six sommets :
#    Dirac échoue, Ore réussit.

G_ore = nx.complete_graph(
    ["B", "C", "D", "E", "F"]
)

G_ore.add_node("A")
G_ore.add_edges_from([
    ("A", "B"),
    ("A", "C")
])


# 3. Le cycle à huit sommets :
#    les deux critères échouent,
#    mais un cycle est trouvé.

G_cycle = nx.cycle_graph(
    ["A", "B", "C", "D", "E", "F", "G", "H"]
)


# 4. Deux triangles reliés par une arête :
#    les critères échouent et aucun cycle
#    hamiltonien n'existe.

G_pont = nx.Graph()

G_pont.add_edges_from([
    ("A", "B"), ("B", "C"), ("C", "A"),
    ("D", "E"), ("E", "F"), ("F", "D"),
    ("C", "D")
])


for nom, graphe in [
    ("Graphe de Dirac", G_dirac),
    ("Graphe d'Ore", G_ore),
    ("Cycle à huit sommets", G_cycle),
    ("Deux triangles reliés", G_pont)
]:
    print()
    print(nom)
    print("-" * len(nom))
    analyser_graphe(graphe)

Une hiérarchie plutôt qu’une opposition

Les théorèmes et l’algorithme ne sont pas deux méthodes concurrentes. Ils n’apportent pas le même type d’information et ne travaillent pas au même niveau.

Cette hiérarchie résume le chemin parcouru dans l’article. Nous avons commencé avec un ascenseur dont il fallait essayer les boutons. Dirac et Ore nous ont ensuite appris que, dans certains graphes, chercher n’est même plus nécessaire pour savoir. Python peut enfin réunir ces deux regards : utiliser d’abord la théorie pour garantir, puis l’exploration pour construire.

Avant d’explorer toutes les routes,
commençons par regarder si un théorème connaît déjà la destination.

Peut-on certifier qu’un cycle hamiltonien n’existe pas ?

Notre programme sait désormais procéder avec méthode. Il teste d’abord Dirac, puis Ore et, lorsque les deux théorèmes restent silencieux, il explore les parcours possibles. S’il termine cette exploration sans trouver de cycle, il peut enfin répondre : ce graphe n’est pas hamiltonien.

Mais faut-il toujours attendre d’avoir essayé toutes les possibilités pour parvenir à cette conclusion ? Peut-on parfois observer la structure du graphe et démontrer immédiatement qu’aucun cycle hamiltonien ne pourra s’y glisser ?

Dirac et Ore fournissent des certificats d’existence.

Certaines ruptures du graphe peuvent, à l’inverse, devenir des certificats d’impossibilité.

Nous ne retrouverons pas pour autant un critère universel comparable à celui d’Euler. Il existe cependant des propriétés que tout graphe hamiltonien doit nécessairement posséder. Dès que l’une d’elles est violée, la recherche peut s’arrêter avant même d’avoir commencé.

Premier obstacle : un sommet qui manque de sorties

Dans un cycle hamiltonien, chaque sommet doit être atteint par une arête, puis quitté par une autre. Deux arêtes distinctes du cycle passent donc par chacun des sommets.

Un sommet isolé, de degré 0, est évidemment inaccessible. Un sommet de degré 1 peut être rejoint, mais il devient impossible de le quitter sans reprendre l’unique arête déjà empruntée.

Condition nécessaire élémentaire

Si un graphe possède un cycle hamiltonien, tous ses sommets ont un degré au moins égal à 2.

Il suffit donc de découvrir un sommet de degré 0 ou 1 pour démontrer la non-existence d’un cycle hamiltonien. Aucun parcours n’a besoin d’être testé.

La réciproque est toutefois fausse. Un degré minimal au moins égal à 2 évite cet obstacle élémentaire, mais ne garantit pas qu’un cycle hamiltonien existe. Une structure peut offrir deux sorties à chaque sommet tout en restant globalement impossible à parcourir.

Un cycle ne supporte aucun passage unique

Imaginons maintenant qu’une arête constitue le seul passage entre deux régions du graphe. Une telle arête est appelée un pont.

Un cycle hamiltonien devrait franchir ce pont pour visiter les sommets situés de l’autre côté. Mais il devrait ensuite revenir dans la première région afin de refermer le cycle. Comme aucun second passage n’existe, il serait obligé d’emprunter deux fois la même arête, ce qui est impossible dans un cycle.

La présence d’un pont interdit l’existence d’un cycle hamiltonien.

Les deux triangles reliés par une unique arête, rencontrés plus tôt dans l’article, illustrent exactement cette situation. L’arête centrale n’était pas seulement peu pratique : elle constituait une preuve immédiate de l’impossibilité.

On peut porter le même regard sur les sommets. Un sommet d’articulation est un sommet dont la suppression déconnecte le graphe. Il joue le rôle d’un carrefour unique entre plusieurs régions.

Or, si un cycle hamiltonien existait, supprimer l’un de ses sommets laisserait un chemin reliant encore tous les autres. Le graphe restant demeurerait donc connecté.

Deux obstacles structurels

• si le graphe contient un pont, il n’est pas hamiltonien ;
• s’il contient un sommet d’articulation, il n’est pas hamiltonien.

Ces observations dépassent le simple comptage des degrés. Un sommet peut posséder plusieurs voisins et rester malgré tout le seul point de passage entre deux parties du graphe. Ce n’est plus sa quantité de connexions qui pose problème, mais la manière dont elles organisent l’ensemble.

Retirer plusieurs sommets pour révéler les coupures

L’idée peut être généralisée. Au lieu de retirer un seul sommet, choisissons un ensemble de sommets que nous noterons S. Le graphe obtenu après leur suppression sera noté G − S.

Supposons que le graphe possède un cycle hamiltonien et que l’on retire k sommets de ce cycle. Celui-ci peut se briser en plusieurs chemins, mais il ne peut produire plus de k morceaux. Chaque sommet retiré crée au plus une nouvelle coupure dans le cycle.

Les éventuelles arêtes supplémentaires du graphe peuvent encore relier certains de ces morceaux. Elles ne peuvent jamais en augmenter le nombre.

Une condition nécessaire plus générale

Si un graphe G est hamiltonien, alors, pour tout ensemble non vide S de sommets, la suppression de S produit au plus autant de composantes connexes que S contient de sommets.

c(G − S) ≤ |S|

La notation c(G − S) désigne le nombre de composantes connexes du graphe après la suppression des sommets de S. La notation |S| désigne le nombre de sommets retirés.

Cette fois encore, la contraposée fournit un certificat de non-existence particulièrement efficace :

S’il existe un ensemble S dont la suppression produit strictement plus de |S| composantes connexes, alors le graphe ne peut pas être hamiltonien.

Pour démontrer qu’un cycle n’existe pas, il suffit donc parfois de retirer quelques sommets bien choisis et de compter les morceaux qui subsistent.

Un graphe sans pont ni articulation, mais pourtant impossible

Considérons cinq sommets répartis en deux groupes :

Premier groupe

U, V

Second groupe

A, B, C

Chacun des sommets A, B et C est relié à U et à V. En revanche, A, B et C ne sont pas reliés entre eux, et aucune arête ne relie U à V. On obtient ainsi le graphe biparti complet K_2,3.

Ce graphe ne contient aucun sommet de degré inférieur à 2. Il ne possède pas de pont : chaque arête appartient à un cycle de longueur 4. Il ne possède pas non plus de sommet d’articulation : la suppression d’un seul sommet ne suffit jamais à le déconnecter.

Les premiers tests ne révèlent donc aucun obstacle.

Retirons maintenant les deux sommets U et V. Les sommets A, B et C restent seuls, sans aucune arête entre eux. Le graphe se décompose alors en trois composantes connexes.

Choix de l’ensemble supprimé

S = {U, V}

|S| = 2  mais  c(G − S) = 3

3 > 2

La condition nécessaire est violée. Il est donc impossible que ce graphe contienne un cycle hamiltonien.

Nous venons ainsi de démontrer la non-existence du cycle sans examiner un seul parcours. L’obstacle n’était visible ni dans le degré minimal, ni dans un pont, ni dans un sommet d’articulation. Il n’apparaissait qu’en supprimant simultanément deux sommets.

Une coupure de deux sommets crée trois morceaux : aucun cycle ne pourra tous les raccorder.

Une autre preuve est possible. Comme ce graphe est biparti, tout cycle doit alterner entre les deux groupes. Un cycle hamiltonien exigerait donc deux groupes de même taille, ce qui n’est pas le cas ici.

Pour aller plus loin : la ténacité d’un graphe

En 1973, le mathématicien Václav Chvátal a formalisé cette résistance aux coupures sous le nom de ténacité, ou toughness en anglais.

Intuitivement, un graphe est d’autant plus tenace qu’il faut supprimer beaucoup de sommets pour le faire éclater en un grand nombre de composantes.

La condition c(G − S) ≤ |S| signifie qu’un graphe est au moins 1-tenace. Tout graphe hamiltonien possède nécessairement cette propriété.

Cette condition reste cependant nécessaire sans être suffisante : elle permet parfois de certifier la non-existence d’un cycle, mais sa vérification ne garantit pas à elle seule que le graphe soit hamiltonien.

Consulter l’article de Václav Chvátal sur les graphes tenaces

Des preuves positives, des preuves négatives… et une zone d’incertitude

Nous disposons maintenant de deux familles d’outils qui fonctionnent en sens opposés.

Cette dernière ligne est essentielle. L’absence d’obstacle visible ne garantit pas l’existence d’un cycle, pas plus que l’échec de Dirac et d’Ore ne prouvait son absence.

Entre les garanties positives et les impossibilités structurelles subsiste donc une vaste région où le graphe refuse de livrer immédiatement son secret. C’est là que d’autres théorèmes, des arguments adaptés à sa structure ou l’exploration algorithmique doivent prendre le relais.

Dirac et Ore disent parfois « oui » sans chercher.
Les coupures disent parfois « non » sans essayer.
Entre les deux commence le véritable territoire de Hamilton.

Conclusion : garantir, interdire… ou reprendre la recherche

Avec Dirac et Ore, le monde de Hamilton paraît soudain devenir un peu plus prévisible. Il n’existe toujours pas de critère général aussi simple que celui d’Euler, mais certains graphes sont suffisamment denses pour que l’existence d’un cycle hamiltonien puisse être affirmée sans en chercher un seul.

Dirac observe le degré de chaque sommet. Ore examine les paires de sommets qui ne sont pas reliés. Dans les deux cas, des informations locales finissent par imposer une conclusion globale : un cycle passant exactement une fois par tous les sommets existe nécessairement.

Nous avons également rencontré le mouvement inverse. Un sommet trop peu connecté, un pont, un sommet d’articulation ou une coupure produisant trop de composantes peuvent démontrer qu’aucun cycle hamiltonien n’est possible. Là encore, il n’est pas nécessaire d’essayer tous les parcours : la structure du graphe suffit à condamner la recherche.

Trois situations, trois démarches

• Dirac ou Ore s’applique : le cycle existe, même si nous ne l’avons pas encore construit.
• Une obstruction structurelle est détectée : le cycle est impossible, sans qu’aucun parcours soit testé.
• Aucun critère ne conclut : il faut poursuivre l’analyse ou explorer les possibilités.

C’est dans cette troisième situation que se trouve l’essentiel de la difficulté. Entre les graphes dont l’hamiltonicité est garantie et ceux qu’un obstacle structurel élimine immédiatement subsiste une immense zone grise. Les degrés y sont trop faibles pour Dirac et Ore, les coupures trop discrètes pour fournir une contradiction, et pourtant le cycle peut exister… ou non.

Nous retrouvons alors Malik devant les boutons de « L’ascenseur fou fou fou ! ». Un premier déplacement semble possible, puis un deuxième. Chaque choix ouvre plusieurs suites, certaines prometteuses, d’autres condamnées bien plus tard. Revenir en arrière reste envisageable sur un petit exercice ; mais que se passe-t-il lorsque le graphe possède des dizaines, des centaines ou des milliers de sommets ?

Lorsque les théorèmes ne répondent ni « oui » ni « non », combien de parcours faut-il examiner avant de connaître la vérité ?

Le problème n’est alors plus seulement de savoir si un cycle hamiltonien existe. Il devient nécessaire de comprendre pourquoi sa recherche peut exiger un nombre vertigineux d’essais, pourquoi quelques sommets supplémentaires suffisent à faire exploser les possibilités et pourquoi aucun raccourci universel efficace n’est aujourd’hui connu.

Dans le prochain article

[4/6] Pourquoi les graphes hamiltoniens sont-ils difficiles ?

Nous quitterons les critères suffisants pour entrer dans la mécanique de la recherche elle-même : multiplication des parcours possibles, retour sur trace, croissance combinatoire et complexité du problème hamiltonien. Il ne s’agira plus seulement de constater que Hamilton oblige parfois à explorer, mais de mesurer à quelle vitesse cette exploration peut devenir hors de portée.

Après avoir appris quand un cycle doit exister et quand il ne peut pas exister, il reste à comprendre pourquoi, entre ces deux certitudes, le trouver est parfois si difficile.