Algorithme de coloration de graphe

- Principe de l'algorithme:

     Tout comme l’algorithme de Welsh-Powell, l’algorithme Dsatur utilise un tri des sommets par ordre de degrés décroissants. Son fonctionnement est assez similaire à l’algorithme glouton. Une fois le tri des sommets effectué, on colorie le sommet de degré maximum avec la couleur 1. Ensuite, le prochain sommet à traiter est le sommet avec le plus haut degré de saturation (DSAT, nombre de couleurs différentes utilisées pour colorier ses voisins). Si plusieurs sommets ont le même degré de saturation, celui choisi est celui avec le plus grand nombre de degrés. On associe à ce sommet le plus petit entier possible, et on le colorie en la couleur associée. On répète ce procédé jusqu’à ce que tous les sommets soient coloriés.

- Analyse de l'algorithme:

     L’algorithme Dsatur, comme nous l’avons vu précédemment, utilise également un tri des sommets préalable. De la même manière que pour l’algorithme de Welsh-Powell, cette étape peut donc demander du temps. Ensuite, de même que pour l’algorithme glouton, l’algorithme Dsatur est assez simple à exécuter. Concernant, le résultat obtenu, l’algorithme fournit un résultat optimal dans 90% des cas, mais il est possible d’obtenir un mauvais résultat pour certains graphes.