SnowCode

Nous allons ici voir comment représenter un arbre de manière très compacte à l'aide du code de Prüfer.

Le codage de Prüfer est une manière très compacte de représenter un arbre. Elle permet très facilement de retrouver l'arbre de manière unique à partir de son codage mais est peu pratique pour parcourir l'arbre.

Le code de Prüfer est une suite de nombre qui fait une taille correspondant au nombre de sommet, moins 2. Donc si on a un graphe à 10 sommet, la suite du code fera une longueur de 8.

En sachant cela on peut également faire une déduction sur les arbres en général. Si on sait que l'on a 8 sommets, on sait que la taille du code de Prüfer sera 6. On peut alors calculer le nombre de permutations (soit d'arbres possibles) avec ces 8 sommets, qui est de 8^6, soit 262 144 arbres possibles. On peut donc en déduire que le nombre d'arbres possibles avec un nombre de sommets donné est n^{n-2}.

Codage de Prüfer

Le codage de Prüfer consiste à répeter les étapes suivantes jusqu'a ce qu'il ne reste plus que deux sommets dans l'arbre :

1. Identifier la feuille de l'arbre avec le numéro minimum
2. Ajouter le sommet adjacent de la feuille dans la suite
3. Enlever la feuille de l'arbre

Décodage de Prüfer

Pour décoder la suite, il suffit alors de connaître la liste des sommets et le code. Il faut alors répeter les étapes suivantes jusqu'a ce qu'il ne reste plus que deux éléments dans la suite :

1. Identifier le plus petit élément de la liste des sommets qui n'est pas dans le code (la suite)
2. Relier le premier élément de la suite au sommet identifié
3. Enlever le premier élément de la suite et le sommet identifié

Une fois qu'il ne reste plus que deux éléments, il suffit alors de les relier.

Voici la description de l'exemple ci-dessus étape par étape :

1. Situation initiale, on a un code S de S = {2,3,3,3} et une liste de sommets allant de 1 à 6.
2. On prends le plus petit sommet qui ne fait pas partie du code (1), et on le lie au premier sommet du code (2). Enfin on supprime 1 de la liste des sommets et 2 du code
3. On prends le plus petit sommet qui ne fait pas partie du code (2), et on le lie au premier sommet du code (3). Enfin on supprime 2 de la liste des sommets et 3 du code
4. On prends le plus petit sommet qui ne fait pas partie du code (4), et on le lie au premier sommet du code (3). Enfin on supprime 4 de la liste des sommets et 3 du code
5. On prends le plus petit sommet qui ne fait pas partie du code (5), et on le lie au premier sommet du code (3). Enfin on supprime 5 de la liste des sommets et 3 du code
6. Enfin, on relie les deux derniers sommets qui sont 5 et 6.

L'arbre està présent reconstitué.