NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 25/07/2016

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

 

Géométrie

 

Topologie

 

Sommaire de cette page

>>> INDEX

 

>>> Situation en résumé

>>> Approche

>>> Exemples

>>> Applications

>>> Anglais

>>> Vocabulaire

>>> Ce que l'on sait

 

 

Chose inouïe, c'est au-dedans de soi qu'il faut regarder le dehors.   Victor Hugo

 

Le blanc est bien une couleur, n'est-ce pas? Oui, bien sûr! Le noir est bien une couleur, n'est-ce pas? Oui, évidemment! Alors de quoi tu te plains, je t'ai bien vendu une télévision couleur …

 

Savez-vous que, en anglais, "off-color humor" signifie humour douteux, vulgaire, trash, cru; mauvaise plaisanterie.

Voir Pensées & humour / Faux-amis

 

 

 

Théorèmes des quatre couleurs (TQC)

Le coloriage: une activité de détente? Pas en mathématique ! C'est un problème de mathématiques combinatoires.

 

Trouver le nombre minimum de couleurs, en l'occurrence quatre, pour colorier une carte a demandé 124 ans d'efforts et 1200 heures de calcul pour la démonstration finale en 1976.

Traduction: Avec quatre couleurs, on colorie toute carte plane*

* Cartes planes classiques, hors cartes enroulées sur un cylindre ou un tore ou …

 

Voir ConjectureGlossaire  

 

 

 

 

Navigation

L'index est THÉMATIQUE.

Pour suivre la chronologie des explications, cliquez sur SUITE en bas de chaque page.

Pour une idée immédiate et concise de la DÉMONSTRATION   >>>

La chronologie HISTORIQUE donne également une bonne idée de la démonstration >>>

 

 

Théorème des quatre couleurs (TQC) – INDEX

 

Général

 

 

Démonstration

 

 

Combien de couleurs

 

 

*    Conjecture des trois couleurs de Steinberg infirmée

 

Outils

 

 

Cartes spécifiques

 

 

Amusements et divers

 

 

 

 

 

 

En résumé

Le problème des quatre couleurs remonte à une question posée en 1852 concernant la coloration des cartes représentant les comtés d'Angleterre.

 

Il s'agissait de choisir un couleur pour chaque région sans frontière de même couleur, exception faite aux points de frontière entre plus de deux régions.

 

Frontières de couleurs différentes

La même couleur peut se retrouver en un point multiple de frontière. Ici, le point est quadruple (D = 4)

 

La situation peut être résumée de la manière suivante:

*    Il sûr qu'il faut plus de trois couleurs, car de nombreux contre-exemples le montrent;

*    Si D est le nombre maximum de lignes de frontière en un point multiple, alors la quantité de couleur est au plus égale à D + 1;

*    Un raisonnement très simple réduit cette quantité à six;

*    Puis, sans trop de peine, le théorème des cinq couleurs sera démontré; et

*    Le minimum est bien quatre couleurs. Conjecture démontrée en 1976 avec force emploi d'ordinateur. À ce jour (2014), il n'existe aucune preuve classique.

 

3

Contre

exemples

4

Démo.

en 1976

5

Démo.

en 1878

6

Démo.

simple

D+1

Démo

simple

>>>

>>> 

>>> 

>>> 

>>>

 

Question subsidiaire: quelles sont les conditions requises pour que trois couleurs soient suffisantes.

Croyez-le ou non! Le problème des trois couleurs est encore plus difficile que le problème des quatre couleurs.

 

Trois couleurs sont suffisantes, y compris avec le fond de carte.

 

 

L'outil de travail pour résoudre ces problèmes est le graphe planaire.

Un point "capitale" de la région est choisi (quelconque). Il prend la couleur de sa région. Des segments relient les capitales des régions mitoyennes.

Les capitales sont les sommets du graphe, et les segments en sont les arêtes.

 

Ces deux représentations – régions ou graphe – sont équivalentes.

 

 

 

