LE COLORIAGE DES CARTES
Accueil Remonter LES PONTS DE KÖNIGSBERG LES GRAPHES PLANAIRES LE COLORIAGE DES CARTES POUR CONCLURE

 

 

    La question est de savoir combien il faut de couleurs différentes, pour colorier n'importe quelle carte de géographie, de sorte que les départements ayant une frontière commune, soient de couleur différente. Question essentielle pour faire des économies de peinture. En tout cas une question de haute voltige pour les mathématiciens, puisqu'elle fait appel à la notion de graphes planaires, que nous avons déjà vue.

    Expérimentalement, il a été constaté que 4 couleurs suffisaient, mais il aura fallu attendre 1976 et la démonstration de K. Appel et W. Haken, pour pouvoir affirmer réellement ce résultat. Démonstration qui a nécessité un temps important d'ordinateur, vu le nombre considérable de configurations. Du coup sa vérification reste difficilement reproductible.

    Voici une approche très simplifiée, dans laquelle chaque département ou pays, constitue le sommet d'un graphe, les arêtes relient tous les départements ayant une frontière commune (et donc une couleur différente). Donc deux sommets reliés par la même arête doivent avoir une couleur différente.

 

PAYS EN NOMBRE IMPAIR

PAYS EN NOMBRE PAIR

 

    Il s'agit d'une approche très intuitive, (donc pas très scientifique, je m'en excuse, quoique l'intuition et les sciences, ça peut donner de bons résultats).

  1. Prenons tout d'abord le cas le moins favorable, c'est à dire celui qui pose le plus de contraintes en matière frontières communes entre les différents pays, soit un pays entièrement entouré par d'autres pays, donc il n'est pas en bord de carte. Deux cas vont se présenter, le nombre total de pays pourra être pair ou impair.
  2. Si le nombre total de pays est impair, il suffira de 3 couleurs (A, B, C).
  3. Si le nombre total de pays est pair, il faudra 4 couleurs (A, B, C, D)

    Tout pays qui viendrait se rajouter autour, même s'il a une frontière commune avec plusieurs autres pays, pourra prendre la couleur de celui qui est au centre. Les 4 couleurs répondent donc au cas le moins favorable, et permettent alors de colorier n'importe quelle carte.