Codage de Prüfer
# 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 $P=(x_{1},x_{2},x_{3},...,x_{n-2})$ 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 :

### 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 $P=(4,4,4,5)$.

## Décodage - Première méthode

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

### Algorithme

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

### Exemple

Considérons la suite $P=(4,4,4,5)$. 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 $x_1$ = 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 $x_2$ = 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 $x_3$ = 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 $x_4$ = 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 $D$ des degrés de chaque sommet, on peut utiliser une suite $I$ des sommets que l'on n'a pas encore traités.

### Algorithme

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

### Exemple

Considérons la suite $P=(4,4,4,5)$. 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 $n^{n-2}$. La figure ci-contre permet de voir qu'il existe effectivement $2^{0}$, $3^{1}$ et $4^{2}$ 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 $n^{n-2}$ é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 $K_{n}$ de degrés $d_{1},d_{2},\dots ,d_{n}$ est égal au coefficient multinomial ${\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots (d_{n}-1)!}}$.

La démonstration s'appuie sur le fait que, dans la suite de Prüfer, le numéro $i$ apparaît exactement $d_{i}-1$ fois.

