Coloration d'un graphe




Nombre chromatique    

 

Colorier un graphe G c'est colorier les sommets de telle façon que deux sommets distincts et adjacents aient toujours des couleurs différentes.


Le nombre chromatique χ(G) est le plus petit nombre de couleurs nécessaires pour colorier le graphe.


  On peut constater que:

◊ Si un graphe a n sommets, alors  χ(G) ≤ n.
      
(On peut donner des couleurs différentes aux sommets).

◊ Si un graphe de n sommets est complet K(n), alors χ(G) = n.
      
(Deux sommets distincts devront avoir des couleurs différentes, il faut donc au moins n couleurs).

◊ Si le plus grand degré d'un sommet est d, alors χ(G) ≤ d + 1.
     
(Prendre un sommet de degré d ainsi que les sommets qui lui sont reliés, colorier ces d+1 sommets avec d+1 couleurs différentes.
      Prendre ensuite, l'un après l'autre, les sommets restants ... pour chacun d'eux, l'une des couleurs, au moins, convient).


◊ 
Lorsque le graphe est planaire, alors χ(G) ≤ 4.

◊ Si G d'ordre n admet un sous graphe complet de m sommets, alors m ≤ χG) ≤ n.

.


Algorithme de Welsh-Powel    

Les couleurs sont numérotées 1, 2, 3 ... (Les couleurs sont les naturels non nuls).

1) Dresser une liste des sommets ( dans un ordre décroissant des degrés).
2) Tant que tous les sommets ne sont pas coloriés :
    Choisir le premier sommet non encore colorié de la liste et lui affecter la plus petite couleur possible,
    non déjà affectée à un sommet adjacent).


Remarque : En modifiant l'ordre des sommets de la liste, on peut parfois obtenir un nombre moindre de couleurs.

Exemple n°1:

Sommets i123456
Degrés d(i)554433
Utilisées c(i)123444
Espéré C 665544





Sommets dans l'ordre décroissant des degrés
Sommets dans l'ordre initial
Sommets rangés dans un ordre quelconque
     

Autres exemple:
                      

Où l'algorithme n'est pas optimal (χ(G) = 2)
 
Le cube
Un K7
Une roue à 9 sommets
graphe orienté


Vous pouvez cliquer sur les images ci-dessus pour effectuer les calculs et déterminer leur coloration. Vous pouvez également modifier les données pour les adapter à d'autres exemples et chercher une coloration du graphe correspondant.


La conception de cette page, les scripts Java ainsi que toutes les figures ont été adaptés du site:
http://perso.wanadoo.fr/jean-paul.davalan/graphs/col/index.html
N'hésitez pas à vous y rendre!!!

Retour à l'Index