QUATRE COULEURS PROBLÈME DES

Carte mentale

Élargissez votre recherche dans Universalis

Les réductions de Kempe

Reprenons l'ensemble inévitable de Kempe :

UK=v2,v3,v4,v5,

vi, désignant la configuration formée par un sommet de degré i, ses voisins et le circuit qu'ils engendrent.

On montre aisément que v2 et v3 sont réductibles : on obtient T' en effaçant l'intérieur du circuit C (dans le cas de C2, on simplifie aussi l'arête double en effaçant l'une des arêtes formant C2). Les circuits C2 et C3 n'utilisant pas toutes les couleurs disponibles, T est coloriable en même temps que T'.

Pour v4, la démonstration est un peu plus délicate. Nous obtenons T' en effaçant l'intérieur du circuit C4 = A B C D). Si C4 n'utilise que deux ou trois couleurs, on peut colorier V : on dit que ces coloriages du circuit séparateur sont directs (ils s'étendent directement à la partie intérieure de la configuration). Mais, si A, B, C, D portent des couleurs toutes différentes (soit dans l'ordre cyclique : 1, 2, 3, 4), le coloriage n'est plus directement possible.

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

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

Réduction de v4. Les chiffres 1, 2, 3, 4 symbolisent les couleurs attribuées aux sommets. Si l'on trace un arc BD séparant A de C, on peut colorier les sommets C, C', C', etc., respectivement avec les couleurs 1, 3, 1, etc. Il est alors possible de colorier V en utilisant la couleur 3. 

Crédits : Encyclopædia Universalis France

Afficher

Kempe résolut cette difficulté en considérant dans T' le sous-graphe constitué des sommets de couleur 1 ou 3 et des arêtes joignant un sommet de couleur 1 à un sommet de couleur 3 : ce sous-graphe sera désigné par G1,3. On définira de même le sous-graphe G2,4, correspondant à l'autre paire de couleurs.

Ces sous-graphes ne peuvent avoir un sommet commun (qui devrait alors être de deux couleurs différentes). Si, dans G1,3, il n'existe pas de chaîne d'arêtes reliant A à C, nous échangerons les couleurs 1 et 3 dans la composante de G1,3 qui contient C, obtenant un nouveau coloriage correct de T' où C4 ne comportera plus la couleur 3, laquelle sera disponible pour colorier V. Si G1,3 contient une chaîne reliant A à C, cette chaîne sépare G2,4 en deux parties et B ne peut pas être relié à D dans G2,4. Une modification similaire de la précédente permet donc d'utiliser pour D la couleur 2, libérant la couleur 4 pour colorier V. En résumé, la topologie du plan permet de modifier le coloriage de C4 de l'une des deux manières suivantes :

1 2 3 41 2 1 4 ou 1 2 3 41 2 3 2.

1 2 3 4 est appelé coloriage indirect de la configuration.

L'argument de Kempe est un algorithme inductif : il est légitime de considérer comme coloriages indirects non seulement ceux qui se ramènent à des coloriages directs, mais aussi ceux qui se ramènent à des coloriages déjà reconnus comme indirects. Si tous les coloriages du circuit séparateur sont directs ou indirects, la configuration est réductible. Mais il peut subsister des coloriages qui résistent à l'argument de Kempe. Si ces coloriages résiduels sont incompatibles avec les conditions géométriques imposées à T' (qui restreignent les possibilités de coloriage du circuit séparateur), on a encore une réduction, d'un type plus général dû à G. D. Birkhoff. Si l'on ne trouve pas de modification (T → T') éliminant tous les coloriages résiduels, la réduction échoue (ce qui n'est pas pour autant une preuve d'irréductibilité !). Dans la plupart des cas, les coloriages possibles sont si nombreux que leur étude nécessite l'emploi de l'ordinateur.

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