DSATUR
# DSATUR

DSAT 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 :

* 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.

## 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.

Cet algorithme est exact pour les graphes bipartis, les graphes-cycle, les graphes monocycliques et bicycliques, les arbres, les colliers, et les graphes-cactus.

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.

