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 $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^[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 | modifier le code]

Note : tous les exemples qui suivent se réfèrent à l'arbre T ci-contre.

Algorithme[modifier | modifier le code]

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 | modifier le code]

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[modifier | modifier le code]

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

Algorithme[modifier | modifier le code]

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 x_i de P
    Augmenter de 1 le degré du sommet numéroté x_i dans D
Fin Pour chaque
Pour chaque valeur x_i 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 x_i en j au graphe T
    Diminuer de 1 les degrés de x_i et de j dans D
Fin Pour chaque
Ajouter l'arête reliant les deux sommets restants de degré 1

Exemple[modifier | modifier le code]

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₁ = 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₂ = 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₃ = 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₄ = 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 | modifier le code]

À 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[modifier | modifier le code]

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 | modifier le code]

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[modifier | modifier le code]

Article principal : 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[modifier | modifier le code]

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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

↑ ^{a et b} Codage de Prüfer sur Apprendre en ligne.net, Didier Müller, 10 février 2003
↑ (de) Prüfer, H., « Neuer Beweis eines Satzes über Permutationen », Arch. Math. Phys., vol. 27,‎ 1918, p. 742–744
↑ (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),‎ 2001, p. 343–350 (lire en ligne)

Bibliographie additionnelle[modifier | modifier le code]

(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 » (n^o 11417), 2019 (ISBN 978-3-030-13434-1, DOI 10.1007/978-3-030-13435-8_3), p. 43–54.

[ael-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,‎ 1918, 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),‎ 2001, p. 343–350 (lire en ligne)

[1]

[2]

[3]