Codage de Prüfer

En mathématiques, le codage de Prüfer est une méthode pour décrire de façon compacte un arbre dont les sommets sont numérotés[1]. Ce codage représente un arbre de n sommets numérotés avec une suite de n-2 termes. Une suite P donnée correspond à un et un seul arbre numéroté de 1 à n.

Les suites de Prüfer ont été utilisées pour la première fois par Heinz Prüfer pour démontrer la formule de Cayley en 1918[2]. On peut aussi les utiliser en programmation informatique pour enregistrer la structure d'un arbre de façon plus compacte qu'avec des pointeurs[réf. nécessaire].

Codage

Un arbre dont le codage de Prüfer donne (4, 4, 4, 5).
Note : tous les exemples qui suivent se réfèrent à l'arbre T ci-contre.

Algorithme

La suite de Prüfer est construite à l'aide de l'algorithme suivant :

Données : Arbre T
Tant qu'il reste plus de deux sommets dans l'arbre T
    Identifier la feuille v de l'arbre ayant le numéro minimum
    Ajouter à la suite P le seul sommet s adjacent à v dans l'arbre T
    Enlever de l'arbre T le sommet v et l'arête incidente à v
Fin Tant que

Exemple

Considérons l'arbre de la figure au-dessus.

Au départ, 1 est la feuille de numéro minimum, c'est donc elle qu'on retire en premier, et l'on met 4 (le numéro de la branche à laquelle elle était raccordée) dans la suite de Prüfer.

Les sommets 2 et 3 sont les suivants à être enlevés et on ajoute encore deux fois 4 à la suite de Prüfer.

Le sommet 4 est à présent une feuille et a le numéro le plus bas, donc on le retire et l'on ajoute 5 (la branche à laquelle il était raccordé) à la fin de la suite.

Il ne reste plus que deux sommets, donc on s'arrête. La suite de Prüfer codant l'arbre est .

Décodage - Première méthode

Cet algorithme s'appuie sur une suite des degrés de chaque sommet de l'arbre .

Algorithme

L'arbre peut être reconstruit à l'aide de l'algorithme inverse suivant[3] :

Données : suite de Prüfer P de longueur n – 2
Créer un graphe T composé de n sommets isolés numérotés de 1 à n
Créer une suite D composée de n valeurs toutes à 1, appelées degrés
Pour chaque valeur xi de P
    Augmenter de 1 le degré du sommet numéroté xi dans D
Fin Pour chaque
Pour chaque valeur xi de P
    Trouver le sommet de degré 1 qui a le plus petit numéro, soit j ce numéro
    Ajouter l'arête allant de xi en j au graphe T
    Diminuer de 1 les degrés de xi et de j dans D
Fin Pour chaque
Ajouter l'arête reliant les deux sommets restants de degré 1

Exemple

Considérons la suite . Il faut qu'elle nous permette de reconstruire l'arbre de la figure au-dessus.

Dans une première phase, on crée un graphe à six sommets isolés numérotés de 1 à 6. On leur attribue à tous un degré par défaut égal à 1. Ensuite, on parcourt P en augmentant le degré des sommets qui y figurent : on augmente trois fois le degré du sommet 4 et une fois le degré du sommet 5. Finalement, on a les degrés D = (1, 1, 1, 4, 2, 1).

Dans la phase suivante, on parcourt à nouveau P :

  • Pour x1 = 4, on cherche le sommet de numéro le plus faible de degré égal à 1. C'est le sommet numéro 1 et l'on relie les sommets 1 et 4, tout en diminuant leurs degrés. On a à présent les degrés D = (0, 1, 1, 3, 2, 1).
  • Pour x2 = 4, on cherche le sommet de numéro le plus faible de degré égal à 1. C'est le sommet numéro 2 et l'on relie les sommets 2 et 4, tout en diminuant leurs degrés. On a à présent les degrés D = (0, 0, 1, 2, 2, 1).
  • Pour x3 = 4, on cherche le sommet de numéro le plus faible de degré égal à 1. C'est le sommet numéro 3 et l'on relie les sommets 3 et 4, tout en diminuant leurs degrés. On a à présent les degrés D = (0, 0, 0, 1, 2, 1).
  • Pour x4 = 5, on cherche le sommet de numéro le plus faible de degré égal à 1. C'est le sommet numéro 4 et l'on relie les sommets 4 et 5, tout en diminuant leurs degrés. On a à présent les degrés D = (0, 0, 0, 0, 1, 1).

Enfin, on relie les deux sommets restants de degré 1, à savoir les sommets de numéros 5 et 6. On a bien reconstitué l'arbre T original.

Décodage - seconde méthode

À la place d'une suite des degrés de chaque sommet, on peut utiliser une suite des sommets que l'on n'a pas encore traités.

Algorithme

L'arbre peut être reconstruit à l'aide de l'algorithme inverse suivant[1] :

Données : suite de Prüfer P de longueur n – 2
Créer un graphe T composé de n sommets isolés numérotés de 1 à n
Créer une suite I des numéros de 1 à n
Tant qu'il reste des éléments dans P et plus de deux éléments dans I
    Soit s le premier élément de la suite P
    Identifier le plus petit élément j de I n'apparaissant pas dans la suite P
    Ajouter l'arête allant de j à s
    Enlever j de I et s de P 
Fin Tant que
Ajouter l'arête reliant les deux sommets restant dans I

Exemple

Considérons la suite . Il faut à nouveau qu'elle nous permette de reconstruire l'arbre de la figure au-dessus.

Au départ, I = (1, 2, 3, 4, 5, 6). Ensuite :

  • Le premier élément de P est 4 et le plus petit élément de I n'apparaissant pas dans P est 1. On relie les sommets 1 et 4 dans T et on les retire respectivement de I et de P. À ce stade, I = (2, 3, 4, 5, 6) et P = (4, 4, 5).
  • Le premier élément de P est 4 et le plus petit élément de I n'apparaissant pas dans P est 2. On relie les sommets 2 et 4 dans T et on les retire respectivement de I et de P. À ce stade, I = (3, 4, 5, 6) et P = (4, 5).
  • Le premier élément de P est 4 et le plus petit élément de I n'apparaissant pas dans P est 3. On relie les sommets 3 et 4 dans T et on les retire respectivement de I et de P. À ce stade, I = (4, 5, 6) et P = (5).
  • Le seul élément de P est 5 et le plus petit élément de I n'apparaissant pas dans P est 4. On relie les sommets 4 et 5 dans T et on les retire respectivement de I et de P. À ce stade, I = (5, 6) et P est vide.

On relie enfin les sommets restants 5 et 6. On a bien reconstitué l'arbre T original.

Démonstration de la formule de Cayley

Il y a respectivement 1, 3 et 16 arbres décorés à 2, 3 et 4 sommets.

En science combinatoire, la formule de Cayley affirme que le nombre d'arbres « décorés » (numérotés) à n sommets est . La figure ci-contre permet de voir qu'il existe effectivement , et arbres décorés distincts à 2, 3 ou 4 sommets respectivement.

Principe de la démonstration

On montre d'abord que :

  • pour un arbre T, il existe une seule suite de Prüfer P décrivant T ;
  • pour une suite P donnée de longueur n – 2, il y a un seul graphe T numéroté de 1 à n dont la suite de Prüfer est P, et c'est un arbre.

Le codage de Prüfer fournit donc une bijection entre l'ensemble des arbres numérotés à n sommets et l'ensemble des suites de longueur n – 2 composées de valeurs dans l'intervalle [1, n]. Comme ce dernier possède éléments, et comme le codage de Prüfer est bijectif, cela démontre la formule de Cayley.

Extension

On peut aller plus loin et prouver que le nombre d'arbres couvrant un graphe complet de degrés est égal au coefficient multinomial .

La démonstration s'appuie sur le fait que, dans la suite de Prüfer, le numéro apparaît exactement fois.

Notes et références

  1. Codage de Prüfer sur Apprendre en ligne.net, Didier Müller, 10 février 2003
  2. (de) Prüfer, H., « Neuer Beweis eines Satzes über Permutationen », Arch. Math. Phys., vol. 27, , p. 742–744
  3. (en) Jens Gottlieb, Bryant A. Julstrom, Günther R. Raidl, and Franz Rothlauf., « Prüfer numbers: A poor representation of spanning trees for evolutionary search », Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), , p. 343–350 (lire en ligne)

Bibliographie additionnelle

(en) Vadim Lozin, « From Words to Graphs, and Back », dans C. Martín-Vide, A. Okhotin, et D. Shapira (éditeurs), Language and Automata Theory and Applications. LATA 2019, Springer Cham, coll. « Lecture Notes in Computer Science » (no 11417), (ISBN 978-3-030-13434-1, DOI 10.1007/978-3-030-13435-8_3), p. 43–54.

  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.