DSATUR
implementation by p. Rolland
04/1998

New Methods to color the vertices of a graph

Communication of ACM. April 1979, Vol. 22. Number 4.

Daniel Brelaz

[ Introduction | Algorithmique | implémentation | Exemple d'éxécution ]

Introduction

On considère un graphe G=(V,E) simple connexe et non-orienté. On rappelle que la définition usuelle d'un graphe simple est un graphe sans boucles, ni multi-arcs (resp.multi-arêtes). Pour chaque sommet v de V, on calcule le degré de saturation DSAT(v) de la manière suivante:

Si aucun voisin de v n'est colorié alors

DSAT(v)=degré(v)

sinon

DSAT(v)= le nombre de couleurs différentes utilisées dans le premier voisinage de v

L'algorithme DSATUR est un algorithme de coloration séquentiel, au sens ou il colorie un seul sommet à la fois et tel que:

au départ le graphe n'est pas colorié

on colorie un sommet non-déjà colorié

on stoppe DSATUR quand tous les sommets de G sont coloriés.

Dans un premier temps on voit bien d'une part que la preuve de terminaison est triviale et d'autre part que l'algorithme est séquentiel. Dans le détail l'algorithme est le suivant:

1. Ordonner les sommets par ordre décroissant de degrés.

2. Colorier un sommet de degré maximum avec la couleur 1.

3. Choisir un sommet avec DSAT maximum. Si conflit choisir celui avec dg maximum.

4. Colorier ce sommet par la plus petite couleur possible

5. Si tous les sommets sont coloriés alors stop. Sinon aller en 3.

Exemple (3) d'implémentation en C et php

• Basic structure en C: dsat_simple_c.txt
• Complexe structure en C:dsat.c (dsat.h). Pour un descriptif complet de l'implémentation: structures, entrées/sorties, conventions,...
• Basic structure en php: http://prolland.free.fr/works/research/dsatphp/dsat.html

Détails : Exemple de résolution algorithmique

Dans cette partie on cherchera à exhiber de manière algorithmique les futurs composants (ie procèdures ou fonctions) qui constitueront notre programme. Dans cette perspective, on peut d'abord traduire de manière naïve le procèdè itératif donné plus haut.

fonction DSAT (G) Tant que TousLesSommetsColorie(G) = FAUX Faire v = SommetDeDsatMaxNonColorieEtDegreMax (G) G = ColorierSommetParLaPlusPetiteCouleur (v,G) G = MiseAJourDesDsat (G) Fin TantQue Retourner (G) Fin fonction

A ce stade, clairement on peut simplifier puisque sommet par sommet on colorie le graphe, on a alors:

fonction DSAT (G) Pour i de 1 à n faire v = SommetDeDsatMaxNonColorieEtDegreMax (G) G = ColorierSommetParLaPlusPetiteCouleur (v,G) G = MiseAJourDesDsat (v,G) Fin Pour Retourner (G) Fin fonction

Il reste alors à définir trois fonctions. On les donne :

fonction SommetDeDsatMaxNonColorieEtDegreMax (G) (* recherche du 1 sommet non colorie *) i <- 1 tant que (colorie(i) = vrai) faire i++ fin tant que (* recherche du premier sommet de dsat max *) dsatmax <- dsat(i) k <- i pour i de k+1 à n faire si colorie(j) = faux alors si dsatmax < dsat(j) alors i <- j dsatmax <- dsat(j) fin si fin si fin pour (* ici retourner(i) réalise uniquement le premier critère *) dgmax <- degré(i) k <- i (* ici on realise le 2nd critere ie le degre *) pour j de k+1 à n faire si colorie(j) = faux alors si ((dsat(j)=dsatmax) et (dgmax<degre(j))) alors i <- j dgmax <- degre(j) fin si fin si fin pour retourner (i) fin fonction

fonction ColorierSommetParLaPlusPetiteCouleur(v,G) initialisationDuVecteurColorAZero Pour i de 1 à degré(v) faire color[couleurDuSommet(iemeVoisinDuSommet(i,v))] <- 1 fin pour pour i de 1 à degré(v)+1 faire si color[i] = 0 alors retourner(i) fin si fin pour Retourner (G) fin fonction

Pour la dernière fonction il y a, de notre point de vue, plusieurs remarques à formuler. Soit v le sommet dernièrement colorié; soit c sa couleur. La mise à jour des dsat ne s'opère que sur :

1. les sommets non coloriés

2. les voisins v_i (i de 1 à degré(v)) du sommet dernièrement coloriés.

3. Pour ces derniers il y a trois cas. Soit v_i un voisin de v.

3a. v_i ne possèdait aucun voisin colorié avant la coloration de v, auquel cas leur dsat(v_i)=degre(v_i). On affecte alors dsat(v_i)=1.

3b. Sinon ( v_i possède des voisins coloriés)

3bi. v_i ne possède (mise à part v) aucun voisin de couleur c. On affecte dsat(v_i)=dsat(v_i)+1

3bii. v_i possède (mise à part v) un ou plusieurs voisins de couleur c. On ne modifie pas dsat(v_i)

fonction MiseAJourDesDsat (v,G) Pour i de 1 à degré(v) faire si (colorie(iemeVoisinDuSommet(i,v)) = faux) alors si (dsat((iemeVoisinDuSommet(i,v))=degre((iemeVoisinDuSommet(i,v))) alors dsat((iemeVoisinDuSommet(i,v))=1 sinon G <- IncrementationOuPasDeDsat(iemeVoisinDuSommet(i,v),couleurDuSommet(v),G) fin si fin pour Retourner (G) fin fonction

fonction IncrementationOuPasDeDsat ( w, colorDeV, G) Pour i de 1 à degré(w) faire si ((couleurDuSommet(iemeVoisinDuSommet(i,w)) = colorDeV) et (iemeVoisinDuSommet(i,w) != w )) alors Retourner (G) fin si fin pour dsat(w) <- dsat(w) + 1 Retourner (G) fin fonction

Philippe Rolland - 04/98