Le Théorème de quatre couleurs

Benjamin Werner

Projet Informatique - INF431 2014 - promo X2012


Le théorème des quatre couleur est bien connu. Il dit qu'il est toujours possible de colorier une carte (resp. un graphe) planaire de manière à ce que deux régions contigües (resp. deux sommets voisins) n'ont pas la même couleur. C'est donc un énoncé particulièrement simple à comprendre.

Il y a un contraste frappant entre cette simplicité de l'énoncé et la complexité de la preuve. Il faut remarquer, et c'est la raison d'être de ce sujet, que cette complexité n'est pas une difficulté mathématique, mais simplement une complexité combinatoire: le nombre de cas à considérer fait que cette preuve ne peut être effectuée par un humain, mais exige l'utilisation de l'ordinateur.

Le travail demandé dans ce sujet est d'écrire un programme qui effectue la vérification de cette partie de la preuve. Cela demande de passer d'abord un peu de temps pour comprendre cette  preuve. Même si elle n'est pas triviale, elle n'utilise pas de concepts mathématiques très sophistiqués.

On trouvera :



Pour aller plus loin :