Dsatur

DSAT^[1] ou DSATUR est un algorithme de coloration de graphes créé par Daniel Brélaz en 1979 à l'EPFL.

Pour une classification: c'est un algorithme de coloration séquentiel par heuristique; DSAT pour Degree SATuration.

On considère un graphe G=(V,E) simple connexe et non-orienté. On rappelle que la définition usuelle d'un graphe simple est un graphe sans boucles, ni multi-arcs (resp.multi-arêtes). Pour chaque sommet v de V, on calcule le degré de saturation DSAT(v) de la manière suivante:

   Si aucun voisin de v n'est colorié alors
       DSAT(v)=degré(v) 
   sinon
       DSAT(v)= le nombre de couleurs différentes utilisées dans le premier voisinage de v 

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

   au départ, aucun sommet du graphe n'est colorié 
   on colorie un sommet non colorié 
   on stoppe DSATUR quand tous les sommets de G sont coloriés. 

Dans un premier temps on voit bien d'une part que la preuve de terminaison est triviale et d'autre part que l'algorithme est séquentiel. Le détail de l'algorithme est le suivant:

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

Liens extérieurs

• (fr) Démonstration et Implémentation en php : http://prolland.free.fr/works/research/dsatphp/dsat.html

• (fr) Implémentation en C : http://prolland.free.fr/Cours/Cycle2/Maitrise/GraphsTheory/TP/PrgGraphDsat/dsat_simple_c.txt

Références