QUATRE COULEURS PROBLÈME DES
Carte mentale
Élargissez votre recherche dans Universalis
L'irréductibilité de v5 et ses conséquences
Kempe crut pouvoir réduire sa dernière configuration (le département ayant cinq voisins, ou, dans le langage dual que nous adoptons, v5) en appliquant deux fois, simultanément, son argument au circuit séparateur C5. Il fallut onze ans pour que P. J. Heawood (1890) prouvât l'illégitimité de cette double modification, en signalant de plus que l'argument de Kempe suffisait à démontrer le théorème des cinq couleurs, résultat plus faible (tout graphe planaire sans boucles est coloriable avec cinq couleurs).
La théorie des réductions, étudiée systématiquement par de nombreux auteurs (le travail fondamental a été accompli en particulier par H. Heesch), n'est pas encore achevée. On ne possède aucun critère général pour la réductibilité d'une configuration. Néanmoins, l'usage des réductions sur une échelle gigantesque a permis à Appel et Haken de contourner l'obstacle posé par l'irréductibilité de v5 et de triompher du problème.
Près de cinq cents pages de raisonnements, dix mille diagrammes analysés, douze cents heures de calcul sur des ordinateurs de haute performance, dix milliards de décisions logiques élémentaires : tel est le bilan, dressé par les auteurs, des moyens mis en jeu. Dans l'ensemble inévitable de configurations, v5 a fait place à 1 405 configurations dont la réductibilité a pu être prouvée par l'ordinateur – ou plutôt par trois ordinateurs de performances 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
Pour citer l’article
Jean MAYER, « QUATRE COULEURS PROBLÈME DES », Encyclopædia Universalis [en ligne], consulté le 14 avril 2022. URL : https://www.universalis.fr/encyclopedie/probleme-des-quatre-couleurs/