En mathématiques combinatoires, la séquence Prüfer (également le code Prüfer ou les nombres Prüfer) d`un arbre étiqueté est une séquence unique associée à l`arbre. Ensuite, nous trouvons la moindre valeur qui n`est pas présent dans la séquence donnée et pas encore ajouté à l`arbre. Étant donné un arbre (représenté par un graphique, pas comme un arbre enraciné) avec n nœuds marqués avec des étiquettes de 1 à n, un code Prufer idéfie l`arborescence de manière unique. Vertex 4 est maintenant une feuille et a la plus petite étiquette, il est donc enlevé et nous ajoutons 5 à la séquence. Ces deux résultats sont rassemblés dans la bijection entre les séquences Prüfer et les arbres étiquetés. Code Prüfer. Codage qui fournit une bijection entre les arborescences étiquetées sur les noeuds et les chaînes d`entiers choisies à partir d`un alphabet des nombres 1 à. Les séquences de Prüfer ont été utilisées pour la première fois par Heinz Prüfer pour prouver la formule de Cayley en 1918. Nous sommes à gauche avec seulement deux sommets, donc nous nous arrêtons. Comparez avec l`exemple donné dans la séquence Prüfer de l`arborescence étiquetée. Nous supprimons le premier élément de la séquence. L`entrée de cet algorithme est la séquence Prüfer $ left ({mathbf{a}_1, mathbf{a}_2, ldots, mathbf{a}_{n-2}}right) $. Au début, le vertex 1 est la feuille avec la plus petite étiquette, de sorte qu`il est enlevé en premier et 4 est mis dans la séquence Prüfer.
De MathWorld-une ressource Web Wolfram. Prüfer, H. L`algorithme a terminé et l`arborescence est terminée. Par conséquent, après les itérations $n-$2, à l`étape 1, il y aura $2 $ de numéros dans la liste, et l`algorithme s`arrêtera. Considérez l`algorithme ci-dessus exécuté sur l`arborescence montrée à droite. La séquence d`un arbre sur n sommets a la longueur n − 2 et peut être générée par un algorithme itératif simple. La bijection de Prüfer`s est basée sur le fait que chaque arbre a au moins deux noeuds de degré 1 (i. Reading, MA: Addison-Wesley, 1990.
Ce dernier ensemble a la taille NN − 2, donc l`existence de cette bijection prouve la formule de Cayley, i. Laissez cette valeur être y. Que la longueur du code Prufer donné soit m. mise en œuvre de mathématiques discrètes: combinatoire et théorie des graphes avec Mathematica. On peut générer la séquence Prüfer d`un arbre étiqueté en supprimant itérativement les sommets de l`arborescence jusqu`à ce que seuls deux sommets demeurent. Arc. La conséquence immédiate est que les séquences de Prüfer fournissent une bijection entre l`ensemble des arbres marqués sur n sommets et l`ensemble des séquences de longueur n – 2 sur les étiquettes 1 à n. un peu moins évidente est le fait que pour une séquence donnée S de longueur n – 2 sur les étiquettes 1 à n , il y a un arbre étiqueté unique dont la séquence Prüfer est S.
La séquence des suppressions de feuilles est 4, 6, 2, 1, 7 et 3, correspondant respectivement aux nœuds incidents 1, 2, 1, 3, 3 et 5. La séquence de l`arbre est {4, 4, 4, 5}. L`arbre aura n + 2 noeuds, numérotés de 1 à n + 2. La séquence a des valeurs n-2. Phys. Nous ajoutons un bord de x à y et répétons cette étape. Enfin, ajoutez le bord (u, v) à l`arborescence. PrueferCode. Qu`est-ce que le code Prufer? Les sommets 2 et 3 sont supprimés ensuite, donc 4 est ajouté deux fois plus. Ensuite, pour chaque nombre dans la séquence a [i], trouver le premier noeud (le plus bas), j, avec un degré égal à 1, ajouter le bord (j, a [i]) à l`arborescence, et décrémenter les degrés de j et un [i]. La séquence Prüfer d`un arbre étiqueté sur n sommets est une séquence unique de longueur n − 2 sur les étiquettes 1 à n — ce qui est beaucoup plus clair. Laissez le premier élément de la séquence actuelle être x.
Neuer Beweis eines Satzes über Permutationen. Code Prüfer utilisant LabeledTreeToCode [g] dans le package de langage Wolfram Combinatorica`, et un code peut être converti en arborescence étiquetée à l`aide de CodeToLabeledTree [code].