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 l'anglais « degree saturation ». C'est un exemple de coloration gloutonne.
Principe
modifierOn 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 coloration 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 colore un seul sommet non déjà coloré à la fois et tel qu'au départ le graphe n'est pas coloré.
Déroulement
modifierBoucle principale
modifierLes différentes étapes sont :
- Ordonner les sommets par ordre décroissant de degrés.
- Colorer un sommet de degré maximum avec la couleur 1.
- Choisir un sommet avec DSAT maximum. En cas d'égalité, choisir un sommet de degré maximal.
- Colorer ce sommet avec la plus petite couleur possible.
- Si tous les sommets sont colorés alors stop. Sinon aller en 3.
Calcul de DSAT
modifierDSAT(v)= nombre de couleurs différentes dans les sommets adjacents à v
Qualité de l'heuristique
modifier
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].
Cet algorithme est exact pour les graphes bipartis, les graphes-cycle, les graphes monocycliques et bicycliques, les arbres, les colliers, et les graphes-cactus[2].
Le plus petit graphe pour lequel DSATUR ne fournit pas la solution exacte au problème, quel que soit l'ordre de parcours des sommets en cas d'égalité, possède 8 sommets et 12 arêtes[3].
Références
modifier- D. Brélaz, New Methods to color the vertices of a graph, Communication of ACM. April 1979, Vol. 22. Number 4
- Adrian Kosowski, Krzysztof Manuszewski, Classical Coloring of Graphs, Chapter 1
- R. Janczewski, M. Kubale, K. Manuszewski, K. Piwakowski, The smallest hard-to-color graph for algorithm DSATUR, Discrete Mathematics 236 (2001), 151–165
Liens externes
modifier- (fr) Implémentation en Python [2022] : http://prolland.free.fr/DSATUR_v1.py.txt
- (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
