QUATRE COULEURS PROBLÈME DES
Carte mentale
Élargissez votre recherche dans Universalis
Position du problème
On veut colorier une carte géographique tracée sur le plan (ou la sphère) de manière que deux régions voisines soient toujours de couleurs différentes. Précisons que chaque région est connexe (d'un seul tenant) et que deux régions voisines ont au moins une ligne frontière en commun. Dans ces conditions, les cartographes ont constaté que toute carte pouvait être coloriée avec quatre couleurs au plus. C'est cette proposition, appelée conjecture des quatre couleurs, qui a été démontrée par Kenneth Appel et Wolfgang Haken.
Dans les travaux récents, on préfère considérer le graphe dual de la carte, qu'on obtient en choisissant dans chaque région un point intérieur (son chef-lieu) et en reliant par une courbe simple (arête) les chefs-lieux de deux régions voisines. Ce graphe peut être tracé sur le plan sans que deux arêtes se coupent (graphe planaire topologique) ; par nature, il ne comporte pas de boucles. Ce sont les chefs-lieux que l'on colorie. La proposition s'énonce alors :
Les sommets d'un graphe planaire sans boucles peuvent être coloriés avec quatre couleurs de manière que toute arête ait ses extrémités de couleurs différentes.
1
2
3
4
5
…
pour nos abonnés,
l’article se compose de 4 pages
Écrit par :
- Jean MAYER : docteur ès lettres, professeur à l'université Paul-Valéry de Montpellier
Classification
Autres références
« QUATRE COULEURS PROBLÈME DES » est également traité dans :
APPEL KENNETH (1932-2013)
Le mathématicien américain Kenneth Appel apporta, avec son confrère Wolfgang Haken, la preuve du problème dit des quatre couleurs en 1976. Kenneth Ira Appel naît le 8 octobre 1932, dans le quartier new-yorkais de Brooklyn. Il étudie les mathématiques au Queens College de New York, où il décroche une licence en 1953, puis à l’université du Michigan, où il passe un doctorat en 1959. Dès l’obtenti […] Lire la suite
INFORMATIQUE ET VÉRITÉ MATHÉMATIQUE
Dans le chapitre « Preuves mathématiques classiques avec ordinateur » : […] Si l'ordinateur peut conduire à de quasi-certitudes en dehors de la méthode hilbertienne, il peut aussi produire des preuves mathématiques classiques. Plusieurs cas sont possibles, que nous allons présenter en insistant sur ce qui les distingue. Certaines techniques de démonstration automatique produisent des démonstrations qu'aucun humain n'avait découvertes sans aide informatique, mais qui, une […] Lire la suite
Voir aussi
Pour citer l’article
Jean MAYER, « QUATRE COULEURS PROBLÈME DES », Encyclopædia Universalis [en ligne], consulté le 19 avril 2022. URL : https://www.universalis.fr/encyclopedie/probleme-des-quatre-couleurs/