Théorème des quatre couleurs
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
Depuis le milieu du XIXe siècle, le problème des quatre couleurs fascine les amateurs de géométrie et irrite les mathématiciens. Et pourtant il ne s'énonce qu’en quelques mots :
- « Il est possible, avec seulement quatre couleurs, de colorier n'importe quelle carte géographique de telle façon que deux pays ayant une frontière commune ne soient dans aucun cas de la même couleur. »
Ce théorème des quatre couleurs, observé et énoncé en 1852 par Francis Guthrie cartographe anglais, est un problème de coloration appliqué à un graphe planaire, les sommets représentant les pays, les arcs représentant l'existence d'une frontière commune. Ce problème, devenu une énigme mathématique, doit sa célébrité au contraste entre la simplicité de son exposé et la complication des innombrables recherches de solutions dont aucune n'a vraiment l'élégance chère aux mathématiciens.
On ne trouvait pas de contre-exemple de cette affirmation empirique. Restait à démontrer le problème suivant.
- « Peut-on colorier une carte avec quatre couleurs de sorte que deux pays ayant une frontière commune (autre que réduite à un point) n'aient jamais la même couleur ? »
Une démonstration publiée en 1879 par Kempe, s'est révélée comporter une erreur. Il a fallu attendre près d'un siècle de recherche pour voir aboutir une démonstration valide.
En 1976, deux américains Kenneth Appel et Wolfgang Haken affirment avoir démontré le théorème des quatre couleurs. Leur démonstration partage la communauté scientifique : pour la première fois, en effet, la démonstration exige l'usage de l'ordinateur pour étudier les 1200 cas critiques. Le problème de la validation du théorème se trouve alors déplacé vers le problème de la validation :
- d'une part de l'algorithme d'exploration
- d'autre part de son implémentation sous forme de programme
Depuis 1976, l'algorithme d'Appel et Haken a été repris et simplifié par d'autres chercheurs. D'autres programmes informatiques, écrits de façon indépendante du premier, aboutissent au même résultat. Il existe ainsi une version entièrement formalisée, formulée avec Coq qui prouve que tout graphe planaire est 4-coloriable.
Paul Erdös pensait que le théorème des quatre couleurs était "un problème subtil et non pas un problème complexe". D'après lui une démonstration simple, et même très simple, devrait exister. Mais pour cela il faudrait "compliquer le problème" et imaginer la formulation d'un ensemble de points plus vaste qu'un graphe-plan et incluant celui-ci.
Un jeune mathématicien a proposé il y a quelques années de concevoir dans l'espace des ensembles de points liés par la contrainte d'impossibilité de liaison entre plus de quatre points liés deux à deux. Mais il n'a pu prouver qu'un graphe-plan issu d'une carte géographique était "nécessairement" un sous-ensemble de l'un de ces graphes dans l'espace (pour 9 points il y a 6 types de graphes-espace).
[modifier] Utilisation pratique
D’autres problèmes plus pratiques peuvent se réduire à la résolution de coloration de graphe, la solution peut alors être appliquée pour améliorer l'organisation de tâches.
- Organiser un examen suivant les matières que doit passer chaque étudiant. Comment mettre en parallèle plusieurs épreuves sans léser un candidat ?
- Optimiser l'utilisation des machines de travail. Comment mettre en parallèle des fabrications utilisant plusieurs machines ?
- Problème d'incompatibilité. Comment faire cohabiter des personnes ou animaux en tenant compte de leur incompatibilité ?
 |
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
