COLORATION DE CARTES GEOGRAPHIQUES : THEOREME DES 4 COULEURS

Choix de l'algorithme

Algorithme purement aléatoire

Algorithme aléatoire respectant la règle de coloration

Algorithme glouton

Algorithme de Welsh Powell

Algorithme DSATUR

--Choisir une carte-- Affichage des étapes de coloration

Algorithme purement aléatoire :

Une couleur aléatoire est choisie pour chaque zone sans respecter la règle de coloration d'un graphe.

Algorithme aléatoire respectant la règle de coloration :

Des couleurs sont choisies aléatoirement en respectant la règle de coloration d'un graphe.

Algorithme glouton :

Des couleurs sont choisies aléatoirement en respectant la règle de coloration d'un graphe.

Algorithme :

On assimile les couleurs à des entiers naturels.

1. On parcourt tous les sommets s du graphe.
2. On regarde l'ensemble des couleurs déjà attribuées aux voisins de s.
3. On en déduit le plus petit entier naturel qui n'appartient pas à cet ensemble.
4. On attribue cette couleur au sommet s.

Algorithme de Welsh Powell :

Principe :

L’algorithme de Welsh & Powell consiste ainsi à colorer séquentiellement le graphe en visitant les sommets par ordre de degré décroissant.

L’idée est que les sommets ayant beaucoup de voisins seront plus difficiles à colorer, et donc il faut les colorer en premier.

Algorithme :

1. Repérer le degré de chaque sommet.
2. Ranger les sommets par ordre de degrés décroissants (dans certains cas plusieurs possibilités).
3. Attribuer au premier sommet (A) de la liste une couleur.
4. Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A).
5. Suivre (si possible) la liste jusqu’au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
6. Continuer jusqu’à ce que la liste soit finie.
7. Prendre une deuxième couleur pour le premier sommet (D) non encore coloré de la liste.
8. Répéter les opérations 4 à 7.
9. Continuer jusqu’à avoir coloré tous les sommets.

Algorithme DSATUR :

Principe :

Pour chaque sommet v du graphe G, on calcule le degré de saturation DSAT(v) et l'on utilisera ce nombre ainsi que le degré des sommets pour déterminer l'ordre de coloration du graphe. L'algorithme s'arrête lorsque tous les sommets de G sont colorés.

Algorithme :

Les différentes étapes sont :

1. Ordonner les sommets par ordre décroissant de degrés.
2. Colorer un sommet de degré maximum avec la couleur 1.
3. Choisir un sommet avec DSAT maximum. En cas d'égalité, choisir un sommet de degré maximal.
4. Colorer ce sommet avec la plus petite couleur possible.
5. Si tous les sommets sont colorés alors stop. Sinon aller en 3.

Calcul de DSAT :

DSAT(v)= nombre de couleurs différentes dans les sommets adjacents à v