Un problème ouvert depuis 37 ans résolu par un mathématicien israélien au parcours peu habituel

Shares

Que peuvent avoir en commun internet, les embouteillages sur les routes, votre cerveau et votre facteur ???

Réponse: la théorie mathématique qui se cache derrière, la théorie des graphes. Internet est un exemple de réseau de communication, les embouteillages se forment dans des réseaux routiers, votre cerveau est constitué d’un réseau de neurones, et la tournée de votre facteur consiste à relier un nombre fini de boites à lettres le plus efficacement possible (sur un réseau routier). Toutes ces applications, et bien d’autres encore, sont des exemples de problèmes qui peuvent être étudiés et résolus grâce à la théorie des graphes, dont les origines remontent au dix-huitième siècle en Russie. Après avoir rappelé ce qu’est la théorie des graphes, nous verrons comment un problème ouvert depuis 37 ans a été résolu par un mathématicien israélien au parcours peu habituel.

Soyez informés en temps réel ! Suivez-nous sur...


Figure 1

Seriez-vous capable de reproduire le dessin à droite, sans lever le crayon et sans repasser deux fois sur le même chemin ? C’est un petit défi bien connu qu’on a tous relevé entre copains à l’école. C’est aussi un problème simple de la théorie des graphes en mathématiques. Mais qu’est-ce qu’un graphe au sens de la “théorie des graphes” ? Un graphe est composé d’un ensemble de points, appelés “sommets” et d’un ensemble de traits appelés “arcs”. Lorsque l’on relie deux sommets par un trait on créé ainsi un arc. Cet arc est dit “orienté” si on définit en plus un sens de parcours le long du trait. Si dans un graphe tous les arcs sont orientés, on dira alors que le graphe est orienté lui aussi. Le petit jeu auquel on jouait à l’école consiste donc à orienter le graphe de façon à parcourir tous les sommets sans passer deux fois sur le même arc.

Mais à quoi sert la théorie des graphes, et quand a-t-elle été élaborée ? Il est généralement admis que le premier résultat dans le domaine a été présenté par Euler en 1735 à l’Académie des Sciences de Russie à Saint-Pétersbourg. Dans sa présentation, Euler proposait une réponse au problème dit des « sept ponts de Königsberg » (maintenant Kaliningrad). La ville de Königsberg était constitué de deux iles et de sept ponts permettant de passer d’un quartier à un autre de la ville. Le problème consistait à déterminer s’il existe une promenade, avec un retour au point de départ, permettant de visiter les différents quartiers de la ville en ne passant qu’une seule fois sur chacun des ponts.

Figure 2

Le plan de la ville peut être représenté à l’aide du schéma de la Figure 3 qui peut lui même être représenté à l’aide d’un graphe (Fig. 4). Le problème « touristique » se traduit alors par la question mathématique suivante : peut-on orienter le graphe de façon, en partant d’un sommet et à y revenir, à parcourir tous les autres sommets sans repasser deux fois par le même arc ? La conjecture (résultat donné sans démonstration) donnée par Euler est négative. En effet, pour que cela soit possible, il faudrait que chaque sommet soit en contact avec un nombre pair d’arcs : on arrive par un arc déterminé et on repart par un autre arc bien précis. Or on peut constater que tous les sommets du graphe (sauf un) sont en contact avec trois arcs. Il n’est donc pas possible de définir une telle promenade touristique à Königsberg.

Figure 3

