Dans le monde des mathématiques et de l’informatique, les graphes servent à modéliser des systèmes complexes ayant des applications dans une multitude de disciplines.
Un graphe est composé d’un ensemble de nœuds (aussi appelés sommets) reliés par paires par des arêtes. Les nœuds du graphe représentent des entités individuelles, tandis que les arêtes représentent les liens entre elles.
On peut se servir de graphes pour représenter un large éventail de situations réelles : réseaux routiers, réseaux informatiques et de communication, réseaux sociaux, représentations moléculaires, réseaux sous-jacents aux marchés financiers, etc. En modélisant ces situations à l’aide de graphes, les chercheuses et chercheurs peuvent analyser divers phénomènes tels que la propagation de l’information (et de la mésinformation), la dynamique des communautés en ligne ou la migration des populations.
Malgré leur apparente simplicité, les graphes ont une structure riche et complexe qui intrigue la communauté de recherche et celle des mathématiques depuis déjà longtemps. Si certaines familles de graphes sont bien comprises, d’autres sont autrement plus compliquées et moins bien, voire très mal comprises, comme c’est le cas des graphes planaires.
Or, la professeure Vida Dujmović (Faculté de génie) a réussi à résoudre certains problèmes de vieille date en posant un théorème révolutionnaire qui répond à la question suivante : quelle est la structure générale des graphes planaires? L’existence de problèmes persistants comme ceux-là laisse souvent supposer qu’un élément fondamental de la théorie échappe à notre compréhension. Et c’est justement en cherchant à mieux comprendre les graphes planaires que la chercheuse, épaulée par ses proches collaborateurs à l’étranger Gwenaël Joret (Belgique), Piotr Micek (Pologne), Pat Morin (Canada), Torsten Ueckerdt (Allemagne) et David R. Wood (Australie), en est venue à poser le théorème de la structure de produits des graphes planaires.
Grâce à ce théorème, elle a démontré que les graphes planaires peuvent être exprimés comme un produit de deux graphes simples et bien compris, à savoir une chaîne et un graphe de largeur arborescente 8.
Ce théorème a permis à l’équipe de résoudre plusieurs problèmes tenaces, notamment une conjecture sur l’étiquetage d’adjacence datant de 1988, une conjecture en lien avec la disposition des files d’attente de 1992 et une autre sur la coloration non répétitive de 2002.
« Ça fait plus de 15 ans que le problème de la disposition des files d’attente m’inspire. J’y revenais sans cesse, munie de nouveaux outils, pour m’y attaquer sous différents angles, mais cette ultime conjecture continuait de me résister malgré les progrès réalisés au fil des années », déclare la chercheuse.
Finalement, c’est la découverte de la structure de produits qui l’a amenée à trouver la clé.
« Comme ça arrive parfois en sciences et en génie, les outils découverts dans la recherche de solution se sont avérés plus importants que le problème lui-même », explique-t-elle.
Son théorème de la structure de produits semble faire partie de ces outils, vu le grand nombre d’éminents problèmes qu’il permet de solutionner, non seulement pour la chercheuse et ses collègues, mais pour toute la communauté de recherche.
La Faculté de génie félicite la professeure Dujmović et son équipe pour leurs extraordinaires contributions à la théorie des graphes. Les personnes et les organisations qui souhaiteraient collaborer à ces travaux peuvent contacter directement Vida Dujmović.