NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 29/10/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

TOPOLOGIE

 

Débutants

Géométrie

QUATRE COULEURS

 

Glossaire

Géométrie

 

 

 

INDEX

Quatre couleurs

 

Géométrie

 

Topologie

 

2 couleurs

3 couleurs

4 couleurs

5 couleurs

6 et plus

 

Sommaire de cette page

>>> Quatre couleurs – Situation

>>> Ensemble inévitable de configurations réduites

>>> Toujours loin de la puissance de calcul disponible

>>> Méthode des charges de Heesch

>>> Démonstration d'Appel et Haken 

>>> Exemple de carte complexe

 

 

 

 

 

 

 

Théorèmes des QUATRE COULEURS

 

Après avoir cerné le nombre de couleurs nécessaire pour colorer une carte plane, nous avons montré que 3 n'est pas suffisant et que 5 est toujours suffisant. Montrer que 4 est suffisant fut une grande épreuve. La démonstration avec l'aide d'ordinateurs date de 1976.

 

 

 

Quatre couleurs – Situation

 

Il faut quatre couleurs dès qu'une région est entourée d'un nombre impair de régions

Point multiple impair: trois couleurs

Régions limitrophes impaires: quatre couleurs

 

 En 1898, Heawood démontre que si le degré de tous les sommets est divisible par 3, alors la carte est 4-coloriable.

 

Situation

Dans tous les cas quatre couleurs suffisent. Le théorème des quatre couleurs fut démontré en 1976 par Kenneth Appel et Wolfgang Haken sur ordinateur qui calcula pendant 1200 heures pour réussir à établir le résultat.

 

Plus tard (1997 ?), Neil Robertson, Daniel Sanders, Paul Seymour et Robin Thomas ont refait et simplifié la preuve de 1976.

 

Aucune des deux n'est assez simple pour être vérifiée à la main, mais le théorème des quatre couleurs est tout de même considéré comme définitivement acquis.

 

 

 

Ensemble inévitable de configurations réduites

 

*    Birkhohh montre que certaine configurations très importantes sont réductibles.

*    Franklin prend la suite et montre qu'une carte à cinq couleurs doit contenir au moins 22 pays.

*    Heesch introduit la méthode de dissipation de charges électriques dans le réseau (le graphe). C'est la bonne piste qui sera améliorée après lui.

*    Heesch conjecture que le nombre ne devrait pas dépasser dix mille. Quantité, en principe, traitable par ordinateur. Il met au point une méthode de réduction des configurations, nommée D-réduction. Le programme prouve bien la réductibilité mais, en cas de réponse négative, aucune conclusion ne peut être tirée. Pour prouver la réductibilité, il faut faire appel à d'autres méthodes par ordinateurs ou manuelles ou combinaison des deux (C-réduction). 

*    D'autres mathématiciens vont travailler cette question et tenter d'élargir ce nombre. En 1950, on atteint 36 seulement. On reste loin du but, loin de la définition d'un ensemble inévitable.

*    En fin des années 1960, la réductibilité était maitrisée. Pas le cas pour la recherche des inévitables ensembles de configurations.

 

 

Exemples de configurations étudiées

 

 

 

 

Toujours loin de la puissance de calcul disponible

 

*    Notion de configuration: c'est une région et ses voisines. Une carte est alors supposée complètement résolue à l'exception de quelques configurations inévitables qu'il va falloir résoudre séparément.

 

*    Les ensembles inévitables contiennent de grandes configurations  avec des anneaux immenses (18 sommets sans doute)

*    Alors qu'on imagine des calculs pour des anneaux à 11 sommets praticables sur ordinateurs. Le temps de calcul est multiplié par 4 pour un sommet de plus. Avec 14 sommets, il fallait 36 heures de calculs.

*    La solution testée par ordinateur parait inatteignable, en calculs comme en place mémoire.

 

*    Appel et Haken poursuivirent ces recherches et finalement trouvèrent qu'il n'était pas nécessaire de travailler sur des anneaux de plus de 14 sommets. Ils identifient malgré tout encore 1476 configurations différentes à résoudre.

*    On rappelle que le but est de démontrer que parmi toutes ces configurations, l'une au moins est inévitable. Laquelle impose que seule quatre couleurs sont suffisantes. Pour chacune, il faut montrer qu'en retirant un sommet, puis en le réintégrant de manière appropriée quatre couleurs suffisent.

 

 

 

  

Méthode des charges de Heesch

 

