Le sudoku arboricole

Piste verte Le 21 décembre 2013  - Ecrit par  Shalom Eliahou Voir les commentaires

Les homards, araignées et autres arbres mathématiques sont-ils gracieux ? Selon une conjecture mi-centenaire, ce devrait être le cas !

L’objet central de cet article, ce sont les arbres mathématiques. Sans plus attendre, en voici un exemple typique :

Une définition précise est donnée plus loin. Mais d’abord, décrivons informellement le problème abordé ici sur ces arbres : il s’agit de numéroter les sommets (les gros points) et les arêtes (les segments) en respectant quelques conditions évoquant un peu celles du sudoku. La numérotation est dite gracieuse lorsque lesdites conditions sont satisfaites.

Le sudoku

Avant de présenter sa version arboricole, rappelons brièvement ce qu’est le sudoku classique. On part d’une grille carrée 9 x 9 partiellement remplie de numéros entre 1 et 9. Le but du casse-tête est de compléter la grille en respectant les conditions suivantes :

  • chaque case doit contenir un numéro entre 1 et 9 ;
  • aucune rangée – ligne ou colonne – ne doit contenir de répétition ;
  • aucune des neuf sous-grilles 3 x 3 délimitées en gras sur la figure ne doit contenir de répétition.

Comme on le verra, la version arboricole est tout aussi facile à comprendre ; là encore, l’une des principales conditions est la non-répétition des numéros. Seul petit hic : elle fait l’objet d’une conjecture ouverte depuis près d’un demi-siècle !

Mini lexique de théorie des graphes

Une dose — homéopathique — de vocabulaire technique nous sera utile pour bien entamer notre promenade champêtre. Un graphe est une collection finie [1] de points et de paires de points. Les points sont appelés sommets et les paires de points sont appelées arêtes. On visualise une arête par un segment de droite ou de courbe reliant ses deux sommets. Voici un exemple de graphe :

Deux sommets reliés par une arête sont dits voisins. Le degré d’un sommet est le nombre de ses voisins. Dans l’exemple ci-contre, le sommet rouge est de degré 6.

On dit d’un graphe qu’il est connexe si, informellement, il est en un seul morceau ; plus formellement, si l’on peut aller de n’importe quel sommet à n’importe quel autre sommet en cheminant le long d’arêtes. C’est bien le cas du présent exemple.

Un cycle est un chemin fermé, c’est-à-dire un graphe connexe dont tous les sommets sont de degré 2. Le sous-graphe marqué en bleu dans l’exemple est un cycle de longueur 4.

Dans cet article, on ne considère que les graphes dits simples : aucun sommet n’est son propre voisin, et aucune paire de sommets n’est reliée par plus d’une arête.

Les graphes sont des objets mathématiques extrêmement utiles, tant au niveau théorique qu’à celui des applications. Ils sont indispensables dans de nombreux domaines dont l’informatique, la chimie ou la modélisation du trafic. Voir par exemple cet article sur ce site.

Venons-en maintenant aux arbres, des graphes très particuliers et aisément reconnaissables.

Arbres

Un arbre est un graphe connexe, sans cycles. Voilà pour la définition formelle complète de ces objets mathématiques !

Les sommets extrémaux d’un arbre sont appelés ses feuilles. Ce sont donc ses sommets de degré 1, ceux de couleur verte dans notre exemple favori :

Notons que si un arbre contient au moins trois sommets, alors chaque feuille est contenue dans une unique arête, qu’on appellera alors sa brindille.

Les arbres jouissent d’une propriété héréditaire très utile, qui est l’affirmation suivante.

Propriété héréditaire. Si, dans un arbre, on supprime une feuille et sa brindille, alors le graphe résultant est encore un arbre.

Cela s’explique facilement : le graphe ainsi tronqué reste en un seul morceau, c’est-à-dire connexe, et reste bien évidemment sans cycle. Il suffit de dessiner un petit exemple pour s’en convaincre.

Voici une première conséquence très intéressante. En procédant à l’envers, on peut construire n’importe quel arbre en partant d’un sommet initial, puis en répétant l’opération suivante : relier une nouvelle feuille à un sommet déjà présent par une nouvelle brindille. Comme dans la suite ci-dessous :

Cette propriété est très utile si l’on veut faire des démonstrations par récurrence au sujet des arbres. Un bel exemple en est la preuve — facultative pour qui souhaite rester sur piste verte, mais valant le coup d’oeil quand même — de cette autre propriété incontournable des arbres.