Plus de deux siècles plus tard, en 1970, un israélien Benjamin Weiss, directeur de thèse d’Elon Lindenstrauss dont on a déjà parlé sur siliconwadi.fr, et un collègue américain Roy Adler proposèrent une nouvelle conjecture de la théorie des graphes qui s’illustre également très bien avec un exemple concret. Supposez que vous arriviez dans une ville que vous ne connaissez pas, et que vous deviez vous rendre à un endroit bien précis. Le problème est que dans cette ville les rues ne possèdent pas de nom et sont toutes à sens unique (graphe orienté)…. A chaque intersection, vous avez la possibilité de continuer tout droit, tourner à droite ou tourner à gauche. Le problème est le suivant : existe-t-il une suite d’instructions finies (par exemple : gauche, droite, droite, tout droit, gauche) vous permettant de rejoindre le point d’arrivée quel que soit votre point de départ ? Par exemple, sur le graphe de la figure 5, en suivant (et répétant si nécessaire) les instructions « bleu-rouge-rouge » on arrive toujours sur le sommet jaune quel que soit le point de départ. Par contre, si on suit les instructions « bleu-bleu-rouge », on arrive toujours sur le point vert.

Figure 4

Ce problème est resté ouvert pendant 37 ans, jusqu’à ce qu’un autre israélien Avraham Trahtman propose une caractérisation des graphes qui peuvent posséder une telle solution. Entre temps, des dizaines de mathématiciens à travers le monde ont essayé en vain de résoudre ce problème ! La caractérisation proposée par Trahtman, ainsi que sa démonstration, sont relativement simples mais font appel à des connaissances en théorie des graphes qui dépassent le cadre de cet article.

Figure 5

Pour bien comprendre la portée des résultats obtenus en théorie des graphes, il est important de savoir que les réseaux peuvent être représentés mathématiquement par des graphes. On peut citer par exemple : réseaux routiers, électriques, d’eau potable, de tout à l’égout, de télécommunications. Internet est l’exemple type où la théorie des graphes et en particulier le résultat de Trahtman apporte des solutions (comment être sûr qu’un email arrive à destination, quelle que soit sa position dans le réseau?). La théorie des graphes peut apporter des solutions pour l’élaboration et l’optimisation de toute sorte de réseaux, mais également pour la mise en place de tournées : tournées de distribution de courrier, de livraison, de ramassage des ordures ménagères, etc… Les applications en informatique et dans les nouvelles technologies (GPS par exemple) sont immenses (les communications entre les différents processeurs d’un super-calculateur peuvent aussi se représenter sous la forme d’un graphe).

Le résultat de Trahtman, un des plus connus de la théorie des graphes, est d’autant plus admirable quand on considère le parcours professionnel atypique de son auteur…

Avraham est un mathématicien israélien d’origine russe, né en 1944. Il est en poste au département de mathématiques de l’université de Sverdlovsk (plus tard Iekaterinbourg) en Russie quand il décide d’aller vivre en Israël en 1992. A son arrivée, les postes universitaires sont rares et de nombreux mathématiciens russes inondent alors le marché de l’emploi israélien. N’étant plus tout jeune (il a alors 48 ans quand il arrive en Israël), il décide d’accepter n’importe quel emploi pour pouvoir subvenir à ses besoins. Il se retrouve ainsi agent d’entretien et gardien de nuit pour une société de nettoyage et de gardiennage. Ne perdant pas espoir de pouvoir refaire des mathématiques un jour, il envoie régulièrement des lettres de candidatures aux universités israéliennes. En 1995, l’Université Bar Ilan à Ramat Gan accepte sa candidature et lui propose un poste d’enseignant-chercheur au sein du département de mathématiques. Avraham peut alors reprendre ses recherches, et c’est ainsi qu’il propose en 2007, à l’âge de 63 ans, une réponse simple à la conjecture de Weiss et Adler. Avraham Trahtman est un grand mathématicien, humble, timide et réservé. Attaché à ses racines et à Israël, il publie sa solution de la conjecture de Weiss dans le Israel Journal of Mathematics plutôt que dans un grand journal américain où il aurait eu plus d’audience.

Alors que l’on considère souvent en mathématiques que les grands résultats sont l’apanage des jeunes chercheurs, l’histoire d’Avraham Trahtman nous enseigne qu’on n’est jamais trop vieux pour réfléchir et qu’à l’âge où en France on met nos seniors à la retraite on peut toujours contribuer à faire avancer la science.

Shares

RetweeTech

Rejoignez nos 2 902 abonnés et recevez nos derniers articles directement sur votre e-mail.