QUATRE COULEURS PROBLÈME DES

Carte mentale

Élargissez votre recherche dans Universalis

Le principe de déchargement

Nous ne pourrons qu'esquisser dans son principe la description de la stratégie qui permet de constituer un ensemble inévitable de configurations. Nous savons déjà que v2, v3 et v4 sont réductibles. Reprenons l'égalité (1), dont le second membre est strictement positif. On peut considérer que chaque sommet de degré i apporte au premier membre une contribution égale à 6 — i, positive pour i = 5, nulle pour i = 6, négative pour les sommets de degré ≥ 7, qu'on appellera sommets majeurs. On définit un « processus de déchargement » qui, sans changer la somme totale des charges 6 — i, répartit la charge positive de chaque sommet de degré 5 sur les sommets majeurs qui en sont à la distance 1 ou 2 (mesurée en arêtes du graphe). Ce processus complexe, comportant de nombreux cas particuliers, aboutit à l'alternative suivante :

1o Les charges négatives suffisent à compenser les charges positives : on dit alors que le graphe est totalement déchargé. La somme totale des charges est ≤ 0, ce qui contredit (1).

2o Il reste des charges positives non compensées, mais les sommets qui les portent font partie de configurations appartenant à un ensemble U. D'après le 1o, U est un ensemble inévitable. Il suffit donc de réduire toutes les configurations appartenant à U pour obtenir un ensemble inévitable de configurations réductibles et démontrer le théorème.

Réductibilité d'un quadrilatère

Dessin : Réductibilité d'un quadrilatère

Réductibilité du quadrilatère (A. B. Kempe): dans un coloriage des régions, réduction d'une région ayant quatre voisines. C'est la réduction de la figure 1 présentée sous forme duale. Ici, on a colorié la carte, c'est-à-dire les régions et non les sommets. Dans le coloriage du bas,... 

Crédits : Encyclopædia Universalis France

Afficher

L'ordinateur a été utilisé dans les deux phases du problème : construction de l'ensemble U, réduction des configurations appartenant à U. S'il a pu être éliminé après coup de la première phase (processus de déchargement), il n'en est pas de même des nombreuses réductions : un circuit C14, par exemple, possède 199 291 coloriages non équivalents avec quatre couleurs, et chacun doit être étudié. Une démonstration du théorème sans intervention du calcul électronique, si elle est possible, exigera probablement des outils logiques d'une nature toute différente et jettera peut-être une lumière nouvelle sur la difficile conjecture de Hadwiger qui est directement liée au problème des quatre couleurs.

Définition. On appelle contraction d'un graphe G la modification consistant à remplacer deux sommets A, B, joints par une arête, par un sommet C qu'on relie à tous les sommets originairement voisins de A et/ou de B.

Conjecture. Par une suite de contractions, un graphe G dont le coloriage exige n couleurs peut être transformé en Kn le graphe complet de n couleurs.

Cette conjecture, démontrée par G. A. Dirac pour n ≤ 4, est équivalente pour n = 5 au théorème des quatre couleurs (K. Wagner). Pour n > 5, le problème reste ouvert.

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 15 avril 2022. URL : https://www.universalis.fr/encyclopedie/probleme-des-quatre-couleurs/