Propriété. Si un arbre a $n$ arêtes, alors il a $n+1$ sommets.

Démonstration

C’est bien vrai pour $n=1$ : un arbre à une seule arête possède deux sommets.

Pour le cas général avec $n \ge 2$, on procède par récurrence, une méthode de démonstration très puissante. En gros, cette méthode revient à dire que si l’on veut atteindre la $n$-ème marche d’un escalier, il suffit d’atteindre sa $(n-1)$-ème marche et de monter une marche de plus.

Dans le cas présent, on suppose le résultat déjà démontré pour les arbres à $n-1$ arêtes et, partant de là, on essaie de le démontrer pour les arbres à $n$ arêtes.

Prenons donc un arbre à $n$ arêtes, et supprimons l’une de ses feuilles avec sa brindille. Par la propriété héréditaire ci-dessus, on tombe sur un arbre à $n-1$ arêtes. Or maintenant, grâce à l’hypothèse de récurrence, on sait que celui-ci possède $(n-1)+1$ sommets, c’est-à-dire $n$ sommets.

En comptant la feuille supprimée, on trouve que l’arbre de départ possède bien $n+1$ sommets en tout. $\Box$

Pour divers liens entre graphes, arbres et littérature, voir sur ce site cet article joliment illustré.

Numérotations gracieuses

Armés de ces connaissances sur les arbres, nous pouvons aborder notre casse-tête aux règles simples — mais pourtant encore bien mal compris. Donnons-nous un arbre $A$ à $n$ arêtes — et donc à $n+1$ sommets. Une numérotation gracieuse de $A$ est la donnée de :

  • une numérotation de ses arêtes de 1 à $n$, sans répétition ;
  • une numérotation de ses sommets de 0 à $n$, sans répétition ;
  • une règle de compatibilité entres ces deux numérotations : le numéro de chaque arête doit être égal à la différence positive des numéros de ses deux sommets.

Cette troisième condition est résumée par le dessin suivant, où l’on a supposé que $b$ est plus grand que $a$ :

Notons que, sitôt les sommets numérotés, la règle de compatibilité fournit automatiquement une numérotation des arêtes : il suffit d’assigner à chacune la différence positive des numéros de ses extrémités, comme ci-dessus. Mais il faut encore s’assurer du respect des contraintes de non-répétition pour que cette numérotation puisse prétendre au titre de gracieuse.

Voici un exemple d’arbre à 9 arêtes gracieusement numéroté. Les arêtes sont numérotées en bleu de 1 à 9, les sommets en rouge de 0 à 9, sans répétition dans les deux cas ; et enfin, la règle de compatibilité est bien satisfaite : chaque numéro d’arête bleu est la différence positive des numéros rouges de ses extrémités.

Le sudoku arboricole

La ressemblance entre les numérotations gracieuses d’un arbre et le sudoku tient en cela : il s’agit d’assigner des numéros pris dans un ensemble précis en respectant des règles de non-répétition. D’où ce terme de sudoku arboricole.

Vous pouvez d’ores et déjà y jouer, sans devoir attendre que votre quotidien préféré vous en propose : dessinez un arbre, de préférence petit au début, et essayez de le numéroter gracieusement ; ou mettez quelqu’un de votre entourage au défi de le faire.

Quel que soit l’arbre choisi, le sudoku sur celui-ci admet-il forcément une solution ? C’est là que les choses se corsent : on ne sait pas ! Mais on conjecture que c’est toujours le cas.

La conjecture

Reformulons cela en utilisant la terminologie officielle : un arbre est dit gracieux s’il admet au moins une numérotation gracieuse.

Conjecture. Tout arbre mathématique est gracieux.

Dans la littérature scientifique, ce problème est connu comme la conjecture des arbres gracieux, entre autres [2]. Elle a été formulée par Alex Rosa en 1967, comme approche possible d’une conjecture antérieure de Ringel et Kotzig, datant de 1963, sur la décomposition de graphes complets [3] comme assemblage de copies d’un arbre donné.

Mis à part quelques résultats partiels, évoqués ci-dessous, on ne sait pas comment démontrer cette conjecture en général. Même des arbres d’apparence assez anodine, comme les homards et les araignées [4] présentés plus loin, sont une sacrée épine dans le pied des chercheurs. Sont-ils gracieux ? On aimerait tant pouvoir enfin l’affirmer ! [5]

Unicité ?

