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 :