|
|
|
|
Le graphe obtenu est un graphe non orienté. Le degré de chaque sommet est donné dans le tableau ci-dessous :
D’où une liste ordonnée des sommets : A C B D E G F H
|
En numérotant les couleurs, la mise en oeuvre de l’algorithme de coloriage nous donne :
|
|
A |
C |
B |
D |
E |
G |
F |
H |
Boucle N° 1 |
u |
|
|
|
u |
|
|
|
|
Boucle N° 2 |
|
v |
v |
|
|
|
|
|
|
Boucle N° 3 |
|
|
|
w |
|
w |
w |
|
|
Boucle N° 4 |
|
|
|
|
|
|
|
x |
|
Coloriage |
u |
v |
v |
w |
u |
w |
w |
x |
Le sous-graphe A H C D est complet donc 4 couleurs sont nécessaires, la mise en œuvre de l’algorithme de coloriage précédent montre que 4 couleurs suffisent. Le nombre chromatique du graphe est donc 4.
Constitution des 4 aquariums :
|
Aquarium 1 |
Aquarium 2 |
Aquarium 3 |
Aquarium 4 |
|
A E |
C B |
D G F |
H |
L’algorithme de coloriage de Welch – Powell encore appelé algorithme « glouton » ne conduit pas toujours à un coloriage optimal, c’est à dire utilisant un nombre de couleurs égal au nombre chromatique du graphe….
A titre de contre-exemple, considérons le graphe ci-dessous :
|
|
Dans ce graphe, tous les sommets sont d’ordre 2. Il est clair que le nombre chromatique de ce graphe est 2 : Une couleur ne suffit pas puisque A et E sont adjacents… Mais deux couleurs suffisent… · A B C : couleur 1 · D E F : couleur 2 |
Tous les sommets étant de même ordre, toute liste des sommets sera classée par ordre décroissant…
Mais comme le montrent les deux classements ci-dessous, le choix initial n’est pas neutre et ne conduit pas au même coloriage.
- Pour la liste ordonnée des sommets : A B C D E F l’algorithme de coloriage nous donne :
|
Sommets |
A |
B |
C |
D |
E |
F |
2 couleurs sont nécessaires |
|
Couleurs |
1 |
1 |
1 |
2 |
2 |
2 |
- Mais pour la liste ordonnée: A D E B F C le même algorithme conduit à :
|
Sommets |
A |
D |
E |
B |
F |
C |
3 couleurs sont nécessaires |
|
Couleurs |
1 |
1 |
2 |
2 |
3 |
3 |
|
|
Le graphe ci-contre est isomorphe au graphe initial. On remarquera que pour la liste A D E B F C le premier coloriage conduit à colorier deux sommets dont la distance est égale à 3. Alors que pour la liste A B C D E F le premier coloriage concerne deux sommets dont la distance est 2….
Le problème se retrouve sur le graphe ci-dessous :
|
