L'art de l'éphémère  /  La tortue

Graphes eulériens  /  Le monde des esprits  /  Du Vanuatu à l'Angola



  • Graphes eulériens

    Je vais rentrer un peu plus en détails dans la manière dont sont tracés les dessins sur le sable du Vanuatu. La chose primordiale, c'est que ces dessins doivent être tracés au moyen d'une ligne continue, c'est-à-dire sans lever le doigt du sol, en revenant à son point de départ, et sans repasser par un arc qui a déjà été tracé. C'est un fait bien connu, qu'on trouve expliqué par exemple dans les lettres de Deacon. Il insiste sur cette règle que doit respecter le tracé des dessins sur le sable. D'ailleurs, chez les Vanuatu, il y a même des éléments explicites pour le confirmer. Par exemple le fait qu'on ne puisse pas repasser sur un arc qui a déjà été tracé, ça fait l'objet, cette règle elle-même fait l'objet d'un dessin qu'on appelle "le rat mangeant le fruit de l'arbre à pain". C'est un dessin qu'on trace, et puis à un certain moment dans le tracé, on repasse sur une partie du dessin qui a déjà été tracée. Cela revient à l'effacer, et on conidère qu'à ce moment-là, c'est la portion du fruit que le rat a mangée. C'est pour dire que la règle est parfaitement explicite. On doit tracer le dessin sans lever le doigt et en passant une fois et une seule par chacun des segments.

    Cette règle-là pose un certain nombre de problèmes. Ce n'est pas si évident de tracer un dessin, surtout s'il a une forme compliquée avec des enchevêtrements de lignes, en respectant la règle. Et c'est tellement pas évident que c'est même ce qui a donné naissance, dans nos mathématiques occidentales, à un domaine spécifique qu'on appelle la "théorie des graphes". Revenons sur ces idées qui ont donné naissance à la théorie des graphe. Ça remonte à un petit problème récréatif étudié par Euler.

    À l'origine, Euler s'était intéressé au problème des ponts de Königsberg. Les ponts de Königsberg sont au nombre de sept, disposés entre deux berges et une île, et le problème était de parcourir l'ensemble des sept ponts une fois et une seule, sans passer deux fois par le même pont. Je ne vais pas prendre l'exemple de Königsberg, mais un exemple analogue qui est aussi bien connu, l'exemple de l'enveloppe. Comment tracer la figure qui est représentée ci-dessous, en passant une fois et une seule par chacun des segments ? Et est-ce qu'un tel tracé est possible ? Pour l'enveloppe, si vous avez joué à ça quand vous étiez à l'école, vous savez sans doute que le tracé est effectivement possible, mais pas n'importe comment. Il y a un certain nombre de contraintes, et pour savoir comment on doit tracer le dessin, il faut pour chacun des points d'intersection, compter le nombre d'arcs qui arrivent à ce point. Si on fait le calcul, ça donne la chose suivante :

    enveloppe

    On a des sommets avec trois arcs, quatre arcs, ou bien deux arcs. Ce qu'Euler avait découvert, c'est que le tracé est possible si le nombre de sommets impairs est égal soit à zéro, c'est-à-dire qu'on n'a pas de sommets impairs, soit à deux, c'est-à-dire qu'on a deux sommets impairs. Et Euler ajoute que dans le cas où on a deux sommets impairs, le tracé est possible, mais à condition de partir de l'un de ces sommets, et de terminer sur l'autre sommet. Qu'est-ce qui se passe dans le cas de l'enveloppe ? Combien on a de sommets impairs ?

    Comme on le voit ci-dessus, on a deux sommets impairs. Ce sont les deux sommets qui ont trois arêtes. D'après le théorème d'Euler, le tracé est possible, mais avec cette restriction qu'on doit partir obligatoirement de l'un de ces sommets, pour arriver à l'autre sommet. Voilà un exemple de tracé. Il y a plusieurs tracés respectant cette condition-là, mais ce que garantit le théorème d'Euler, c'est qu'il y en a au moins un. Voilà un exemple :

    enveloppe animée

    On part du sommet de gauche, on va vers le haut, on trace le toit, ensuite on repart vers le bas. On est déjà arrivé au point d'arrivée, mais on peut continuer, toujours sans repasser par des sommets déjà tracés, et cela permet finalement de compléter la figure, en respectant la règle.

    J'ai rappelé ce théorème d'Euler, pour montrer que l'idée de tracer un graphe, un dessin, avec une ligne continue, est une idée qui joue un rôle dans nos mathématiques occidentales, d'une part, et pour rappeler aussi que c'est un problème qui n'est pas évident a priori, qui peut poser un certain, nombre de difficultés. Si on analyse le théorème d'Euler, on constate qu'il est constitué au départ d'une "idée". Pourquoi Euler parle des sommets avec un nombre pair d'arêtes ? C'est une idée qui est toute simple en fait, c'est que si on arrive à ce sommet, il faut pouvoir en repartir. C'est-à-dire qu'il faut pouvoir grouper les arêtes qui arrivent à un sommet par deux, une pour arriver, l'autre pour repartir. Et si on peut les grouper par deux, ça veut dire qu'il y en a un nombre pair. Et cela doit être le cas pour chacun des sommets, sauf éventuellement celui qu'on emprunte au départ, et celui par lequel on arrive, puisqu'effectivement pour ceux-là, comme on ne repart pas, ou comme on ne vient de nulle part, ça permet d'avoir des sommets impairs. Mais on a donc soit zéro sommet impair, soit deux sommets impairs. L'idée, finalement, est assez simple. Ce qui est plus compliqué, c'est d'en faire un "théorème", c'est-à-dire notamment de dire que si le graphe vérifie ces conditions-là, alors on pourra effectuer un chemin avec une ligne continue. Le théorème lui-même, avec sa démonstration (qui est une démonstration par récurrence sur le nombre de points du graphe, c'est-à-dire reposant sur les axiomes de l'ensemble des entiers naturels), a évidemment peu de chance de se trouver en dehors du contexte de nos mathématiques occidentales. Par contre, l'idée de base, cette idée qu'il faut que les sommets aient un nombre pair d'arêtes, il n'est pas exclu de trouver, disons, des idées analogues, en dehors de notre contexte occidental.

    Ce genre de questions a donné naissance à un nouveau champ de recherches chez les historiens des mathématiques. Dans cette discipline, de plus en plus de gens s'intéressent aujourd'hui aux notions extra-occidentales qui pourraient avoir un lien de parenté avec nos mathématiques, ce qu'on appelle l'"ethnomathématique". Dans le cas des dessins sur le sable Vanuatu, ces dessins ont fait l'objet d'études de la part de personnes qui s'intéressent à l'"ethnomathématique". En particulier une américaine, Marcia Ascher, a publié une étude sur le sujet, reprise dans son livre Ethnomathematics. A Multicultural View of Mathematical Ideas  paru en 1991 (Chapman & Hall). Elle s'est intéressée aux courbes du type de celle de la tortue, et elle a montré que dans la plupart des cas, le tracé respectait un certain nombre de règles qui n'étaient pas obligatoires, en particulier des règles de symétrie. Si vous vous souvenez du tracé de la tortue, il était formé d'une combinaison de sous-courbes, et chacune de ces sous-courbes avait des propriétés de symétries. Et on peut observer ça sur un certain nombre de tracés du même type.


    L'art de l'éphémère  /  La tortue

    Graphes eulériens  /  Le monde des esprits  /  Du Vanuatu à l'Angola