Qu'est ce qu'un arbre gracieux ? © Ejausburg, Pixabay, DP

Sciences

Qu'est ce qu'un arbre gracieux ?

Question/RéponseClassé sous :Mathématiques , ensemble mathématique , arbre généalogique

Certains termes mathématiques sont étonnants et peuvent même faire rêver. Ainsi en est-il de la gracieuseté des arbres. Dans la jungle mathématique, comment distinguer les arbres gracieux de ceux qui ne le sont pas ?

En mathématiques, un arbre est constitué de nœuds reliés par des arêtes. Un peu comme dans les arbres généalogiques, chaque nœud a ou non des fils et un nœud est la racine de tous. En voici donc un, pourvu de six nœuds et cinq arêtes (la racine est celui au-dessus).

 

Cet arbre sera considéré comme gracieux si on peut numéroter les nœuds de 0 à 5 et les arêtes de 1 à 5 de sorte que le numéro de chaque arête soit égal, au signe près, à la différence des numéros des nœuds qui la limitent.

Question : cet arbre est-il gracieux ?

Réponse : oui, comme le montre l'étiquetage (ci-dessous).

Question : l’arbre suivant est-il gracieux ?

Réponse : oui, comme le montre l'étiquetage (en dessous).  

 

       

Une conjecture vieille de 50 ans

En 1967, Alexander Rosa, un mathématicien slovaque a conjecturé que tout arbre était gracieux sans pouvoir le démontrer. La question a fait l'objet d'énormément de recherches depuis, mais personne n'a réussi à démontrer que c'était vrai ou que c'était faux. On a seulement réussi à démontrer, grâce à l'utilisation d'ordinateurs puissants, que tous les arbres ayant au plus 35 nœuds sont gracieux.

Une question loufoque ?

Si vous pensez que cette recherche est complètement gratuite et sans applications possibles, dites-vous que les réseaux sont représentés par des arbres ou plus généralement des graphes et que la question de l'étiquetage des nœuds et des arêtes a son importance.

Abonnez-vous à la lettre d'information Mathématiques amusantes : chaque semaine, Futura traite une question de mathématique pour le plaisir des 7 à 77 ans.

!

Merci pour votre inscription.
Heureux de vous compter parmi nos lecteurs !

En savoir plus sur Hervé Lehning

Normalien et agrégé de mathématiques, Hervé Lehning a enseigné sa discipline une bonne quarantaine d'années. Fou de cryptographie, membre de l'Association des réservistes du chiffre et de la sécurité de l'information, il a en particulier percé les secrets de la boîte à chiffrer d'Henri II. 

À découvrir également : L'univers des codes secrets de l'Antiquité à Internet, paru en 2012 chez Ixelles.

À voir aussi :