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. 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. On peut aussi les utiliser en programmation informatique pour enregistrer la structure d'un arbre de façon plus compacte qu'avec des pointeurs.

Codage

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 :

 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 :

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

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

Bibliographie additionnelle 
.

Arbre (graphe)
Structure de données en théorie des graphes