Partie III : La coloration par Welsh-Powel

1. 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. La complexité de l’algorithme devient O(n ln n + m) en utilisant un tri par comparaison, mais reste O(n + m) avec un tri par dénombrement. Cependant on peut parfois aboutir aux pires colorations possibles ( n 2 au lieu de 2). L’heuristique DSATUR propose une amélioration du principe de l’algorithme de Welsh & Powell afin d’éviter ce problème.

Il y a une certaine procédure à respecter afin de mettre en oeuvre cet algorithme.

Procédure :

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

2. Algorithme

On note L la liste des sommets si classes suivant l’ordre décroissant de leur
degre : d(s1) d(s2) d(s3) ::: d(sn).
Initialisation :
L : liste des sommets dans l’ordre décroissant du degré
couleur = 0
Tant que L ≠ ∅ ; faire
couleur=couleur+1
couleur(s) = couleur
Pour tout t dans L faire
Si t ∉ Γs
couleur(t)=couleur
Γs = Γs ∪ Γt
Fin si
Fin faire
Retirer les sommets colores de L
Fin faire

3. Exemples

Prenons ces 5 graphes :

GraphesTest

Graphe 1 :

Sommet	Degré	Successeurs
1	0	X

Couleur/Sommet	1
C1 : rouge	C1

Graphe 2 :

Sommet	Degré	Successeurs
1	1	2
2	1	1

Couleur/Sommet	1	2
C1 : rouge	C1
C2 : bleu	X	C2

Graphe 3 :

Sommet	Degré	Successeurs
1	2	{2,3}
2	2	{1,3}
3	2	{1,2}

Couleur/Sommet	3	2	1
C1 : vert	C1
C2 : bleu	X	C2
C3 : rouge	X	X	C3

Graphe 4 :

Sommet	Degré	Successeurs
1	2	{2,4}
2	2	{1,3}
3	2	{2,4}
4	2	{1,3}

Couleur/Sommet	4	3	2	1
C1 : bleu	C1		C1
C2 : rouge	X	C2	X	C2

Graphe 5 :

Sommet	Degré	Successeurs
1	2	{2,5}
2	2	{1,3}
3	2	{2,4}
4	2	{3,5}
5	2	{1,4}

Couleur/Sommet	5	4	3	2	1
C1 : bleu	C1		C1
C2 rouge	X	C2	X	C2
C3 : Vert	X	X	X	X	C3

4. Contre-exemple

Afin de tester l’efficacité de l’algorithme de Welsh Powell, nous allons mettre en place un contre exemple.

Soit le graphe :

ContreExemple(2).png

Nous allons dérouler l’algorithme de Welsh Powell normalement :

Sommet	Degré	Successeurs
1	1	2
2	3	{1,3,8}
3	2	{2,4}
4	2	{3,5}
5	3	{4,6,7}
6	1	5
7	2	{5,8}
8	2	{2,7}

Couleur/sommet	5	2	8	7	4	3	6	1
C1 (rouge)	C1	C1
C2 (vert)	x	x	C2		C2		C2	C2
C3 (bleu)	x	x	x	C3	x	C3	x	x

Avec l’application de l’algorithme, on obtient alors cette coloration :

ContreExemple color.png

Hors, elle n’est pas optimale.
En effet, seul deux couleurs suffisent pour colorier ce graphe, tel que :

ContreExemple color opti.png

5. Limites

L’algorithme de Welsh Powell permet d’avoir une coloration des sommets cohérente.

Néanmoins, le contre-exemple montre bien que la coloration proposée n’est pas toujours optimale, car dans certains cas, un nombre plus restreint de couleurs peuvent être utilisées (voir ci-dessus).

Il est donc parfois plus simple d’étudier le graphe sans ce dernier et de trouver soi-même une coloration optimale, et ensuite vérifier sa coloration avec l’algorithme pour voir si elle est optimale ou non (à condition que le graphe soit facile de compréhension comme l’est notre contre-exemple).

Compte-rendu 30|11|2015

Finalisation du programme Java
Début de la rédaction du mémoire sous format Word
Début de la rédaction de la partie III

Compte-rendu 27|11|2015

Programme Java fonctionnel avec des exemples simples et début des tests sur la carte de la France.
Partie II terminée (reste à ajouter les exemples DSATUR et RLF)
Début de la partie III
Ajout de nouvelles sources

Travail du 24|11|2015

Recherches concernant les algorithme DSATUR et RLF

Ajout des sources utilisées jusqu’à présent (ICI et dans l’onglet correspondant)

Programme Java d’implémentation de Welsh-Powel

Objectifs pour la prochaine séance:

Terminer la deuxième partie
Continuer le programme Java et l’optimiser
Commencer la partie III
Continuer à ajouter les sources

Travail du 22| 11 | 2015

Réalisation du début de programme sous Java et finalisation des recherches sur le fonctionnement de l’algorithme (uniquement dans le cadre de la programmation).

Définition des différentes classes Java et de leurs contenues, première approche et essaie sur les structures.