Les quatre COULEURS – Approche

 

Combien de couleurs ?

 

Quelle que soit la complexité d'une carte géographique

quatre couleurs suffisent pour la colorier

sans que deux frontières soient de la même couleur.

 

On dit que les cartes son 4-coloriables

Ou encore que le nombre chromatique des cartes est 4.

 

Le théorème s'applique à la coloration des cartes géographiques comme à celle des faces des polyèdres ou encore celle des sommets d'un graphe planaire.

Note: on dit coloration et non coloriage.

 

Les démonstrations

Elle existe pour cinq couleurs depuis longtemps. Mais, il a fallu avoir recours aux ordinateurs pour démontrer récemment que quatre couleurs suffisent.

La coloration du damier ne nécessite que deux couleurs, mais colorier un volume comme un globe, un tore ou un bretzel nécessitent six ou sept couleurs.

 

Point multiple

Un point multiple sur une carte est un point où plus de trois régions se rejoignent. La quantité D de régions limitrophes (ou quantité d'arêtes en un sommet dans la présentation en graphe) est le degré du sommet.

 

Exemple avec le centre de ces cercles

 

Une première piste: selon la parité du degré du point multiple :

*    pair:                      2 couleurs; et

*    impair: au moins 3 couleurs.
 

 

 

 

Exemples pour se familiariser

 

Deux couleurs

Un dessin fait en un seul coup de crayon est toujours coloriable avec deux couleurs.

 


 

 

Trois couleurs

Notez que chaque région est mitoyenne avec une quantité paire de régions, y compris le fond.

La région centrale comme le fond sont mitoyens avec six régions.

 

Quatre couleurs

Cette configuration avec présence d'un point multiple impair conduit à quatre couleurs: trois pour la figure et une pour le fond.

 

Plus de  couleurs

La coloration de volumes exige jusqu'à sept couleurs.

Certains objets utopiques en exigent davantage.

Six couleurs sont nécessaires pour la coloration d'un tore. C'est le cas aussi pour la bouteille de Klein.

 

 

 

 

Application particulière

Nos téléphones portables fonctionnent quel que soit l'endroit où nous nous trouvons. Pour cela le territoire est couvert d'antennes qui rayonnent avec une portée de 30 km (en moyenne et en zone rurale) et cela à des fréquences différentes.

La zone arrosée est découpée en polygones (hexagones) contigus. Deux hexagones contigus ne doivent pas recevoir la même fréquence.

 

La carte de Martin Gardner (le 1er avril 1975)

 

 

French and English corner

 

In 1976, the Four-Color Problem was solved: every map drawn on a sheet of paper can be colored with only four colors in such a way that countries sharing a common border receive different colors.

The four color theorem is sometimes known as the four color map theorem or Guthrie's problem.

 

Vocabulaire anglais et français

Français

Anglais

Commentaires

Anneau

Ring

Arêtes correspondant aux régions entourant une région donnée.

Carte

Map

Ensemble de régions partageant des frontières non réduites à un point.

Carte à cinq couleurs

Five-chromatic map

Carte hypothétique qui exigerait d'utiliser cinq couleurs.

Carte plane

Planar map

Carte classique, posée sur une table! Non enroulée sur un cylindre ou une sphère ou un tore …

Carte normale

Normal map

Aucun pays en n'englobe d'autres, et

Pas plus de trois pays se rejoignent en un point.

Chaine

Chain

Ensemble de régions qui se suivent avec deux couleurs alternées.

Circuit

Circuit

Chaine fermée: région de départ égal région d'arrivée.

Configuration

Configuration

Ensemble formé d'une région spécifique et de toutes ses régions voisines.

Dans un graphe, ensemble de sommets associé à toutes les arêtes les reliant.

Une configuration est une partie d'une triangulation incluse dans un circuit.

Configuration réductible

Reducible configuration

Une configuration est réductible si elle ne peut pas être contenue dans une triangulation du graphe le plus petit qui ne peut pas être 4-coloriable.

Degré

Degree

Multiplicity

Quantité d'arêtes sur un sommet.

Ensemble inévitable

Inevitable set

Un ensemble inévitable est un ensemble de configurations qui ont la propriété que toute triangulation doit contenir une de ces configurations.

Graphe

Graph

Un graphe peut être construit à partir de toute carte: les régions sont les sommets (pensez à la capitale)  et les arêtes relient les capitales des régions ayant des frontière communes.

Graphe cubique

Graphe triangulé

Carte normale

Cubic graph

Triangulated graph

Normal map

Graphe dont tous les sommets sont de degré 3.

L'indice chromatique d'un graphe cubique est 3 ou 4.

Graphe triangulé

Triangulation

Graphe d'une carte normale. Tous les sommets comportent trois arêtes. 

Pour tout graphe une triangulation est faisable en ajoutant des arêtes divisant les faces qui ne le sont pas en triangles.

Pays voisins

Neighboring countries

Partageant un bout de frontière en commun.

Région

Region

Chaque partie de la carte délimitée par des frontières fermées.

Snark

Snark

Graphe cubique connexe, sans isthme et d'indice chromatique égal à 4.

Graphe dans lequel chaque sommet a trois voisins, et dont les arêtes ne peuvent pas être colorées avec seulement trois couleurs sans que deux arêtes de même couleur ne se rencontrent en un même sommet.

Stable

Stable

Sous-ensemble de sommets d'un graphe, deux à deux non adjacents (sommets qui peuvent prendre la même couleur).

La coloration d'un graphe consiste à le partitionner en stables.

 

 

 

Ce que l'on sait (en résumé)

2 couleurs

Une carte planaire est 2-coloriable si et seulement si tous les points multiples internes sont de degré pair.

>>>

2 invariant d'Euler

Pour tout graphe planaire: sommet – faces + faces = 2 (Euler).

>>>

3 frontières

Si une carte triangulée (plane) est 4-coloriable, alors la carte d'origine est 4-coloriable.

>>>

4 couleurs

Toute carte planaire est 4-coloriable (Apple et Hagen).

>>>

4 inévitables

Toute carte triangulée contient au moins un des quatre configurations inévitables suivantes: digone, triangle, carré ou pentagone.

>>>

< 5 frontières

Toute carte planaire contient au moins un pays qui à cinq voisins ou moins. (Kempe).

>>>

5 régions

Il est impossible de disposer cinq régions de telle façon qu'il existe des frontières communes entre tous les couples possibles. (De Morgan).

>>>

k couleurs

Pour tout k, il existe un graphe sans triangle qi nécessite au moins k couleurs. (Erdös)

Maximum

Il suffit de D + 1 couleurs pour colorer un graphe planaire, D étant le degré maximum parmi les sommets du graphe.

>>>

 

 

 

 

 

 

 

Suite

*    Graphes et quatre couleurs

*    Quatre couleursIndex

*    Nombres en couleurs (triplets de Pythagore colorés)

Voir

*    Cinq pays

*    Couleurs

*    Démonstration

*    Énigme des carrés mitoyens

*    Graphe à 2 couleurs

*    Indicateur d'Euler-Poincaré

*    Introduction à la topologie

*    Quadrichromie

*    Ruban de Moebius

*    TopologieGlossaire

*    TopologieIndex

DicoNombre

*    Nombre 4

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Geometri/TopoQuat.htm

 

Références

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

Note: la quantité d'ouvrages écrits sur le sujet est très importante, surtout en anglais. Certains sont en partie consultable sur Internet.

Sites

*    Le théorème des quatre couleurs – Georges Gonthier

*    Chapitre 4 – Le théorème des quatre couleurs – Université de La Rochelle

*    Francis Gunthrie – Bibm@th.net

*    The four colour theorem – Mac Tutor History of Mathematics

*    The four colour theorem

*    The Mathematics Behind the Maps