Théorie des graphes et Applications

 La théorie des graphes est une branche fascinante et attractive des mathématiques. Elle contient plusieurs résultats, à la fois simples et profonds. Les représentations visuelles naturelles de nombreux problèmes invitent tout mathématicien à l’exploration. Les graphes sont des objets très puissants qui permettent de modéliser un très grand nombre de problèmes dans des domaines aussi variés que les sciences sociales, la biologie, la logistique, la chimie ou la physique. De manière informelle, un graphe est un ensemble de points appelés sommets et un ensemble d’arêtes qui relient certaines paires de sommets. Généralement, dans un réseau social, les sommets peuvent représenter les personnes, et deux personnes partagent une arête si elles se connaissent. En logistique, un sommet peut représenter une tâche à accomplir, et une tâche peut être liée à une autre lorsque l’une doit être effectuée avant l’autre. En chimie, les sommets peuvent représenter les atomes d’une molécule, et les arêtes les liaisons chimiques entre les atomes. Les graphes peuvent être utilisés pour répondre à des problèmes liés à ces différentes situations. 

En sciences sociales, la question peut par exemple être : quel est le plus grand groupe de personnes qui se connaissent mutuellement ? En logistique, quel est le temps minimum nécessaire pour accomplir toutes les tâches ? En chimie, combien de différentes molécules ont une même formule donnée ? Les graphes permettent de transformer ces problèmes en problèmes purement mathématiques. Par exemple, le plus grand groupe de personnes qui se connaissent mutuellement constitue ce que nous appelons une clique dans le graphe, et trouver la plus grande clique est un problème fréquemment étudié. Le temps minimum nécessaire pour accomplir un ensemble de tâches peut être modélisé à l’aide d’un problème de graphe appelé coloration. Le nombre de molécules différentes qui ont la même formule correspond au nombre de graphes non isomorphes qui ont la même séquence de degrés.

La théorie des graphes se situe à la frontière entre les mathématiques et l’informatique théorique. En particulier, tout un domaine de la théorie des graphes est axé sur la recherche d’algorithmes pour résoudre des problèmes de graphes. Un algorithme est une séquence d’instructions qui résout un problème. Il peut alors être implémenté dans un ordinateur, et utilisé pour n’importe quelle application du problème. Mais pour que l’algorithme soit utile, il faut qu’il soit efficace. La complexité d’un algorithme est, de manière informelle, le temps ou l’espace qu’il faut pour qu’il s’exécute sur un ordinateur, et la complexité d’un problème est la complexité minimale d’un algorithme qui le résout. L’étude de la complexité d’un problème est un outil utile lors de la recherche d’algorithmes efficaces. En particulier, lorsque la complexité est trop élevée, on pourrait vouloir se concentrer sur la recherche d’algorithmes d’approximation efficaces, qui ne donnent qu’une approximation du résultat attendu, mais dont la complexité est plus faible. Pour ces raisons, la complexité des problèmes de graphes est un domaine très intéressant et largement étudié.

 Contrairement à d’autres branches des mathématiques, l’épanouissement de la théorie des graphes est assez récent. Elle a été étudiée pour la première fois en tant que théorie cohérente par Petersen en 1891, et le premier livre à paraître sur le sujet a été écrit par König en 1936. L’intérêt autour de la théorie des graphes est restée très petit jusqu’à une explosion de la recherche dans les années 1960. Cependant, elle est considérée comme ayant commencé en 1736 lorsque le grand mathématicien suisse Leonhard Euler a résolu le fameux problème des ponts de Königsberg, qui demande s’il est possible de se promener dans la ville de Königsberg (située en Prusse à l’époque) et de traverser chaqu’un de ses sept ponts exactement une fois. Finalement, on a vu que le problème des ponts de Königsberg pouvait être exprimé comme un problème de théorie des graphes, bien que les graphes n’aient jamais été mentionnés par Euler, un domaine qui n’existait pas en 1736. Cela a conduit au concept de graphes Eulériens. Cependant, la théorie des graphes s’est légèrement développée depuis cette époque. C’est peut-être une question demandant de combien de couleurs avons-nous besoin pour colorer une carte planaire ? qui a stimulé la recherche dans le domaine. Posée par Francis Guthrie en 1852 alors qu’il colorier la carte d’Angleterre. Il a suggéré que quatre couleurs étaient suffisantes pour colorer la carte afin qu’aucune région partageant une frontière commune ne reçoive la même couleur, ce qu’on a appelée conjecture des quatre couleurs. Au siècle suivant, une grande quantité de travaux et de théories ont été développés pour prouver la conjecture des quatre couleurs, ceci a notamment contribué au développement de la théorie des graphes. Après de nombreuses fausses tentatives, la conjecture des quatre couleurs a finalement été résolue en 1976 par Appel et Haken. La question posée par Guthrie a donné naissance au sujet probablement le plus populaire de la théorie des graphes, à savoir la coloration des sommets. De nombreuses variantes de colorations de graphes ont été définies et étudiées depuis lors, transformant la coloration de graphes en une théorie très riche marquée par de nombreux excellents résultats.

Références 

• K. Dliou, Studies of some graph invariants with constraints on the distance, PhD thesis (2023), ENSA Agadir, UIZ.