- DSATUR
-
DSAT[1] ou DSATUR est un algorithme de coloration de graphes créé par Daniel Brélaz en 1979 à l'EPFL. Il s'agit d'un algorithme de coloration séquentiel par heuristique. DSAT est l'abréviation de Degree SATuration.
Sommaire
Principe
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) et l'on utilisera ce nombre ainsi que le degré des sommets pour déterminer l'ordre de coloriage du graphe. L'algorithme s'arrête lorsque tous les sommets de G sont colorés.
L'algorithme DSATUR est un algorithme de coloration séquentiel, au sens où il colorie un seul sommet non déjà coloré à la fois et tel qu'au départ le graphe n'est pas coloré.
Déroulement
Boucle principale
Les différentes étapes sont :
- Ordonner les sommets par ordre décroissant de degrés.
- Colorier un sommet de degré maximum avec la couleur 1.
- Choisir un sommet avec DSAT maximum. En cas de conflit, choisir celui de degré maximum.
- Colorier ce sommet avec la plus petite couleur possible
- Si tous les sommets sont coloriés alors stop. Sinon aller en 3.
Calcul de DSAT
Si aucun voisin de v n'est coloré alors DSAT(v)=degré(v) sinon DSAT(v)= le nombre de couleurs différentes utilisées dans le premier voisinage de v
Qualité de l'heuristique
Cet algorithme étant classé parmi les heuristiques il ne fournit pas forcement une solution optimale. DSATUR produit donc en temps polynomial une solution réalisable. Son auteur a montré qu'il était capable de fournir en un temps court (relativement aux autres heuristiques et aux méthodes exactes) une coloration optimale dans plus de 90% des cas[1].
Le plus petit graphe qui prend DSATUR en défaut a avoir été exhibé possède 8 sommets et 12 arrêtes[2], il s'agit du plus petit possible pour cet algorithme.
Références
Liens externes
- (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
Catégories :- Algorithme d'optimisation
- Algorithme de la théorie des graphes
Wikimedia Foundation. 2010.