théorème des quatre couleurs

COMBINATOIRE

Ce théorème énonce la possibilité de colorier avec quatre couleurs seulement une carte géographique sans que deux pays voisins aient la même couleur.
Conjecturé en 1852 par le mathématicien anglais Francis Guthrie , cela n’a pu être démontré qu’en 1977 par Wolfgang Haken et Kenneth Appel , spécialistes de topologie algorithmique. Cette démonstration, la première nécessitant l’usage d’un ordinateur a été contestée. Depuis, d’autres programmes ont été écrits permettant de vérifier la validité du théorème.

Ce théorème – et les méthodes informatiques permettant sa démonstration – 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.