S’il est deux mots de grande importance en mathématiques, ce sont existence et unicité. Lorsque l’on dispose d’un système de contraintes mathématiques, quel qu’il soit, on se demande toujours si des solutions existent et, si oui, si celles-ci sont uniques — généralement à symétrie près.

Ainsi, la conjecture ci-dessus concerne l’existence de numérotations gracieuses pour tout arbre. Mais qu’en est-il de l’unicité ?

Déjà, l’ensemble des numérotations gracieuses d’un arbre à $n$ arêtes est doté d’une certaine symétrie : si l’on remplace, pour chaque sommet, son numéro $a$ par le numéro complémentaire $n-a$, et qu’on laisse les numéros des arêtes inchangés, alors la nouvelle numérotation est encore gracieuse. Cela découle de la simple formule
\[ (n-a) - (n-b) \, = \, b-a. \]
Donc, tout arbre gracieux comptant plus d’une arête admet au moins deux numérotations gracieuses. Petite illustration de cette symétrie :

Bon eh bien, qu’en est-il de l’unicité à symétrie près ? Cela dépend de l’arbre, mais en général, ses numérotations gracieuses semblent au contraire être très abondantes, comme dans le cas des chemins ci-dessous. C’est d’autant plus choquant qu’on ne sait pas démontrer qu’il en existe toujours au moins une !

Bref état des connaissances

Voici le statut — ouvert ou résolu — de la conjecture pour certaines familles d’arbres. Les termes consacrés pour nommer certaines d’entre elles sont assez cocasses, comme on a pu le subodorer dès le début de l’article.


Les chemins. Ces arbres très spéciaux, qu’on peut caractériser comme ceux ayant exactement deux feuilles, sont bien décrits par leur nom même :

Il est facile de numéroter gracieusement un chemin de longueur $n$ donnée. En partant d’une extrémité, on numérote toutes les arêtes successivement de $1$ à $n$, puis on numérote les sommets en partant de l’arête numéro $n$ et en respectant la règle de compatibilité :

Mais voici une autre numérotation gracieuse du même chemin :

En fait, lorsque $n$ grandit, le nombre de numérotations gracieuses du chemin à $n$ arêtes croît de façon exponentielle ! A tel point qu’on ne sait pas toutes les décrire.


Les chenilles. Une chenille est un arbre obtenu en partant d’un chemin et en rajoutant quelques brindilles à ses sommets :

Là encore, une recette simple, similaire à celle pour les chemins, permet de numéroter gracieusement les chenilles. On la devine dans cet exemple, en observant comment les arêtes sont numérotées dans l’ordre :

Les chenilles sont très utiles en théorie des graphes appliquée à la chimie, en particulier pour représenter les molécules d’hydrocarbone benzenoïde (merci Wikipedia).


Les homards. Un homard s’obtient en partant d’une chenille et en rajoutant quelques brindilles supplémentaires à ses sommets :

Et là, catastrophe : on dépasse déjà les frontières du connu ! On ne connaît aucune méthode systématique pour numéroter gracieusement un homard, ou en démontrer abstraitement la faisabilité.

En résumé, on sait que tous les chemins et toutes les chenilles sont gracieuses. Mais on ignore si tous les homards le sont.


Les araignées. Voici un exemple typique d’araignée mathématique, c’est-à-dire un arbre avec un sommet central duquel partent plusieurs chemins (ses pattes) :

On sait numéroter gracieusement les araignées à trois ou quatre pattes. Mais pour celles qui en ont cinq ou plus, on ne sait pas faire en général !


Les étoiles. Les étoiles sont un cas particulier d’araignée, où toutes les pattes sont de longueur 1 :

Ces arbres-là sont les plus faciles à numéroter gracieusement. Sauriez-vous le faire ? Sans le moindre doute. Ne pas guigner la solution — unique à symétries près — avant d’avoir essayé, voire avant d’avoir réussi !

Solution

Il suffit d’assigner 0 au sommet central, puis les numéros suivants aux feuilles et à leurs brindilles respectives, et le tour est joué !


Autres familles. Pour clore ce bref survol des connaissances, voici encore le statut de la conjecture pour quelques autres familles d’arbres :

  • Les arbres avec 4 feuilles ou moins sont gracieux. A partir de 5 feuilles, on ne sait plus faire en général.
  • Les arbres de diamètre 5 ou moins sont gracieux. Le diamètre d’un arbre, par définition, c’est la plus grande longueur de chemin contenu dans cet arbre. Par exemple, les étoiles sont de diamètre 2.
  • Les arbres à 34 arêtes ou moins sont gracieux, comme cela a été vérifié par ordinateur.

