Seules 4 couleurs suffisent pour colorer une carte politique : comment est-ce possible ?

Alexis Tremblay
Alexis Tremblay

Combien de couleurs sont nécessaires pour colorer une carte (politique) pour que deux pays voisins ne soient pas de la même couleur ? Cela semble impossible, mais il n’en faut que quatre, quelle que soit la carte ! Ceci est démontré par un théorème mathématique appelé Théorème des quatre couleurs. Nous le voyons dans cet article, en essayant également de comprendre comment cela est possible et ce qu’est la théorie des graphes, la discipline mathématique capable de schématiser ce problème et de le résoudre.

Quatre couleurs suffisent pour colorer les régions connectées

Prenez une feuille de papier et divisez-la en combien ça coûte déclencher vous voulez avec des lignes qui le coupent d’un côté à l’autre. Peu importe le nombre de lignes que vous créez et le nombre de régions différentes que vous créez : dans tous les cas, quatre couleurs différentes suffiront pour colorer toutes les régions afin que les régions voisines n’aient pas la même couleur. Ou plutôt, dans presque tous les cas.

4 exemples de théorème des couleurs
Exemples d’images avec des régions connectées, chaque image ne contient que 4 couleurs.
Crédits : A. ArglebargleIV ; B. Charge inductive ; C. Dmharvey

La condition fondamentale pour que ce que nous disons soit vrai est que le Régions que l’on dessine sur le papier sont connectéterme géométrique facilement compréhensible de par son caractère intuitif : une région est dite connectée si et seulement si elle est il n’est pas composé de plusieurs parties (ensembles ouverts) disjoints, c’est-à-dire non voisins.

Ce que vous venez de lire est exactement le Théorème des quatre couleursqui précise ceci :

Étant donné une surface plane divisée en régions connectées, quatre couleurs suffisent pour colorer chaque région en veillant à ce que les régions voisines n’aient pas la même couleur.

Ce théorème est célèbre pour pouvoir être appliqué à cartes géographiques politiques. En fait, quatre couleurs suffisent pour représenter les régions d’Italie ou même les États du monde entier.

Carte du théorème des quatre couleurs de l'Italie

Il existe cependant des cas dans lesquels cela n’est pas applicable : alors qu’en réalité les régions ne sont pas connectées. Voyons ce que cela signifie.

Cartes sphériques et cas dans lesquels le théorème ne tient pas

Une région n’est pas connectée lorsque, contrairement à ce qui a été dit jusqu’à présent, elle est constituée de plusieurs parties voisines entre elles. Dans ce cas, la possibilité d’utiliser seulement 4 couleurs n’est plus envisageable.

5 régions non connectées du théorème des couleurs
Crédits : Inductiveload, Mrmw

Un exemple facilement compréhensible de région non connectée est celui de les états-unis d’Amérique. Si vous prenez une carte du monde, vous verrez que les États-Unis sont constitués de un bloc central de 48 Étatsdes îles Hawaï et d’un seul État isolé et sans frontière avec aucun autre État confédéré : leAlaska.

Bien que les États-Unis ne soient pas une région connectée, le monde peut toujours être coloré de quatre couleurs grâce au fait que l’Alaska est limitrophe du Canada, qui à son tour borde uniquement le reste des États-Unis. Mais imaginons un instant que le bloc central des USA soit entouré de trois États voisins comme dans l’image ci-dessous.

cas non connecté théorème des quatre couleurs

Dans ce cas il n’y a pas de solution : Il y a 5 couleurs nécessaires.

Le globe peut également être coloré avec 4 couleurs

Le nombre de couleurs dépend non seulement de la structure des régions, mais aussi par le type de surface sur lequel ils sont dessinés. En d’autres termes, le nombre minimum de couleurs dépend de la forme de la « carte du monde » sur lequel nous nous appuyons. Dans le cas de la Terre – qui a une forme sphérique – la réponse reste 4.

Cependant, il en existe un généralisation du théorème des quatre couleurs qui définit le nombre de couleurs nécessaires en fonction du type de surface sur laquelle nous nous trouvons. Un exemple amusant est celui de Donut, sur lequel la réponse serait 7 couleurs.

Projection_color_torus

Mais on pourrait se demander : est-il vrai que toute carte (avec des régions connectées) n’a besoin que de 4 couleurs pour être colorée, ou n’avons-nous tout simplement pas encore trouvé de cas qui contredit cette hypothèse ?

Ici apparaît dans le discours un solution mathématique rigoureuse.

Les cartes politiques sont comparables aux graphiques

Cet exemple nous aide à comprendre comment mathématiques est fondamental pour formaliser et faire des conjectures concrètes relatives à vie courante. Connaître les mathématiques, en effet, signifie aussi et surtout apprendre à comprendre ce qui peut être résolu et ce qui n’a pas d’explication.

Dans le cas des « cartes 4 couleurs », une branche des mathématiques appelée la théorie des graphesqui étudie précisément moi des graphiques, des objets discrets qui permettent de schématiser des problèmes beaucoup plus complexes. Plus simplement, voici ce que l’on pourrait considérer comme réticulé : lignes Et points Que ils schématisent des concepts.

théorie des graphes du théorème des quatre couleurs
Crédits : Tomwsulcer

Dans ce cas, nous pouvons associer un graphique réalisé ainsi à notre carte géographique : disons un pointer au « centre » de chaque région et connectons-le avec un segment à chaque point correspondant vers les régions voisines. L’objectif est de démontrer qu’il existe une configuration qui utilise seulement quatre couleurs donc, en partant de n’importe quel sommet et en se déplaçant le long du graphique, on ne trouvera pas deux points consécutifs de la même couleur.

Pour les plus passionnés, vous pouvez trouver la démonstration complète dans les sources ci-dessous. Pour les « moins » passionnés, nous vous invitons à essayez avec un stylo et du papier: chaque division de la feuille que vous réaliserez sera colorable avec seulement 4 couleurs.