Exposé n° 84 : Résoudre des énigmes à l’aide de graphes

Un graphe est un outil mathématique très simple à visualiser car il est représenté par des points qui peuvent être reliés par des lignes. C’est par un graphe que l’on représente, par exemple, le plan d’un métro.
Malgré son apparente simplicité, sa puissance de modélisation est énorme. Les graphes permettent en effet de représenter les relations entre des éléments qui peuvent être ce qu’on veut : des atomes, des utilisateurs de Facebook, des ordinateurs, des carrefours routiers, des élèves, etc. Pour ceux qui les connaissent, ils sont partout ! Et c’est donc de façon très naturelle qu’ils possèdent des dizaines d’applications : l’organisation d’horaires, la recherche d’un plus court chemin dans un GPS, l’analyse de réseaux sociaux, la chimie,… et même la résolution d’énigmes ! Après avoir introduit ce modèle, nous explorerons sa puissance en venant à l’aide de Sherlock Holmes.

Exposé proposé par Hadrien Melot.