La coloration de graphes trouve l’une de ses applications les plus célèbres et les plus élégantes dans le domaine de la cartographie. Cette section explore comment les concepts théoriques développés précédemment s’appliquent concrètement à la représentation cartographique, depuis les propriétés mathématiques fondamentales jusqu’aux applications modernes dans les systèmes d’information géographique.
Contexte historique
Le théorème des quatre couleurs que nous allons démontrer, constitue le pilier théorique des applications cartographiques moderne de la coloration de graphes. Énoncé pour la première fois par Francis Guthrie en 1852, ce théorème stipule qu’il est possible de colorier n’importe quelle carte géographique plane avec seulement quatre couleurs, de sorte que deux régions adjacentes ne portent jamais la même couleur.
L’histoire de ce théorème est remarquable par sa simplicité apparente contrastant avec la complexité de sa démonstration. Francis Guthrie l’observa en coloriant une carte des comtés d’Angleterre, remarquant qu’il ne lui fallait que quatre couleurs. La conjecture fut transmise à Auguste de Morgan, puis à William Rowan Hamilton, mais resta non démontrée pendant plus d’un siècle.
Le concept de colorisation deviendra plus tard un élément central de la sémiologie graphique, discipline qui occupe aujourd’hui une place essentielle dans les applications cartographiques et la représentation de l’information. En effet, la sélection et l’utilisation des couleurs ne répondent pas uniquement à des contraintes mathématiques de distinction, mais aussi à des principes perceptifs et cognitifs visant à rendre une carte ou une information lisible et interprétable par l’utilisateur. Selon les règles de la sémiologie établies par Jacques Bertin, chaque couleur doit permettre d’identifier distinctement chaque région voisine, tout en maintenant une harmonie visuelle dans l’ensemble de l’infographie.
La première démonstration complète fut proposée par Kenneth Appel et Wolfgang Haken en 1976. Cette preuve, “nécessitait” l’assistance d’un ordinateur pour vérifier plus de 1 000 configurations particulières.
Théorème : tout graphe planaire possède un nombre chromatique $\phi(G) \le 4$. Cette formulation établit un lien direct entre la topologie des cartes géographiques et les propriétés des graphes planaires, confirmé par l’encadrement théorique $n(G)/\alpha(G) \leq \varphi(G) \leq \Delta + 1$ se resserre à $\phi(G) \le 4$ pour les graphes planaires.
Pour appliquer la théorie des graphes à une carte géographique, la transformation s’effectue selon le principe suivant :
- Chaque région (pays, département, commune) devient un sommet du graphe
- Deux sommets sont reliés par une arête si et seulement si les régions correspondantes partagent une frontière commune (non réduite à un point)
- Le graphe obtenu est planaire par construction
Cette modélisation permet de ramener le problème cartographique à un problème de coloration de graphe planaire, bénéficiant ainsi de tous les résultats théoriques associés.
Fondements mathématiques
Ensembles stables
Définition 1 : Soit $G=(X,U)$ un graphe non-orienté. Un sous-ensemble $S \in X$ est un ensemble stable s’il ne comprend que deux sommets non-adjacents deux-à-deux : $\forall x_i, x_j \in S \implies (x_i, x_j) \notin U$. Comme tout sous-ensemble stable est aussi un ensemble stable, il convient de chercher le cardinal maximum d’un ensemble stable. Ce nombre est noté $\alpha(G)$ et est appelé le nombre de stabilité.
Cette notion d’ensemble stable revêt une importance particulière en cartographie : dans le contexte d’une carte géographique, un ensemble stable correspond à un groupe de régions qui ne partagent aucune frontière commune entre elles. Ces régions peuvent donc recevoir la même couleur sans violer la règle fondamentale de coloration cartographique.
Définition 2 : Colorier un graphe, c’est colorier les sommets de telle sorte que deux sommets distincts et adjacents aient toujours des couleurs différentes. Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorier le graphe. Le nombre chromatique $\phi(G)$ est défini comme le nombre minimal de couleurs nécessaires à la coloration de $G$. Un graphe $G$ tel que $\phi(G) \leq k$ qui est coloriable en $k$ couleurs est dit $k$-chromatique.
Encadrement du nombre chromatique
Les propriétés mathématiques permettent d’établir des bornes précises pour le nombre chromatique, particulièrement utiles dans l’évaluation préalable du nombre de couleurs nécessaires pour une carte donnée.
Borne inférieure du nombre chromatique : Puisque $\alpha(G)$ est le nombre maximum des sommets des ensembles stables déduits de $G$, on a $\alpha(G) \times \phi(G) \geq n(G) \implies \phi(G) \geq \frac{n(G)}{\alpha(G)}.$ Cette relation établit une contrainte fondamentale : plus les régions sont interconnectées (petit $\alpha(G)$), plus le nombre de couleurs nécessaires sera élevé.
Borne supérieure du nombre chromatique : Une borne supérieure est donnée par $deg+1$, avec $deg$ le plus grand degré d’un sommet. En cartographie, cela correspond au nombre maximum de frontières qu’une région peut partager avec ses voisines, plus une unité.
Encadrement du nombre chromatique : En utilisant les deux notions précédentes, le nombre chromatique peut être borné par : $\frac{n(G)}{\alpha(G)} \leq \phi(G) \leq deg + 1.$
Cette formulation permet aux cartographes d’estimer rapidement les ressources nécessaires avant d’entreprendre la coloration d’une carte complexe.
Coloration cartographique
L’algorithme fondamental présenté dans la base théorique s’applique directement à la coloration cartographique :
- Tri préalable : On range les sommets (régions) dans un tableau en ordre de degré décroissant.
- Attribution couleur $C_1$ : On attribue la couleur $C_1$ à $x_1$ et au premier sommet de la liste qui n’est pas adjacent à $x_1$, et ainsi de suite avec les sommets de la liste qui ne sont pas adjacents aux sommets déjà coloriés.
- Attribution couleur $C_2$ : On attribue la couleur $C_2$ au premier sommet non colorié ainsi qu’aux sommets suivants qui ne sont pas adjacents aux sommets coloriés par la couleur $C_2$.
- Itération : On répète ce processus jusqu’à épuisement des sommets de la liste.
Exemple détaillé
Considérons l’exemple cartographique avec $n(G) = 7$ régions. L’analyse des ensembles stables révèle :
$S_1 = {x_1, x_6}$ ;
$S_2 = {x_2, x_5}$ ;
$S_3 = {x_3, x_7}$ ;
$S_4 = {x_4}$, donnant $\alpha(G) = 2$.
L’application des formules d’encadrement fournit $\phi(G) \geq \frac{7}{2} \geq 3$. Le degré maximum étant 4, nous obtenons l’encadrement chromatique $\frac{7}{2} \leq 3 \leq 4+1$, soit $3 \leq \phi(G) \leq 5$.
L’algorithme de coloration produit le tableau suivant :
| Sommet | $x_7$ | $x_5$ | $x_4$ | $x_2$ | $x_3$ | $x_1$ | $x_6$ |
|---|---|---|---|---|---|---|---|
| deg | 4 | 4 | 3 | 3 | 3 | 3 | 3 |
| couleur | $C_1$ | $C_3$ | $C_3$ | $C_2$ | $C_1$ | $C_4$ | $C_4$ |
Cette coloration utilise 4 couleurs, respectant la borne supérieure théorique tout en demeurant dans l’encadrement prévu.
Applications pratiques modernes
Systèmes d’Information Géographique
Les Systèmes d’Information Géographique modernes intègrent ces algorithmes mathématiques pour automatiser la coloration cartographique. L’implémentation respecte les contraintes théoriques :
- Vérification des ensembles stables : Le système identifie automatiquement les groupes de régions non-adjacentes pouvant partager la même couleur.
- Calcul du nombre chromatique : L’estimation préalable par les bornes mathématiques optimise l’allocation des ressources de calcul.
- Application de l’algorithme : Le tri par degré décroissant et l’attribution séquentielle des couleurs suivent la procédure théorique.
Optimisation et performances
L’analyse mathématique préalable permet d’optimiser significativement les performances :
Estimation du nombre de couleurs : L’encadrement $\frac{n(G)}{\alpha(G)} \leq \phi(G) \leq deg+1$ fournit une estimation rapide avant le calcul effectif, permettant d’allouer les ressources appropriées.
Validation de l’optimalité : La comparaison entre le résultat obtenu et les bornes théoriques permet de valider la qualité de la coloration et d’identifier les cas nécessitant des algorithmes plus sophistiqués.
Défis cartographiques spécifiques
L’application des propriétés mathématiques révèle des défis particuliers en cartographie :
Territoires à forte connectivité : Les régions urbaines denses présentent souvent des degrés élevés, augmentant la borne supérieure et complexifiant la coloration.
Optimisation du nombre de stabilité : L’identification d’ensembles stables maximaux permet de minimiser le nombre de couleurs nécessaires, particulièrement crucial pour les cartes à impression économique.