Codage de Prüfer

Le codage de Prüfer est une manière très compacte de décrire un arbre.

Codage

Soit l'arbre T = (V, E) et supposons V = {1, 2, ..., n}.
L'algorithme ci-dessous fournira le code de T, c'est-à-dire une suite S de n-2 termes employant (éventuellement plusieurs fois) des nombres choisis parmi {1, ..., n}.

Pas général de l'algorithme de codage

(à répéter tant qu'il reste plus de deux sommets dans l'arbre courant T)
  • identifier la feuille v de l'arbre courant ayant le numéro minimum ;
  • ajouter à la suite S le seul sommet s adjacent à v dans l'arbre T courant ;
  • enlever de l'arbre T courant le sommet v et l'arête incidente à v.

Exemple de codage
Etape 0

Arbre à coder		 Etape 1

S={4}		 Etape 2

S={4,10}		 Etape 3

S={4,10,3}		 Etape 4

S={4,10,3,8}
Etape 5

S={4,10,3,8,4}		 Etape 6

S={4,10,3,8,4,4}		 Etape 7

S={4,10,3,8,4,4,5}		 Etape 8

S={4,10,3,8,4,4,5,10}		 S={4,10,3,8,4,4,5,10} est le codage de Prüfer de l'arbre initial.

Zone pour malvoyants

Etape 0

1: 4
2: 10
3: 6, 8
4: 1, 5, 7, 8
5: 4, 10
6: 3
7: 4
8: 3, 4
9: 10
10: 2, 5, 9

Arbre à coder
Etape 1

2: 10
3: 6, 8
4: 5, 7, 8
5: 4, 10
6: 3
7: 4
8: 3, 4
9: 10
10: 2, 5, 9

S={4}
Etape 2

3: 6, 8
4: 5, 7, 8
5: 4, 10
6: 3
7: 4
8: 3, 4
9: 10
10: 5, 9

S={4,10}
Etape 3

3: 8
4: 5, 7, 8
5: 4, 10
7: 4
8: 3, 4
9: 10
10: 5, 9

S={4,10,3}
Etape 4

4: 5, 7, 8
5: 4, 10
7: 4
8: 4
9: 10
10: 5, 9

S={4,10,3,8}
Etape 5

4: 5, 8
5: 4, 10
8: 4
9: 10
10: 5, 9

S={4,10,3,8,4}
Etape 6

4: 5
5: 4, 10
9: 10
10: 5, 9

S={4,10,3,8,4,4}
Etape 7

5: 10
9: 10
10: 5, 9

S={4,10,3,8,4,4,5}
Etape 8

9: 10
10: 9

S={4,10,3,8,4,4,5,10}
 S={4,10,3,8,4,4,5,10} est le codage de Prüfer de l'arbre initial.

 

Décodage

Donnée: suite S de n-2 nombres, chacun provenant de {1, ..., n}.
Posons I = {1, ..., n}.

Pas général de l'algorithme de décodage

(à répéter tant qu'il reste des éléments dans S et plus de deux éléments dans I)
  • identifier le plus petit élément i de I n'apparaissant pas dans la suite S ;
  • relier par une arête de T le sommet i avec le sommet s correspondant au premier élément de la suite S ;
  • enlever i de I et s de S.

Les deux éléments qui restent dans I à la fin de l'algorithme constituent les extrémités de la dernière arête à ajouter à T.

Exemple de décodage
Etape 1

I={1,2,3,4,5,6,7,8,9,10}
S={4,10,3,8,4,4,5,10}		 Etape 2

I={2,3,4,5,6,7,8,9,10}
S={10,3,8,4,4,5,10}		 Etape 3

I={3,4,5,6,7,8,9,10}
S={3,8,4,4,5,10}		 Etape 4

I={3,4,5,7,8,9,10}
S={8,4,4,5,10}		 Etape 5

I={4,5,7,8,9,10}
S={4,4,5,10}
Etape 6

I={4,5,8,9,10}
S={4,5,10}		 Etape 7

I={4,5,9,10}
S={5,10}		 Etape 8

I={5,9,10}
S={10}		 Etape 9

I={9,10}
S={}		 Etape 10

I={}
S={}

Zone pour malvoyants

Etape 1

I={1,2,3,4,5,6,7,8,9,10}
S={4,10,3,8,4,4,5,10}

Etape 2

1: 4
4: 1

I={2,3,4,5,6,7,8,9,10}
S={10,3,8,4,4,5,10}

Etape 3


1: 4
2: 10
4: 1
10: 2

I={3,4,5,6,7,8,9,10}
S={3,8,4,4,5,10}

Etape 4

1: 4
2: 10
3: 6
4: 1
6: 3
10: 2

I={3,4,5,7,8,9,10}
S={8,4,4,5,10}

Etape 5

1: 4
2: 10
3: 6, 8
4: 1
6: 3
8: 3
10: 2

I={4,5,7,8,9,10}
S={4,4,5,10}

Etape 6

1: 4
2: 10
3: 6, 8
4: 1, 7
6: 3
7: 4
8: 3
10: 2

I={4,5,8,9,10}
S={4,5,10}

Etape 7

1: 4
2: 10
3: 6, 8
4: 1, 7, 8
6: 3
7: 4
8: 3, 4
10: 2

I={4,5,9,10}
S={5,10}

Etape 8

1: 4
2: 10
3: 6, 8
4: 1, 5, 7, 8
5: 4
6: 3
7: 4
8: 3, 4
10: 2

I={5,9,10}
S={10}

Etape 9

1: 4
2: 10
3: 6, 8
4: 1, 5, 7, 8
5: 4, 10
6: 3
7: 4
8: 3, 4
10: 2, 5

I={9,10}
S={}

Etape 10

1: 4
2: 10
3: 6, 8
4: 1, 5, 7, 8
5: 4, 10
6: 3
7: 4
8: 3, 4
9: 10
10: 2, 5, 9

I={}
S={}

 

Théorème 7 (Cayley, 1857)

Le nombre d'arbres que l'on peut construire sur n (n>1) sommets numérotés est égal à nn-2.

Preuve

La preuve est immédiate en utilisant le codage de Prüfer. En effet, on vérifie aisément que les deux algorithmes constituent les deux sens d'une bijection entre les arbres sur n sommets numérotés et les mots de n-2 lettres sur l'alphabet à n lettres.
Ce constat permet de conclure la preuve du théorème de Cayley. En effet, il existe nn-2 mots de longueur n-2 sur l'alphabet à n lettres, donc d'arbres sur n sommets numérotés.

Exercice

1: 2
2: 1, 3
3: 2, 4, 5
4: 3
5: 3, 6, 7
6: 5
7: 5, 8, 9
8: 7
9: 7, 10
10: 9

 Décrivez l'arbre ci-contre à l'aide du codage de Prüfer.

Dessinez l'arbre correspondant à la suite S={1,1,1,1,1,1,1,1,1}.

Téléchargez ensuite le fichier Mathematica ci-dessous:

prufer.nb

et utilisez Mathematica pour vous entraîner au codage de Prüfer!

Le corrigé est disponible, mais seulement pour les visiteurs autorisés!
Mot de passe :

Didier Müller, 10.2.03