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

Médias de l’article

Réduction d'une configuration v4 d'un graphe planaire triangulé

Réduction d'une configuration v4 d'un graphe planaire triangulé
Crédits : Encyclopædia Universalis France

dessin

Réductibilité d'un quadrilatère

Réductibilité d'un quadrilatère
Crédits : Encyclopædia Universalis France

dessin

Afficher les 2 médias de l'article


Écrit par :

  • : 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)

  • Écrit par 
  • Melinda C. SHEPHERD
  •  • 380 mots

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

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 990 mots
  •  • 1 média

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/