Imprimer
Affichages : 21646

Vote utilisateur: 4 / 5

Etoiles activesEtoiles activesEtoiles activesEtoiles activesEtoiles inactives
 

Le Théorème des Quatre Couleurs.


Le théorème des quatre couleurs énonce la possibilité de colorier (on dit aussi colorer en théorie des graphes) avec quatre couleurs seulement une carte géographique sans que deux pays voisins aient la même couleur.

4couleurs france

Pour être plus précis, en n'utilisant que quatre couleurs différentes, il est possible de colorer n'importe quelle carte découpée en régions connexes (d'un seul morceau), de sorte que deux régions adjacentes (ou limitrophes), c'est-à-dire ayant toute une frontière (et non simplement un point) en commun reçoivent toujours deux couleurs distinctes.
Ainsi, chacune des régions doit recevoir une couleur différente si les régions sont deux à deux adjacentes.

Par ailleurs, il ne peut exister cinq régions connexes deux à deux adjacentes (c'est la partie facile du théorème de Kuratowski).

Application.

Ce théorème a une application pratique dans l'affectation par un opérateur mobile des fréquences GSM aux zones de couverture des stations de base de son réseau. En effet, comme dans la situation des quatre couleurs :

- un réseau GSM est modélisé, comme une carte géographique, par des hexagones contigus : chaque hexagone (appelé "cellule", d'où la notion de réseau cellulaire) correspond au rayonnement d'une station de base (environ 30 kms de diamètre en zone rurale).

- deux hexagones contigus ne doivent en aucun cas se voir attribuer la même bande de fréquences.

Histoire.


La première conjecture des quatre couleurs semble avoir été émise en 1852 par un mathématicien et botaniste Sud Africain, Francis Guthrie (1831 - 1899).

Francis Guthrie était étudiant à l'University College de Londres, où il y suivit les cours du célèbre De Morgan.
Il s'oriente ensuite vers des études de botanique, alors que son frère, Frederick Guthrie, devient mathématicien et suit aussi les cours de De Morgan.
Francis Guthrie remarque qu'il lui suffit de quatre couleurs pour colorer la carte (pourtant complexe) des cantons d'Angleterre, sans donner la même couleur à deux cantons adjacents (ayant une frontière commune).
Il demande alors à son frère Frederick, si cette propriété ne serait pas vraie en général pour toute carte plane ; celui-ci communique la conjecture à De Morgan, et en 1878 Cayley la publie.

4couleurs

La première preuve effectuée par ordinateur.