Icosien : Un jeu de théorie des graphes

 Neutre : accessible à tous

Niveau 4 du jeu "Icosien" de Neamar

Icosien ¹ est un jeu de réflexion basé sur la théorie des graphes. Il fut inventé en 1857 par W.R.Hamilton (1805-1865), mathématicien génial qui - entre autres - reformula la mécanique dans un formalisme qui porte maintenant son nom, et créa les quaternions (que nous verrons dans un prochain article sur les nombres).


Nous nous intéresserons dans cet article à une adaptation en flash de ce jeu, réalisée par Neamar. Plus précisément, nous allons voir quelques explications des principes mathématiques qui se cachent derrière et une méthode de résolution des deux derniers niveaux du jeu.

ATTENTION SPOILER ALERT !

Si vous ne connaissez pas ce jeu, ne lisez pas l'article avant de l'avoir essayé !  

Jouer d'abord au jeu Icosien de Neamar.

Vous avez aimé ce jeu et aimeriez en savoir plus sur la théorie des graphes ? Vous vous êtes arraché les cheveux sur les deux derniers niveaux et souhaitez en voir une solution détaillée ? Alors suivez le guide...

Les graphes Eulériens

La première partie du jeu est plutôt facile et n'est qu'un échauffement. Il s'agit de trouver des cycles eulériens.
Un graphe est dit "Eulérien" lorsqu'il admet un cycle eulérien : on peut « parcourir » le graphe en partant d'un sommet quelconque et en passant exactement une fois par chaque arête (et donc forcément par chaque sommet au moins une fois, parfois plus) pour revenir au sommet de départ. Dit autrement, on peut le tracer sans lever le crayon.
Il est interdit de repasser deux fois par la même arête, ou de relier deux sommets qui ne sont pas liés par une arête. En revanche il est possible de croiser les fils.

Un théorème fondamental, dû je vous le donne en mille à... Leonard P.Euler (1707-1783), affirme qu'un graphe est eulérien si et seulement si de tout sommet part un nombre pair d'arêtes ² (on dit que le sommet est de degré pair).

Ainsi, lorsqu'un graphe ne possède que des sommets de degré pair, nous pouvons partir de n'importe quel sommet et y revenir en ayant parcouru toutes les arêtes ! C'est le cas du niveau 1 qui sert d'exemple ainsi que des niveaux 4, 6, 7 et 8 qui sont donc très faciles.

Niveau 6

Lorsqu'un graphe possède des sommets de degré pair et de degré impair, il n'est pas eulérien. En revanche, il suffit qu'il possède exactement deux sommets de degré impair (ni plus ni moins) pour pouvoir partir de l'un et arriver à l'autre en ayant parcouru toutes les arêtes (nous avons alors un chemin eulérien). Le graphe est "presque eulérien" puisqu'il suffit de relier les sommets de départ et d'arrivée pour qu'il le devienne.
C'est le cas des niveaux 2, 3, 5 et 9. Ceux-ci sont assez faciles à condition de partir d'un sommet de degré impair ! Le niveau neuf peut poser problème si l'on ne remarque pas les deux sommets en question...

Niveau 9

En conclusion, déterminer si un graphe admet un chemin eulérien - et le tracer - est très facile puisqu'il suffit de compter le degré de chaque sommet.

Les graphes Hamiltoniens

A partir du niveau 10 (qui sert d'exemple), les règles changent. On demande maintenant au joueur de parcourir non plus toutes les arêtes, mais tous les sommets. Pas de problème a priori, cela ne devrait pas être bien plus difficile ! Grosse erreur. Nous allons voir que ce problème peut devenir arbitrairement difficile.

Un graphe est dit "Hamiltonien" lorsqu'il admet un cycle hamiltonien : on peut parcourir le graphe en passant par tous les sommets une seule fois et revenir au sommet de départ. Il peut exister plusieurs solutions différentes et il n'existe pas de théorème simple qui caractérise les graphes hamiltoniens, contrairement aux graphes eulériens.
Si tous les graphes de la première partie du jeu ne sont pas eulériens (certains sont presque eulériens comme nous l'avons vu et admettent non pas un cycle mais un chemin eulérien), tous les graphes du reste du jeu sont hamiltoniens.

Les niveaux 10, 11 et 12 sont faciles et ne servent qu'à se familiariser avec les cycles hamiltoniens. Le 13 demande à anticiper le fait que l'on doit revenir au sommet de départ mais reste facile. Le 14 et le 15 sont a peine plus subtils.

Niveau 14

Le 16 n'est pas difficile non plus. Le 17 est un peu astucieux et le 18 se fait bien après quelques essais. En revanche dès que l'on arrive au 19, ce n'est plus du tout la même histoire.
S'il peut certainement être résolu par essais/erreurs, il est toutefois bien plus complexe que les autres.

Le niveau 19

Niveau 19

Une méthode pour trouver un cycle hamiltonien dans un graphe consisterait à essayer tous les chemins... Faisable pour les niveaux précédents, cette méthode prendrait un temps fou pour ce niveau et plus encore pour le suivant !
Essayons plutôt de diviser pour régner : coupons le graphe en sous-graphes et résolvons d'abord ces graphes partiels. Cette méthode est particulièrement adaptée au niveau 19 puisqu'il est constitué de trois sous-graphes identiques, celui du haut, de gauche et de droite, qui ont cette forme :

Morceau du niveau 19

Notons toutefois que celui de droite n'est pas rattaché par le même nombre d'arêtes, un sommet ayant été enlevé par le concepteur du jeu ³... ce qui rend le problème plus difficile a première vue, mais va en revanche faciliter la tâche avec notre méthode.

Etape 1 :

Listons quelques chemins hamiltoniens dans le morceau de graphe. Pas besoin d'être exhaustif, une dizaine de possibilités devraient nous permettre de trouver au moins une solution générale. Nous verrons exactement combien de solutions différentes nous donne cette liste (incomplète). Par souci de concision, nous n'avons pas pris en compte les chemins symétriques de ceux listés, qui augmenteraient donc encore le nombre de solutions finales. Pour bien différencier les chemins, nous avons tracé le premier en rouge, et les suivants arborent en bleu les arêtes qui diffèrent du premier chemin.

Chemin Hamiltonien partiel n°1

Chemin Hamiltonien partiel n°2

Chemin Hamiltonien partiel n°3

Chemin Hamiltonien partiel n°4

Chemin Hamiltonien partiel n°5

Chemin Hamiltonien partiel n°6

Chemin Hamiltonien partiel n°7

Chemin Hamiltonien partiel n°8

Chemin Hamiltonien partiel n°9

Chemin Hamiltonien partiel n°10

Chemin Hamiltonien partiel n°11

Etape 2 :

Faisons le tri. Remarquons déjà que notre chemin numéro 5 est un cycle, nous pouvons tout de suite l'éliminer. Commençons par le sous-graphe du haut. Les quatre premiers chemins ainsi que les 7, 9, 10 et 11 ne conviennent pas car aucun (de ceux que nous avons listé) ne pourrait alors aller à droite, à cause du sommet manquant. Il nous reste donc le 6 et le 8 pour le sous-graphe du haut. Nous avons coloré en vert les arêtes qui seront nécessairement utilisées dans le cycle hamiltonien basé sur ces sous-graphes :

Possibilités avec le sous-graphe 6

Possibilités avec le sous-graphe 8

Ces sous-graphes étant quasiment identiques, ils offrent les mêmes possibilités. Au final, nous pouvons énumérer les solutions suivantes sous la forme de trois chiffres (a,b,c) avec a représentant le numéro du graphe du haut, b celui de droite et c celui de gauche :

(6,1,2); (6,1,3); (6,1,7); (6,1,9); (6,1,11); (6,4,2); (6,4,3); (6,4,7); (6,4,9); (6,4,11); (6,10,2); (6,10,3); (6,10,7); (6,10,9); (6,10,11);
(8,1,2); (8,1,3); (8,1,7); (8,1,9); (8,1,11); (8,4,2); (8,4,3); (8,4,7); (8,4,9); (8,4,11); (8,10,2); (8,10,3); (8,10,7); (8,10,9); (8,10,11);

Solution (6,10,11) proposée par Neamar

Solution (6,1,7) proposée par un ami (merci Pierre !)

Il existe donc de nombreuses solutions différentes, au moins 30, et plus encore si nous considérons les chemins symétriques (attention toutefois, il ne faut pas doubler ce nombre car le graphe n'est pas symétrique !). Remarquons toutefois que les solutions ne diffèrent que très localement.

Le niveau 20

Niveau 20

Au premier regard, ce niveau semble infaisable. Si l'on essaye à tâtons de le résoudre, on craint d'y passer du temps et de s'arracher les cheveux. Celui-ci pas moyen de le découper en sous-graphes... Alors comment faire ?
Eh bien contrairement aux apparences, il est possible de simplifier considérablement ce graphe, puisqu'il possède beaucoup de sommets de degré 2. Ceux-ci sont une aubaine puisque comme tous les sommets doivent être parcourus, les arêtes de ceux de degré 2 le seront forcément ! Nous pouvons donc supprimer temporairement ces sommets et les remplacer chacun par une nouvelle arête. Alors allons-y, simplifions :

Etape 1 :

Tout d'abord, comptons les degrés des sommets pour repérer ceux que nous pourrons supprimer :

Il y a 10 sommets de degré 2

Etape 2 :

Repérons les arêtes qui seront forcément parcourues :

Arêtes inévitables

Supprimons les arêtes inutiles et ainsi réduisons le degré de certains sommets

Arêtes inutiles supprimées

Et recommençons

De nouvelles arêtes inévitables

Et recommençons encore jusqu'à ce qu'il n'y ait plus de sommet de degré 2

Encore des arêtes inévitables

Etape 3 :

Il ne reste plus qu'à remplacer chaque chemin en rouge par une nouvelle arête (bleue par exemple) et supprimer les sommets correspondants.

Etape 4 :

Recommencer les étapes 2 et 3 tant que possible.

Simplification du graphe

Et voilà le résultat final, le graphe à été simplifié au maximum... Il fait nettement moins peur !

Niveau 20 simplifié

Etape 5 :

Résoudre le graphe simplifié. Et il possède exactement une solution :

Solution simplifiée

Etape 6 :

Reporter les arêtes vertes dans le graphe de départ (chemins rouges) pour obtenir la solution générale. Il manque deux arêtes car la simplification a été effectuée plusieurs fois (étape 4), ce sont les arêtes bleues.

Solution générale

Et nous pouvons tracer le cycle hamiltonien dans le jeu :

Conclusion

Alors, faciles les problèmes de théorie des graphes ? Certainement pas ! Contrairement aux chemins eulériens, trouver un cycle hamiltonien est un problème NP-complet, c'est-à-dire algorithmiquement difficile. Actuellement il n'existe pas d'algorithme permettant de trouver un cycle hamiltonien dans n'importe quel graphe en un temps raisonnable (il est toujours possible d'essayer tous les chemins mais c'est bien trop long en général !). Les niveaux 19 et 20 du jeu Icosien illustrent bien cette difficulté : nous avons dû utiliser deux méthodes complètement différentes pour les résoudre. En effet, le niveau 19 n'est pas simplifiable comme le 20 (on ne peut supprimer qu'un seul sommet de cette manière...) et le niveau 20 n'est pas décomposable en sous-graphes comme le 19.

Nous avons utilisé deux heuristiques différentes. Une heuristique est un algorithme qui fournit rapidement une solution réalisable, mais pas nécessairement optimale. On peut très bien ne pas trouver de solution par cet algorithme (exemple : simplifier le niveau 19 ne mène à rien).

Pour finir, saluons le concepteur de ce jeu, Neamar, ainsi que le graphiste Licoti, pour ce qui est certainement le plus beau jeu de graphe sur le net !

Notes :

1. A l'origine, le jeu consistait à illustrer des propriétés de symétrie de l'icosaèdre (et du dodécaèdre, les deux possédant les même symétries), d'où le terme "icosien".

2. Ce théorème est valable pour les graphes connexes, c'est à dire d'un seul tenant. Nous ne considérons que des graphes connexes dans ce jeu.

3. Le concepteur, Neamar, est partit de graphes hypohamiltoniens (dont la propriété est de devenir hamiltonien après avoir enlevé n'importe quel sommet) dans certains niveaux. C'est le cas des graphes des niveaux 15, 16 et 19 auquel il a donc enlevé un sommet.

Tweeter