• Home
  • Home
  • Wouf's Blog
  • Bibliowouf
  • Boutique TShirt
  • Sponsoring
  • Politique de confidentialié
• Math
  • Math au collège
  • Applis et boutiques
  • Cours particuliers
• Jeux
  • Echecs
  • Poker
  • Des chiffres et des lettres
  • Dogs and cats (mastermind)
  • boggle - version Anglaise
  • boggle - version Française
• Info
  • Console Python
  • SVG EDIT
  • fond d'écran
  • Prénom en chinois
  • Boite à outils
  • Mes Logiciels
  • DIVERS
  • Webmaster?
  • Liens

Tweet

 

NEWS

• Page : https://site2wouf.fr/clubelo2005.php
• Catégorie : Non définie

[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.

Nombre de sommets	Seuil donné par Dirac	Condition à vérifier
6	6 ÷ 2	au moins 3 voisins par sommet
7	7 ÷ 2	au moins 4 voisins par sommet
8	8 ÷ 2	au moins 4 voisins par sommet
10	10 ÷ 2	au moins 5 voisins par sommet

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.

---

Pour aller plus loin : l’idée de la preuve

Choisissons dans le graphe un chemin aussi long que possible et notons ses deux extrémités A et B. Puisque ce chemin est maximal, aucun voisin de A ou de B ne peut se trouver à l’extérieur du chemin : sinon, il suffirait d’ajouter ce sommet pour obtenir un chemin plus long.

A possède au moins n ÷ 2 voisins sur le chemin et B en possède au moins autant. En observant la position de ces voisins le long du parcours, on montre que deux connexions doivent nécessairement permettre de refermer le chemin en un cycle passant par tous ses sommets.

Si ce cycle ne contenait pas encore les n sommets du graphe, la forte connexité imposée par la condition de Dirac permettrait de le rouvrir vers un sommet extérieur et de construire un chemin plus long. Cela contredirait le choix initial. Le cycle contient donc tous les sommets : il est hamiltonien.

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.

L...

lien vers l'article sur wouf blog