Théorie des graphes : une science aux applications illimitées ?

Tout autour de nous figurent des liens physiques ou intangibles qui peuvent être modélisés par des graphes. C’est un plan de métro où chaque station est représentée par un point et où chaque ligne est une connexion entre ces stations, ou encore un réseau reliant producteurs et consommateurs d’énergie par des câbles électriques. En recherche, l’étude de ces objets et la compréhension de leur structure est au cœur de la théorie des graphes, une discipline à l’interface entre mathématiques et informatique.

« À ses débuts, la théorie des graphes s’apparentait en quelque sorte à des mathématiques récréatives basées sur la résolution de petits problèmes ou d’énigmes avant de devenir un champ mathématique à part entière au XX^e siècle », décrit Louis Esperet, directeur de recherche CNRS au laboratoire Sciences pour la Conception, l'Optimisation et la Production de Grenoble (G-SCOP - CNRS/Université Grenoble Alpes). Leonhard Euler est souvent considéré comme le fondateur de la discipline avec sa résolution du problème des sept ponts de Königsberg. Le mathématicien suisse prouve au début du XVIII^e siècle qu’il est impossible de traverser une seule fois ces sept ponts sans repasser par un autre déjà traversé. Deux siècles plus tard, la théorie des graphes joue un rôle crucial dans des opérations militaires de la guerre froide. D’un côté, elle vise à maximiser le transport de marchandises soviétiques, de l’autre, elle sert à trouver les points de faiblesses sur ce même réseau ferroviaire en vue de possibles bombardements aériens côté américain. Ces deux objectifs distincts s’avèrent poser le même problème¹.

C’est toutefois l’arrivée de l’informatique qui permet à la théorie des graphes de prendre pleinement son essor. « Depuis une quarantaine d’années, une partie de la communauté se concentre sur l’élaboration de théories unificatrices permettant de résoudre une multitude de problèmes sans en cibler un en particulier », explique Marthe Bonamy, chargée de recherche CNRS au Laboratoire Bordelais de Recherche en Informatique (LaBRI - CNRS/Bordeaux INP/Université de Bordeaux). Les applications modernes n’en sont que d’autant plus vastes : recherche de médicaments, logistique, télécommunications ou encore étude des réseaux sociaux. La théorie des graphes s’est imposée comme un outil central à la compréhension des réseaux intriqués de notre société.

Elle ne saurait cependant se résumer à ses domaines d’application. En effet, ses origines mathématiques lui procurent aussi de grandes questions théoriques. « Une question générale est d’identifier ce qui détermine la frontière très fine entre des problèmes théoriquement faciles ou difficiles à résoudre. Autrement dit, l’étude de la complexité des algorithmes de graphe », explique Louis Esperet. Les résultats qui en découlent bénéficient notamment à la résolution de problèmes d’autres champs mathématiques, comme la théorie des groupes et la topologie.

Actuellement, la communauté travaille sur de nombreux enjeux théoriques comme le développement d’algorithmes pour des systèmes distribués, la compréhension des relations entre les propriétés structurelles des graphes, l’étude des graphes construits selon des processus aléatoires, etc. « La théorie des graphes est un jeu permanent entre l’adaptation de méthodes existantes à des problèmes industriels qui ne cessent d’émerger et la recherche de nouvelles théories, sachant que les deux se nourrissent l’un l’autre », résume Marthe Bonamy.

Notes

1. Alexander Schrijver. On the History of the Transportation and Maximum Flow Problems, Documenta Mathematica · Extra Volume ISMP (2012) 169–180.