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 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. 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 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 . Cet algorithme s'appuie sur une suite des degrés de chaque sommet de l'arbre . L'arbre peut être reconstruit à l'aide de l'algorithme inverse suivant : 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 xi de P Augmenter de 1 le degré du sommet numéroté xi dans D Fin Pour chaque Pour chaque valeur xi 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 xi en j au graphe T Diminuer de 1 les degrés de xi et de j dans D Fin Pour chaque Ajouter l'arête reliant les deux sommets restants de degré 1 Considérons la suite .

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (4)

Séances de cours associées (2)

Codage de Prüfer

Preuve par bijection

En mathématiques, une preuve par bijection (ou démonstration par bijection) est une technique de démonstration qui consiste à obtenir l'égalité de deux expressions entières en exhibant une bijection entre deux ensembles dont les deux expressions sont les cardinaux. Autrement dit, on examine deux ensembles finis X et Y, on les dénombre et au moyen d'une bijection de X sur Y, on en déduit que les résultats des comptages sont égaux. On présente souvent la démonstration en disant qu'on a transformé le problème de dénombrement en un problème équivalent.

Arbre couvrant

Dans le domaine mathématique de la théorie des graphes, un arbre couvrant d'un graphe non orienté et connexe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe. De façon équivalente, c'est un sous-graphe acyclique maximal, ou encore, un sous-graphe couvrant connexe minimal. Dans certains cas, le nombre d'arbres couvrants d'un graphe connexe est facilement calculable. Par exemple, si lui-même est un arbre, alors , tandis que si est un n-cycle, alors .

Explore le comptage des arbres marqués à l'aide de codes et d'algorithmes Prüfer, fournissant des cartes entre les arbres et les séquences.

Explore l'estimation des arbres non marqués et leur reconstruction unique à partir de séquences.