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

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 :

  1. Ordonner les sommets par ordre décroissant de degrés.
  2. Colorer un sommet de degré maximum avec la couleur 1.
  3. Choisir un sommet avec DSAT maximum. En cas d'égalité, choisir un sommet de degré maximal.
  4. Colorer ce sommet avec la plus petite couleur possible.
  5. 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
Le plus petit graphe 3-colorable qui trompe l’algorithme DSATUR qui trouve une 4-coloration.

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
  1. D. Brélaz, New Methods to color the vertices of a graph, Communication of ACM. April 1979, Vol. 22. Number 4
  2. Adrian Kosowski, Krzysztof Manuszewski, Classical Coloring of Graphs, Chapter 1
  3. 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
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.