• 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

NEWS

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

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

Précédemment dans « Cultivons-nous… Hamilton »

Une ville traversée par un fleuve. Sept ponts. Et une promenade impossible.

Dans le prologue de cette série, l’héritage d’Euler nous avait appris qu’un problème de parcours pouvait parfois être résolu sans essayer le moindre itinéraire. Pour savoir s’il était possible de traverser chaque pont exactement une fois, il suffisait de regarder les degrés des sommets. Quelques nombres pairs ou impairs, et le verdict tombait.

Puis un nouveau personnage est entré en scène. Dans Hamilton et le jeu icosien, les arêtes ont cédé la vedette aux sommets. Il ne s’agissait plus d’emprunter chaque passage, mais de visiter chaque lieu une seule fois avant de revenir au point de départ. Le décor semblait familier. Les règles, elles, venaient de changer.

Le deuxième épisode, Euler contre Hamilton, révélait alors le véritable piège. Euler permet souvent de diagnostiquer un graphe en examinant ses degrés. Hamilton oblige à construire un parcours dont tous les choix doivent rester compatibles jusqu’au dernier sommet. Un déplacement parfaitement autorisé peut préparer une impasse qui ne se révélera que beaucoup plus tard.

Dans le troisième épisode, deux théorèmes semblaient enfin offrir une issue. Lorsque le graphe est suffisamment bien connecté, Dirac ou Ore peuvent garantir qu’un cycle hamiltonien existe avant même que nous ayons commencé à le chercher. À l’inverse, certains obstacles structurels permettent parfois d’affirmer immédiatement qu’aucun cycle n’est possible.

Mais entre ces deux certitudes subsiste une immense zone grise.

Le cycle existe peut-être.
Peut-être pas.
Et cette fois, les théorèmes ne diront rien de plus.

La théorie a parlé. Puis elle s’est tue.

Il ne reste plus qu’un graphe, une multitude d’embranchements et une question inquiétante : combien de parcours faudra-t-il examiner avant de connaître la vérité ?

Du silence des théorèmes à la forêt des choix

Un théorème comme celui de Dirac ou d’Ore ressemble à un raccourci spectaculaire. On lui présente un graphe, on vérifie quelques conditions sur les degrés, et la conclusion tombe : un cycle hamiltonien existe. Nul besoin de le construire, encore moins d’examiner tous les parcours possibles.

Mais lorsque ces conditions ne sont pas satisfaites, il ne faut surtout pas conclure trop vite. Le théorème ne dit pas que le cycle n’existe pas. Il dit seulement qu’il ne peut pas nous le garantir.

C’est une nuance logique essentielle.

Ne pas disposer d’une preuve d’existence n’est pas disposer d’une preuve d’impossibilité.

Imaginons un graphe dans lequel aucun sommet n’est isolé, aucune coupure évidente ne condamne le parcours et où les degrés restent pourtant insuffisants pour appliquer Dirac ou Ore. Le dessin semble prometteur. Plusieurs chemins s’offrent immédiatement à nous. Certains paraissent même presque dessiner un cycle.

Alors nous choisissons un sommet de départ.

Deux voisins sont accessibles. Nous en sélectionnons un. Depuis ce nouveau sommet, trois directions deviennent possibles. Puis deux autres. À chaque étape, il faut avancer sans revisiter un sommet déjà utilisé, tout en conservant l’espoir de rejoindre finalement le point de départ.

Le problème ne vient pas de la difficulté de chaque décision prise isolément. Choisir un voisin parmi deux ou trois possibilités paraît anodin. Ce sont les conséquences cumulées de ces choix qui deviennent redoutables.

Une branche peut sembler parfaitement viable pendant longtemps. Le parcours visite presque tous les sommets, contourne plusieurs obstacles et paraît toucher au but. Puis, à quelques étapes de la fin, un sommet reste prisonnier à l’écart du cycle. Il n’est plus possible de l’insérer sans repasser par un sommet déjà visité.

Il faut alors revenir en arrière.

Pas seulement d’un sommet, parfois. Le mauvais choix peut avoir été effectué beaucoup plus tôt, à un embranchement qui paraissait sans importance. On défait donc le dernier déplacement, puis le précédent, jusqu’à retrouver une décision encore modifiable. On emprunte une autre branche et l’exploration recommence.

C’est le principe du retour sur trace, ou backtracking, déjà rencontré dans l’épisode précédent. Cette méthode permet d’éviter de poursuivre un chemin dès qu’il est manifestement condamné. Elle est plus intelligente qu’une énumération aveugle de tous les ordres possibles.

Mais elle n’est pas magique.

Dans certains graphes, les impasses apparaissent très vite : l’exploration élimine alors de nombreuses branches presque immédiatement. Dans d’autres, les mauvais parcours ne révèlent leur faiblesse qu’après avoir visité une grande partie des sommets. Le programme peut alors consacrer beaucoup de temps à explorer des pistes qui semblaient toutes raisonnables.

Le dessin initial se transforme peu à peu en un arbre invisible. Son tronc représente le sommet de départ. Chaque embranchement correspond à un choix possible. Chaque nouvelle décision fait naître d’autres branches, qui se divisent à leur tour. Certaines s’interrompent rapidement. D’autres s’enfoncent très loin avant de finir en impasse.

Et quelque part, peut-être, une branche referme enfin le cycle.