Partie I : Définition des termes

1. Notion de graphe et sous-graphe

Définition:

Un graphe G est un schéma contenant des points nommés sommets, reliés ou non par des segments appelés arêtes.
Un graphe est dit simple s’il ne comporte aucune boucle et que deux arêtes ne relient jamais la même paire de sommets.
Un graphe est dit complet si tous les sommets sont adjacents les uns avec les autres.

Un sous graphe d’un graphe G est un graphe constitué de certains sommets de G et de toutes les arêtes qui les relient.

Il est dit stable lorsqu’il ne comporte aucune arête, autrement dit si deux sommets quelconques ne sont pas adjacents.

Exemple:

Soit le graphe G :

Si G est le graphe complet d’ordre 4, alors le graphe G’ est un sous-graphe de G mais le graphe G’’ n’en est pas un:

2. Sommets, arêtes, ordre et degré d’un graphe

Définitions :

Un sommet d’un graphe correspond à un point du graphe composé ou non par des arêtes.
Les arêtes représentent les liaisons entre un sommet et un autre ou un sommet sur lui-même.

L’ordre d’un graphe est le nombre de sommets de ce graphe.
Dans un graphe, le degré de chaque sommet est le nombre d’arêtes dont il est l’une des extrémités.

Propriété :

La somme des degrés de tous les sommets d’un graphe est égal au double du nombre total d’arêtes de ce graphe

Exemple :

Soit le graphe G :

graphdegsomm

Les sommets sont A, B et C
L’ordre du graphe est 3.
Le degré de A est d(A)=2
d(A)+d(B)+d(C)=2+2+2=6
La somme des degré de tous les sommets est bien égale au double du nombre total d’arêtes du graphe

3. Nombre chromatique

Colorier un graphe c’est associer à tout sommet une couleur telle que deux sommets adjacents n’aient pas la même couleur.

Le plus petit nombre de couleurs nécessaire pour colorier un graphe s’appelle le nombre chromatique du graphe.

Le nombre chromatique, noté χ(G), d’un graphe est inférieur ou égal à dmax+1 où dmax est le plus grand degré des sommets.

Nous pouvons déterminer un encadrement de ce nombre, avant de le trouver de manière exacte avec l’algorithme de Welsh-Powel.

Exemple :

Soit le graphe G :

graphecolo

Prenons le cas de B-C-G

Il faut au minimum 3 couleurs car B-C-G représente un graphe complet d’ordre 3: Les 3 sommets ne doivent donc pas avoir la même couleur pour respecter la règle.

Nous savons donc que χ(G) ≥ 3

Le sommet de plus haut degré est C, de degré 5. Il faut donc au plus 6 couleurs.

Donc, χ(G) ≤ 6

Nous avons un encadrement : 3 ≤ χ(G) ≤ 6

Travail du 20|11|2015

Ajustement du plan de la première partie concernant les définitions:

Partie I : Définition des termes

Notion de graphe et sous-graphes
Sommets, arêtes, ordre et degré d’un graphe
Nombre chromatique

Rédaction de la première partie (voir onglet correspondant)

Réorganisation de la deuxième partie, modification de l’onglet et ajout des sources pour la méthode DSATUR pour la prochaine séance

Objectifs pour la prochaine séance:

Ajouter les sources pour la première partie
Terminer la deuxième partie
Continuer les recherches sur l’application en Java
Commencer la troisième partie
Revoir la présentation du sujet

Partie II : La coloration

1. L’histoire de la coloration des graphes

Les premiers résultats de coloration de graphes concernent presque exclusivement la coloration des cartes. En cherchant à mettre en couleurs une carte des comtés d’Angleterre, Francis Guthrie (mathématicien et botaniste sud-africain 1831 − 1899) postule en 1852 la conjecture des quatre couleurs : il remarqua en effet qu’il n’y avait besoin que de quatre couleurs pour que deux comtés ayant une frontière commune soient de couleurs différentes.

En 1879, Alfred Kempe (mathématicien anglais 1849 − 1922) publia ce qu’il prétendit en être une démonstration et pendant une décennie, on crut que le problème des quatre couleurs était résolu.

En 1890, Percy John Heawood (mathématicien anglais 1861 − 1955) fit remarquer que la démonstration de Kempe était fausse. Il montra quant à lui le théorème des cinq couleurs en reprenant des idées de Kempe.

De nombreux travaux ont été publiés lors du siècle suivant pour réduire le nombre de couleurs à quatre, jusqu’à la démonstration finale de Kenneth Appel (mathématicien américain né en 1932) et Wolfgang Haken (mathématicien allemand né en 1928). Il s’agit aussi de la première preuve majeure utilisant massivement l’ordinateur.

Outre le problème de cartes, la coloration des graphes intervient également pour les problème d’optimisation avec contraintes (planning, incompatibilités), dans les réseaux, la cryptographie. . . Aucune formule miracle permet de déterminer le nombre chromatique d’un graphe quelconque.

