Coloration des sommets d'un graphe planaire
Coloration des sommets d'un graphe planaire
Théorème 8: théorème des quatre couleursOn peut colorer les sommets d'un graphe planaire (sans boucles) en utilisant au plus quatre couleurs de telle sorte que toutes les arêtes aient des extrémités de couleurs différentes. |
Cette conjecture a été formulée pour la première fois par l'Écossais Francis Guthrie en 1852. Il était alors question de coloration de carte de géographie (voir exercice 1). La preuve de ce théorème n'arriva qu'en... 1976, grâce à Kenneth Appel et Wolfgang Haken. La démonstration fit grand bruit car c'est le premier théorème de l'histoire des mathématiques qui a nécessité l'usage systématique de l'ordinateur. La communauté mathématique se divisa alors en deux camps: ceux pour qui le théorème des quatre couleurs était définitivement démontré, et ceux pour qui tout restait à faire.
Colorez la carte ci-dessous en utilisant le moins de couleurs possibles, de sorte que deux pays voisins aient des couleurs différentes (cliquez sur l'image pour avoir la carte de l'Afrique sans les couleurs).
Construisez d'abord un graphe associé à cette carte, puis colorez-en les sommets.
Prenez une feuille de papier. Tracez une droite quelconque qui traverse la feuille de part en part. Recommencez l'opération n fois.
Démontrez que la "carte" ainsi obtenue peut être colorée en deux couleurs.
| Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés! |
   |
 Didier Müller, 13.2.03 |