DSATD. Brélaz, New Methods to color the vertices of a graph, Communication of ACM. April 1979, Vol. 22. Number 4 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 « ». C'est un exemple de coloration gloutonne.
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 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 Boucle principale 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 DSAT(v)= nombre de couleurs différentes dans les sommets adjacents à v
Qualité de l'heuristique
Cet algorithme étant classé parmi les heuristiques, il ne fournit pas forcément 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.
Cet algorithme est exact pour les graphes bipartis, les graphes-cycle, les graphes monocycliques et bicycliques, les arbres, les colliers, et les graphes-cactus Adrian Kosowski, Krzysztof Manuszewski, Classical Coloring of Graphs, Chapter 1.
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êtesR. Janczewski, M. Kubale, K. Manuszewski, K. Piwakowski, The smallest hard-to-color graph for algorithm DSATUR, Discrete Mathematics 236 (2001), 151–165.
Références
Liens externes Implémentation en Python : http://prolland.free.fr/DSATUR_v1.py.txt Démonstration et Implémentation en php : http://prolland.free.fr/works/research/dsatphp/dsat.html Implémentation en C : http://prolland.free.fr/Cours/Cycle2/Maitrise/GraphsTheory/TP/PrgGraphDsat/dsat_simple_c.txt
Catégorie:Algorithme d'optimisation Catégorie:Algorithme de la théorie des graphes