La plupart du temps, il faut se contenter d’un encadrement, autrement dit d’un minorant et d’un majorant du nombre chromatique.

Il existe plusieurs algorithmes de coloration, que nous allons voir plus en détail.

2. Algorithme glouton

Les algorithmes glouton sont couramment utilisés dans la résolution de problèmes.

Le principe de tels algorithmes consiste à choisir des solutions locales optimales d’un problème dans le but d’obtenir une solution optimale globale au problème.

Dans le cas du coloriage de graphe, cela va consister à colorier les sommets un par un avec la plus petite couleur possible ; l’ensemble des couleurs possibles étant donné par les couleurs de ses voisins. L’ordre dans lequel les sommets sont traités définit les différentes variantes de d’algorithme. Une méthode est de colorer les sommets par ordre de difficultés décroissantes.

Exemple :

Entrée :
liste ordonnée V des n sommets d’un graphe G
liste ordonnée C de couleurs
Pour i variant de 1 à n
v = V[i]
couleur = la première couleur de C non utilisée par les voisins de v
colorier(v, couleur)
Fin pour

L’algorithme glouton le plus utilisé est l’algorithme de Welsh-Powel que nous allons étudier plus en profondeur dans une paragraphe dédié.

Néanmoins, il existe d’autres algorithmes reposant sur le principe glouton, moins connu, comme DSATUR et RLF, ayant des limites.

3. Algorithme DSATUR

DSATUR est un algorithme de coloration de graphes créé par Daniel Brélaz en 1979 à l’EPFL (École polytechnique fédérale de Lausanne).

Il s’agit d’un algorithme de coloration séquentiel par heuristique. DSAT est l’abréviation de dégré saturation.

Propriété :

On considère un graphe G=(V,E) simple connexe et non-orienté. Pour chaque sommet v de V, on calcule le degré de saturation DSAT(v) de la manière suivante:

Si aucun voisin de x est colorié, alors DSAT(x) = le degré de x
Sinon, DSAT(x) = le nombre de couleurs différentes utilisées dans le voisinage de x

L’algorithme DSATUR est un algorithme de coloration séquentiel, au sens ou il colorie un seul sommet à la fois et tel que:

Au départ le graphe n’est pas colorié
On colorie un sommet non-déjà colorié
On stoppe DSATUR quand tous les sommets de G sont coloriés.

Méthode d’application de l’algorithme :

Ordonner les sommets par ordre décroissant de degré.
Colorer un sommet de degré maximum avec la couleur 1.
Choisir un sommet non coloré avec DSAT maximum. Si conflit choisir celui avec degré maximum.
Colorer ce sommet par la plus petite couleur possible
Si tous les sommets sont colorés alors stop. Sinon aller en 3.

Exemple :

Exemple :

Soit les couleurs hiérarchisées :

hierarchie couleursdartur

On prend le sommet de plus haut degré, soit le sommet 1.

On lui attribue la couleur minimale, soit C1 :

dsaturgrapheetapeuno

Puis, on regarde plus un voisin du sommet 1 étant de plus haut degré: Nous allons prendre le sommet 6.

Il faut lui attribuer une couleur minimale, mais différente de la couleur du sommet : On prend C2 :

dsaturgrapheetapedos

On fait la même chose pour le voisin du sommet étant de plus haut degré : le sommet 5. On lui attribue une couleur minimale différente de celle de ses voisins : la couleur C3 :

dsaturgrapheetapetres$

On réédite l’opération pour tous les autres sommets, puis on obtient :

4. Algorithme RLF

L’algorithme RLF construit les classes de couleur les unes après les autres. Pour chaque classe, le premier sommet à en faire partie est choisi au hasard parmi ceux ayant un nombre maximum de sommets adjacents non colorées. La classe est alors complétée de la manière suivante. Soit W ⊆ U l’ensemble des sommets non colorées qui ne peuvent plus faire partie de la classe en construction (car ils sont adjacents à au moins un sommet de cette classe).

Le prochain sommet introduit dans la classe est un sommet faisant partie de U mais pas de W , et ayant un nombre maximum de sommets adjacents dans W . Lorsque U =W , on passe a la classe de couleur suivante.

Cet Algorithme est basé sur la méthode DSATUR

Les différentes étapes de l’algorithme :

Choisir un sommet x de degré maximum;
Choisir un voisin de ce sommet y tel que vc(x,y) soit maximum;
Contracter y en x;
Répéter 2 et 3 jusqu’à ce que x soit voisin à tous les autres sommet;
Enlever le sommet x et reprendre à l’étape 1;

Exemple :

Tout d’abord, il faut repérer le sommet de plus au degré : c’est le sommet 1.

Nous allons donc lui attribuer une couleur, et « éliminer » tous ses sommets adjacents. Ceux qui ne le sont pas prendront la couleur du sommet 1 :

dsaturgrapheetape1

Puis, nous allons étudier un sous-graphe où les deux premiers sommets coloriés sont exclus, et choisir un nouveau sommet (le sommet 5) et lui attribuer une autre couleur :

dsaturgrapheetape25