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 ?

au sommaire


    En mathématiques, un arbre est constitué de nœuds reliés par des arêtes. Un peu comme dans les arbresarbres 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).

    Image du site Futura Sciences
     

    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).

    Image du site Futura Sciences

    Question : l’arbre suivant est-il gracieux ?

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

    Image du site Futura Sciences
     

           

    Image du site Futura Sciences

    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 applicationsapplications 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.

    Hervé Lehning

    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. 

    Acheter le livre 


    Cliquez pour acheter le livre 

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