Suite aux travaux de Kempe, on sait que: une triangulation qui représente une carte minimale à cinq couleurs ne peut pas avoir de sommets avec moins de cinq arêtes.

 

Astucieusement Heesch opère une analogie électrique en associant le graphe à un circuit électrique dont il va chercher à équilibrer les charges. Il donne les charges suivantes aux sommets:

 

Charge

Nombres d'arêtes au sommet

1

5

0

6

- 1

7

Etc.

 

La somme des charges dans tout le circuit est positive (en fait égale à 12, valeur déduite de la relation d'Euler). On va redistribuer les charges autour de 0, tout en conservant la somme.

Le truc consiste à trouver une méthode de redistribution équilibrant les charges et finissant par des configurations limites, avec impossibilité d'aller plus loin.

La somme totale étant positive, il y aura toujours des sommets positifs.

 

Pour le graphe, la charge totale est toujours exactement égale à 12. Ce qui veut dire que la charge du graphe est toujours positive. 

Une charge est affectée à chaque sommet. Elle est égale à 6 – d, avec d le degré du sommet. Les sommets de degré supérieur à 6 sont donc négatifs, ce sont les sommets majeurs. Et seuls les sommets de degré égal à 5 sont positif (+1).

L'idée est d'écouler les charges positives vers les négatives des sommets majeurs, à charge totale conservée. Le but est de mettre en évidence les nouvelles charges positives qui correspondraient à des configurations réductibles.

Comme toute triangulation doit posséder des sommets de charges positives, les configurations mises en évidence par ce procédé doivent former un ensemble inévitable.

 

Exemple

Tous les sommets de charge 5 donnent 1/5 à tous les sommets voisins de charge > 6.

Alors, deux configurations inévitables subsistent:

 

En rouge

Sommet 5,5

En rouge

Sommet 6,5

 

 

 

 

Démonstration d'Appel et Haken 

 

Les procédures de réduction par les charges s'améliorent.

 

En 1970,

Haken en réduit encore le nombre. Néanmoins, le volume de calcul pour les explorer toutes est énorme; mais, cela commence à être accessible.

 

En 1972,

Wolfgang Haken et Kenneth Appel travaillent ensemble et affinent la procédure par approches d'améliorations successives. Trois ans de travail, 500 modifications plus tard et avec 1200 de calcul…

 

… En juin 1976

L'analyse de tous les cas est terminée et le théorème des quatre couleurs démontré.

 

En 1995

Nouvelle démonstration, plus simple, mais dans la même veine par Neil Robertson, Sanders, Seymour et Thomas.

 

 

Appel et Haken

Roberston et al.

Configurations inévitables

1 478

633

Règle de répartition des charges

> 300

32

 

 

Le théorème est démontré, mais la question du coloriage des cartes fait toujours l'objet de recherches intenses.

 
 

Voir Historique complet

 

 

Exemple de carte complexe

(une des cartes d'Appel et Hanken)

 

Monstre!

La démonstration repose sur l'analyse d'environ  2000 cartes particulières où l'on montre que chacune d'elles se comporte d'une certaine manière. La vérification de tous les cas particuliers est une tâche fastidieuse, qui a demandé plusieurs milliers d'heures de calcul sur ordinateur puissant. Si l'on devait rédiger cette démonstration in extenso, le texte en serait si monstrueux que personne ne vivrait assez longtemps pour le lire intégralement, et à plus forte raison pour le vérifier. 

Ian Stewart – Les mathématiques - Page 118

 

 

 

 

 

Retour

Suite

*    Cinq couleurs

*      Démonstration en bref

*      Historique – Quatre couleurs

*   Prince de Möbius

*    Quatre couleursIndex 

Voir

*    Cinq pays

*    Couleurs

*    Démonstration

*    Énigme des carrés mitoyens

*    Graphe à 2 couleurs

*    Indicateur d'Euler-Poincaré

*    Introduction à la topologie

*    Quadrichromie

*    TopologieGlossaire

*    TopologieIndex

DicoNombre

*    Nombre 4

Livre

Les premières pages sont consultables en e-book

 

*    Les mathématiques – Chapitre: le théorème des quatre couleurs – Ian Stewart – pages 117 à 126

*    Mathematics – The golden age – Keith Devlin

*    Mathematics todayChapitre: the four color problem – Kenneth Appel and Wolgang Haken – page 153 à 180

Sites

*    Voir références

Cette page

http://villemin.gerard.free.fr/aMaths/Topologi/aaaGraph/Coul4.htm