Chapitre II - Les villas du Bellevue - L’Agrapheur – Intrigues policières à saveur mathématique

Polytechnique > L’Agrapheur > Chapitre II - Les villas du Bellevue

Chapitre II - Les villas du Bellevue

Le deuxième chapitre est consacré aux graphes « planaires ». Il s’agit de graphes que l’on peut dessiner sur une surface plate sans que les arêtes se croisent. Lorsqu’on dessine un graphe avec des arêtes qui se croisent, cela ne signifie pas que celui-ci n’est pas planaire. En effet, il se peut qu’en déplaçant les sommets, on réussisse à éviter tous les croisements. Un bon exemple est donné dans le dernier chapitre, lorsque Manori tente de résoudre la deuxième grille de sudoku. Le premier graphe proposé par l’apprentie sudokiste comporte beaucoup de croisements. Par exemple, l’arête qui relie le sommet A au sommet 3 croise quatre arêtes, celles reliant D à 1, D à 2, E à 1, et E à 2. Manori dessine ensuite une autre représentation de ce même graphe, en évitant tous les croisements. Le graphe dessiné par Lei est donc planaire.

Les graphes planaires ont été popularisés par l’Écossais Francis Guthrie qui, en 1852, s’est demandé s’il est possible de colorer toutes les cartes de géographie à l’aide de quatre couleurs uniquement, sans que deux pays ayant une frontière commune aient la même couleur. En représentant chaque pays par un sommet et en reliant deux sommets par une arête si, et seulement si, les deux pays représentés par ces sommets ont une frontière commune, on obtient un graphe planaire. Francis Guthrie a donc voulu savoir s’il est toujours possible de colorer les sommets d’un graphe planaire en utilisant uniquement quatre couleurs, avec comme unique contrainte que les extrémités de chaque arête doivent être de couleur différente (ce qui est équivalent à demander que les pays ayant une frontière commune aient des couleurs distinctes). Ce n’est qu’en 1976 que Kenneth Appel et Wolfgang Haken ont réussi à démontrer que quatre couleurs sont toujours suffisantes [App89]. Cette preuve a nécessité l’usage intensif d’ordinateurs, et il est impossible de vérifier à la main que tous les cas traités par l’ordinateur ne comportent pas d’erreur. La communauté mathématique est actuellement divisée en deux camps, selon qu’on accepte définitivement cette démonstration ou qu’on pense que tout reste à faire. Des efforts ont été fournis pour simplifier cette démonstration. Une version plus courte est parue dans [Rob97].

Les graphes planaires ont déjà fait l’objet de nombreuses études bien avant que Francis Guthrie ne pose sa question de coloration. Par exemple, tel qu’il est mentionné dans le chapitre II, le célèbre mathématicien suisse Leonhard Euler a démontré en 1736 qu’il existe un lien entre le nombre de sommets, le nombre d’arêtes et le nombre de faces dans un graphe planaire. Le lecteur intéressé par les graphes planaires peut en apprendre beaucoup plus en consultant, par exemple, le livre écrit par Nishizeki et Chiba [Nis88].

Notes pédagogiques - Les graphes planaires