Chapitre VII - L'homme à la cagoule - L’Agrapheur – Intrigues policières à saveur mathématique

Polytechnique > L’Agrapheur > Chapitre VII - L'homme à la cagoule

Chapitre VII - L'homme à la cagoule

Pour réussir à mettre un visage sur l’homme à la cagoule, Manori utilise, au chapitre VII, le concept de coloration des sommets d’un graphe. Nous en avons déjà parlé dans le cadre du chapitre II. Alors que Francis Guthrie s’intéressait à la coloration des sommets d’un graphe planaire, ce qui peut toujours se faire à l’aide de quatre couleurs, ce concept peut être étendu à tous les graphes. Il s’agit toujours d’attribuer une couleur à chaque sommet de telle sorte que chaque arête ait ses deux extrémités de couleur différente. De nombreux problèmes peuvent être modélisés en termes de coloration des sommets d’un graphe. Dans des problèmes d’horaires, par exemple, on associe un sommet à chaque tâche à planifier et on relie deux sommets par une arête lorsque les deux tâches correspondantes sont incompatibles, en ce sens qu’elles ne peuvent pas avoir lieu simultanément. Construire un horaire consiste alors à colorer les sommets du graphe, chaque couleur correspondant à une période différente de l’horaire. En imposant que les extrémités d’une arête soient de couleur différente, on évite de planifier deux tâches incompatibles à la même période. Dans l’affaire de l’homme à la cagoule, chaque sommet représente un prisonnier et une arête relie deux d’entre eux s’ils n’ont pas travaillé au même endroit. Puisque les 17 prisonniers devaient en principe se trouver dans l’un des trois établissements hospitaliers de la ville de Sion, trois couleurs devraient être suffisantes théoriquement pour colorer tous les sommets de ce graphe. Manori a observé que tel n’était pas le cas et il a réussi à démontrer que ce n’est qu’en supprimant Lambert du graphe (c’est-à-dire le sommet I) qu’on peut obtenir une coloration qui ne contredise pas les témoignages.

Le livre de Jensen et Toft [Jen95] permet d’en apprendre davantage sur les problèmes de coloration alors que celui de Kubale [Kub04] s’intéresse plus particulièrement aux extensions et généralisations de ce concept, le but étant de disposer de modèles collant le plus possible à la réalité.

Notes pédagogiques - Colorations des sommets