Superpermutations

3. La théorie des graphes à la rescousse

Une approche pour modéliser et tenter de résoudre le problème qui semble porter ses fruits utilise la théorie des graphes. Nous allons montrer comment modéliser le problème à l'aide du graphe des permutations, et présenter les résultats que cela a pu apporter.

Donnons-nous un alphabet \Sigma_n. Le graphe des permutations est un graphe orienté dont les sommets sont les permutations de \Sigma_n. Un arc relie un sommet \sigma_1 à un sommet \sigma_2 s'il existe un mot \omega\in\Sigma_n^* tel que \omega est un préfixe de \sigma_1 et un suffixe de \sigma_2.

Par exemple, avec \Sigma_3={1,2,3}, un arc relie le sommet 321 au sommet 132 puisque le mot 32 est un préfixe de 321 et un suffixe de 132. En revanche les mots 231 et 321 ne sont pas reliés par un arc puisqu'il n'existe de pas de mot qui soit à la fois un suffixe de l'un et un préfixe de l'autre. On peut dessiner le graphe de \Sigma_3 :

Graphe des permutations de \Sigma_3.

Le poids de chaque arc correspond à la longueur du mot suffixe/préfixe des sommets reliés. Par exemple, un arc relie le mot 123 au mot 231 car le mot 1 (de taille 1) est préfixe de 123 et suffixe de 231. De plus, l'arc qui relie 231 à 123 est de poids 2 car le mot 23 (de taille 2) est préfixe de 231 et suffixe de 123.

Eh bien l'on peut montrer que trouver le plus court circuit qui passe par tous les sommets exactement une fois (on parle de chemin hamiltonien) sur le graphe des permutations d'un alphabet de taille n revient à trouver une superpermutation de taille minimale.

L'image suivante montre le chemin hamiltonien (en rouge) qui correspond à la superpermutation 123121321.

Un chemin hamiltonien sur le graphe des permutations de \Sigma_3.

En effet, on parcourt dans l'ordre

    \[ 123\to231\to312\to213\to132\to321 \]

puis on concatène les permutations en retirant les chevauchements comme expliqué avec l'algorithme de la partie précédente.

Malheureusement, même en changeant l'approche, le problème est encore loin d'être résolu. Le problème du chemin hamiltonien est NP-complet, et la taille des graphes des permutations suit une croissance factorielle (il y a autant de sommets que de permutations !)

Bibliographie

1 Cliquer pour recommander cet article