Quelle stratégie ?

Comment progresser vers une solution de ce problème ? C’est très difficile de répondre en l’état. Plusieurs stratégies s’offrent au chercheur.

Une approche possible, déjà abondamment pratiquée, consiste à se concentrer sur des familles spécifiques d’arbres en essayant de résoudre le problème pour celles-ci. Par exemple, on ignore si tous les homards sont gracieux. Est-ce une bonne idée de se focaliser sur eux, voire sur le cas encore plus spécifique de ceux obtenus à partir d’une chenille en n’ajoutant qu’une seule brindille, par exemple ?

Les mathématiques peuvent avoir des développements imprévus. Ainsi, on pourrait croire que concentrer ses recherches sur une classe restreinte d’objets, comme suggéré ci-dessus, simplifie forcément les choses. Or ce n’est pas toujours le cas. Il arrive qu’au contraire, cela les complique ; parce qu’en se restreignant trop, on risque de se priver de la possibilité d’user de méthodes plus générales et plus abstraites et, par là, plus puissantes.

Une approche alternative, parmi d’autres possibles, serait d’essayer de compter les arbres à $n$ arêtes à numérotation gracieuse, et ensuite espérer constater qu’on trouve le même décompte que tous les arbres à $n$ arêtes. On sait assez bien compter les arbres ; par exemple, il y a exactement 2.023.443.032 arbres à 27 arêtes vraiment distincts [6]. Cela dit, cette voie ne ressemble guère plus à un long fleuve tranquille.

Enfin, on n’est jamais à l’abri d’une surprise : il se pourrait que la conjecture soit fausse ! C’est-à-dire qu’il pourrait exister, quelque part dans le paysage mathématique, un arbre parfaitement disgracieux. Si c’était le cas, combien d’arêtes aurait-il ? Quarante ? Un milliard de milliards ? Comment faire, le cas échéant, pour le trouver, le construire, ou ne serait-ce que prouver abstraitement son existence ?

Seul le futur, façonné par les recherches de toutes celles et ceux qui s’y pencheront — dont des lectrices et lecteurs de cet article, qui sait ? — nous dira quelle approche aura finalement permis de surmonter ce très énigmatique problème.

Un petit défi

Pour finir sur une note ludique, voici un arbre à 9 arêtes qu’il s’agit de numéroter gracieusement. Vous l’aurez reconnu, il s’agit d’un homard obtenu à partir d’une chenille par l’ajout d’une seule brindille supplémentaire. Dans l’onglet de gauche, deux sommets sont déjà numérotés — et alors, comme pour le sudoku classique, il n’y a qu’une seule complétion possible en une numérotation gracieuse (à permutation près des numéros des trois brindilles de droite). A titre d’aide, dans l’onglet de droite, trois sommets supplémentaires sont numérotés. Ne cliquer dessus qu’en cas de panne sèche — ou de solution !

Il se pourrait qu’occasionnellement, de nouveaux défis soient proposés ici même. Bonne recherche !

Post-scriptum :

L’auteur remercie gracieusement Roland Bacher et Bruno Martin, ainsi que les relecteurs de pseudonymes Thierry Viéville, Jean-Romain et P.Levallois, pour leur lecture attentive et leurs commentaires très constructifs.

Article édité par Shalom Eliahou

Notes

[1C’est une convention très fréquente, même si des versions infinies sont aussi intéressantes et étudiées.

[2Une notion analogue de numérotation gracieuse a en fait un sens pour tous les graphes. Mais dans ce contexte plus général, on connaît de nombreux cas non gracieux.

[3C’est-à-dire dont tous les sommets sont voisins les uns des autres.

[4Eh oui, je n’y peux rien : en théorie des graphes, les homards et les araignées — ainsi que les chemins, les étoiles et les chenilles — sont des arbres !

[5Pour la première personne au monde capable d’affirmer, preuve à l’appui et nonobstant l’incrédulité publique, que toutes les araignées et tous les homards sont gracieux, c’est la célébrité assurée :-)

[6On dirait « non-isomorphes », en langage technique.

Partager cet article

Pour citer cet article :

Shalom Eliahou — «Le sudoku arboricole» — Images des Mathématiques, CNRS, 2013

Crédits image :

Image à la une - Un arbre à Buenos Aires, le 5 août 2013.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM