Codage de Prüfer

méthode pour décrire de façon compacte un arbre dont les sommets sont numérotés

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 modifier

 
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 modifier

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 modifier

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 modifier

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

Algorithme modifier

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 modifier

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 modifier

À 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 modifier

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
    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 modifier

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 modifier

 
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 modifier

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 modifier

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 modifier

  1. a et b 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 modifier

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