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
[modifier | modifier le code]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 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
[modifier | modifier le code]Boucle principale
[modifier | modifier le code]Les 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
[modifier | modifier le code]DSAT(v)= nombre de couleurs différentes dans les sommets adjacents à v
Qualité de l'heuristique
[modifier | modifier le code]
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 | modifier le code]- 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 | modifier le code]- (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
