Codage de Prüfer

Prenons un arbre dont les sommets de taille $n$ dont les sommets sont étiquetés de $0$ à $n-1$. Le codage de Prüfer ne pourra contenir que des nombres entiers de $0$ à $n-1$ et il formera une séquence de $n-2$ nombres.

Partant d'un arbre, on peut établir le code de Prüfer. Dans l'autre sens, partant du code, on peut reconstruire l'arbre.

Exemple

Prenons les trois arbres ci-dessous.

Remarquez que ces trois arbres sont les mêmes. Seules les connexions comptent et un arbre est simplement un graphe connexe, non orienté et sans cycle.

Cette définition des arbres est un peu plus générale que celle vue en classe. Vu de cette façon, il n'y a pas de parents, d'enfants ou de racine. Vous pouvez imaginer l'arbre comme des perles accrochées avec des ficelles. Dans la figure de gauche, on a simplement suspendu l'arbre par la perle étiquetée 1 ce qui revient à sélectionner 1 comme racine. Mais on aurait aussi bien pu suspendre l'ensemble à la parle 7 (arbre de droite) et alors 7 aurait été la racine.

Ces trois représentations d'un même arbre contiennent des sommets étiquetés de $0$ à $7$, donc $n = 8$. Dans ce cas le codage de Prüfer sera : $(1, 2, 0, 4, 1, 2)$.

Un code de Prüfer identifie un arbre de façon unique : Les deux arbres représentés ci-dessus sont identiques, ils auront donc le même code de Prûfer. De plus, toutes les séquences de $n-2$ nombres sont valables et représentent un arbre différents. Cela signifie qu'il y a $8^6 = 262\,144$ arbres. En général, il existe $n^{n-2}$ arbres de taille $n$. C'est pour le démontrer que Prüfer a inventé son code.

De l'arbre au code

Soit $T$ un arbre dont les $n$ sommets sont étiquetés de $0$ à $n-1$. On veut produire le code de Prüfer sous forme d'une séquence $P$.

FONCTION code
ENTRÉE: arbre T
SORTIE: code P
DÉBUT
    Initialiser P comme séquence vide
    TANT QUE T comporte encore au moins 2 sommets, FAIRE
        sélectionner la feuille de T ayant l'étiquette la plus petite
        soit v le voisin de cette feuille,
        ajouter v à la séquence P
        enlever la feuille de T
    FIN TANT QUE
    RENVOYER P
FIN

Vous pouvez vérifiez que l'arbre donné en exemple produit bien le code $(1, 2, 0, 4, 1, 2)$.

Du code à l'arbre

Soit $P$ un code de Prüfer, c'est à dire une séquence de $n-2$ nombres dont les valeurs peuvent être choisies de $0$ à $n-1$. On veut obtenir l'arbre $T$ correspondant.

FONCTION decode
ENTRÉE: code P
SORTIE: arbre T
DÉBUT
    soit n égale à taille de P + 2
    créer arbre T composé de n sommets isolés (aucune connexion)
    créer une séquence D composée de n valeurs toutes à 1, appelées degrés
    POUR CHAQUE valeur s dans P
        augmenter de 1 le degré du sommet numéroté s dans D
    FIN
    POUR CHAQUE valeur s dans P
        sélectionner le premier indice f de degré 1 dans D
        ajouter dans T une arête entre s et f
        dans D, diminuer de 1 les degrés de s et f
    FIN POUR
    ajouter dans T une arête entre les deux sommets de degré 1 restant dans D
    RENVOYER T
FIN

Implémentation

Nos souhaitons implémenter les fonctions code et decode. Pour cela, il nous faut une représentation pour les arbres. Je propose plusieurs options :

on peut utiliser le module graphe vu en cours. Un arbre étant un graphe particulier, le module graphe conviendra.
On peut choisir un tableau de $n$ éléments tels que arbre[i] représente le parent du sommet i. Par exemple, l'arbre de droite serait codé [4, 2, 7, 1, 1, 7, 0, -1]. Comme 7 est la racine, on a choisi de l'indiquer par arbre[7] = -1.
Avec ce choix, dans decode, il faut initialiser T = [0...0]
Lors de la connexion, on n'indique la connexion que dans un sens : arbre[f] = s.
Avec ce choix, le code P = (1, 2, 0, 4, 1, 2) devrait renvoyer l'arbre T = [4, 2, -1, 1, 1, 2, 0, 2] ou bien T = [4, 2, 7, 1, 1, 2, 0, -1].

Avec ce 2e choix, l'arbre à gauche et l'arbre à droite ne sont pas représentés de la même façon bien qu'ils aient le même code de Prüfer.

Utilisation

La 2e solution d'implémentation de l'arbre montre que le code de Prüfer ne fait pas gagner grand chose en termes de poids : au lieu d'un tableau T de taille n, le code a la taille n - 2. C'est moins mais pas beaucoup moins. Ce n'est donc pas cela qui est important.

Quand on choisit une représentation pour un graphe, on pourra facilement avoir l'impression que deux graphes sont différents alors que leur jeu de connexion fait qu'ils sont équivalents. Le code de Prüfer permet étant unique, si deux graphes ont le même, c'est qu'ils sont équivalents. Le code permet alors de tester l'équivalence entre deux arbres.

On peut aussi, pour $n$ sommets, chercher le meilleur arbre possible satisfaisant certains critères. Le code de Prüfer permet de parcourir tous les arbres possibles sans risque de répétition et ainsi de trouver le meilleur choix.