La difficulté du problème hamiltonien se cache dans cette forêt des choix. Elle ne saute pas toujours aux yeux sur le dessin. Deux graphes presque semblables peuvent demander des efforts de recherche très différents. Une seule arête ajoutée ou retirée peut ouvrir un raccourci décisif, condamner une famille entière de parcours ou repousser très loin le moment où une erreur devient visible.

Nous voilà donc face à une question plus précise. Ce n’est plus seulement :

Existe-t-il un cycle hamiltonien ?

Mais aussi :

Combien de choix faudra-t-il explorer pour le trouver — ou pour comprendre qu’il n’existe pas ?

Pour mesurer l’ampleur du problème, il suffit maintenant d’ajouter quelques sommets.

Quelques sommets de plus, des millions de parcours

Au premier regard, ajouter un sommet à un graphe paraît être une modification modeste. Un point supplémentaire, quelques arêtes nouvelles, rien qui semble devoir bouleverser le problème.

Pourtant, dans une recherche hamiltonienne, ce sommet ne vient pas simplement s’ajouter à la fin d’un parcours. Il peut prendre place avant le deuxième sommet, après le troisième, entre deux sommets déjà choisis… Chaque nouvelle position possible se combine avec toutes les organisations précédentes.

L'explosion...

Le nombre de parcours envisageables ne grandit donc pas régulièrement. Il explose.

Prenons le cas volontairement extrême d’un graphe complet à n sommets : chaque sommet y est relié à tous les autres. Une fois le sommet de départ fixé, tous les ordres de visite sont possibles. Il faut cependant éviter de compter plusieurs fois le même cycle : commencer la lecture à un autre endroit ne crée pas un nouveau cycle, et parcourir celui-ci dans le sens inverse ne change pas davantage son tracé.

Le nombre de cycles hamiltoniens distincts est alors donné par :

\dfrac{(n-1)!}{2}

Le point d’exclamation désigne ici une factorielle. Ainsi, la factorielle de 7 correspond au produit de tous les entiers de 1 à 7. Cette opération possède une redoutable particularité : sa croissance devient très rapidement vertigineuse.

Entre huit et dix sommets, le nombre de cycles est multiplié par 72. Avec seulement deux sommets supplémentaires, nous passons de quelques milliers de possibilités à près de deux cent mille.

• À douze sommets, il faut déjà compter près de vingt millions de cycles distincts.
• À quinze, plus de quarante-trois milliards.
• À vingt, le nombre dépasse soixante millions de milliards.

Travailler... pendant 2000 ans

Imaginons une machine capable d’examiner un million de parcours chaque seconde, sans jamais ralentir et sans commettre la moindre erreur. Pour parcourir la dernière ligne du tableau, elle devrait travailler pendant près de deux mille ans.

Le détective avait commencé son enquête avec quelques suspects. Il se retrouve désormais face à une foule plus nombreuse que tout ce qu’il pourrait interroger au cours d’une vie.

Dans les problèmes combinatoires, quelques éléments supplémentaires peuvent transformer une recherche raisonnable en exploration démesurée.

Il faut toutefois interpréter ce tableau avec prudence. Un graphe complet n’est pas un exemple difficile pour trouver un cycle hamiltonien : puisque toutes les arêtes existent, presque n’importe quel ordre de visite convient. Le tableau ne mesure donc pas directement le travail nécessaire pour résoudre ce cas particulier.

Révelation

Il révèle autre chose : la taille de l’univers dans lequel une recherche naïve pourrait être contrainte de se déplacer. Dans un graphe quelconque, une grande partie de ces ordres est éliminée parce que certaines arêtes manquent. Mais il reste parfois un nombre immense de parcours partiels qui semblent possibles avant de conduire à une impasse.

Supposons par exemple qu’un programme ait déjà visité dix sommets. Plusieurs prolongements restent disponibles. Il en choisit un, puis un autre, et poursuit jusqu’à ce qu’un sommet devienne inaccessible. Il revient alors au choix précédent, essaie une autre branche, avance de nouveau… Chaque échec élimine une possibilité, mais il peut rester derrière lui des milliers, des millions ou des milliards d’alternatives encore inexplorées.

C’est ici que l’apparence du graphe peut devenir trompeuse. Un dessin comportant vingt sommets tient facilement sur une feuille. L’œil humain les embrasse tous en une seconde. Pourtant, les ordres dans lesquels ils peuvent être visités forment un espace gigantesque, impossible à représenter sur cette même feuille.

Le graphe visible reste petit.

L’arbre des choix, lui, devient colossal.

Cette croissance explique pourquoi une méthode qui fonctionne parfaitement sur dix sommets peut devenir inutilisable ...

TIPS

Avez-vous vu les fonds d'écran du menu informatique/goodies ?

Voir tous les conseils.

Dernière mise à jour:

Nouvelle Page !

• Exercices du jour : Les 16 immeubles !

Pages modifiées (ou corrigées) !

• Exercices du jour : L'enclos
• Exercices du jour : Les carrelages de couleur /a>

Voir toutes les mises à jour.

Trois liens disponibles !

Votre propre message ici, c'est possible! Plus d'informations

Sauf mention contraire, le site est placé sous double licence Creative Commons et GNU Free Documentation License, par contre les grandes images décoratives appartiennent à Corbis et sont licenciées par microsoft

Contact: w0uf@free.fr (avec un zéro à la place du O)