Chapitre IV - La course à l'héritage - L’Agrapheur – Intrigues policières à saveur mathématique

Polytechnique > L’Agrapheur > Chapitre IV - La course à l'héritage

Chapitre IV - La course à l'héritage

Dans l’affaire de l’héritage de Monsieur Grumbacker, Manori prouve que l’auteur du téléphone anonyme est un escroc grâce aux graphes dits « de ligne ». Il s’agit du graphe d’intersection des arêtes d’un graphe. Plus précisément, étant donné un graphe quelconque, que je noterai G, on peut construire un nouveau graphe H dont les sommets représentent les arêtes de G et tel que deux sommets sont reliés par une arête dans H si, et seulement si, les deux arêtes correspondantes dans G ont une extrémité en commun. L’un des premiers résultats importants concernant cette classe de graphes est dû à Hassler Whitney [Whi32] qui a réussi à démontrer qu’à une exception près, on peut reconstruire le graphe original G de manière unique en connaissant son graphe de ligne H. En 1968, Beineke [Bei68] a démontré qu’un graphe de ligne est caractérisé par la non-existence d’exactement neuf sous-graphes. En d’autres termes, il a construit un ensemble de neuf graphes qui ne sont pas de ligne et il a pu démontrer qu’en choisissant un sous-ensemble quelconque de sommets dans un graphe de ligne G et en rajoutant toutes les arêtes qui relient ces sommets dans G, on n’obtient jamais l’un des neuf graphes de son ensemble. Dans l’affaire de l’héritage, Manori se rend compte que le graphe dessiné par Bonvin est l’un des neuf graphes de la liste de Beineke.

Notes pédagogiques - Les graphes de ligne