Qu'est-ce que prufer ?

En mathématiques, le code de Prüfer (également connu sous le nom de séquence de Prüfer) est une façon de coder un arbre étiqueté à l'aide d'une séquence de nombres entiers. Ce code est utile pour représenter des arbres dans des programmes informatiques, car il est plus facile de manipuler des séquences de nombres que des structures arborescentes complexes.

Le code de Prüfer a été inventé en 1918 par l'ingénieur allemand Heinz Prüfer. Il est particulièrement efficace pour coder des arbres ayant un grand nombre de nœuds, car la taille de la séquence de codes est proportionnelle au nombre de nœuds de l'arbre, et non à la complexité de sa structure.

Pour coder un arbre à l'aide du code de Prüfer, on suit les étapes suivantes :

1. Trouver la feuille avec l'étiquette la plus petite et retirer cette feuille de l'arbre.
2. Ajouter l'étiquette de la feuille retirée à la séquence de codes.
3. Répéter les étapes 1 et 2 jusqu'à ce qu'il ne reste plus qu'une feuille dans l'arbre.

La séquence de codes obtenue est le code de Prüfer de l'arbre. Cette séquence peut être utilisée pour reconstruire l'arbre d'origine en utilisant un algorithme inverse appelé l'algorithme de Prüfer.