|
|||||||||||||||||||||||||
|
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 Conjecture
– Glossaire
|
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 >>> |
|
|
||||||||||||||
|
Général |
|
|||||||||||||
|
Démonstration |
|
|||||||||||||
|
Combien de couleurs |
|
|||||||||||||
|
Outils |
|
|||||||||||||
|
Cartes spécifiques |
|
|||||||||||||
|
Amusements et divers |
|
|||||||||||||
|
|
||||||||||||
|
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:
|
||||||||||||
|
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. |
|||||||||||
|
|
|
|
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 :
|
|
|
|
||
|
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. |
|
|
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)
|
|
|||
|
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. |
|
|
|
|||
|
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 |
|
|
Voir |
|
|
DicoNombre |
|
|
Cette page |
http://villemin.gerard.free.fr/Wwwgvmm/Geometri/TopoQuat.htm |
|
Les
premières pages sont consultables
en e-book
Note: la quantité d'ouvrages
écrits sur le sujet est très importante, surtout en anglais. Certains sont en
partie consultable sur Internet. |
|
|
Sites |
|
