DSATUR

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 Degree SATuration.

Sommaire

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 coloriage 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 colorie 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. Colorier un sommet de degré maximum avec la couleur 1.
  3. Choisir un sommet avec DSAT maximum. En cas de conflit, choisir celui de degré maximum.
  4. Colorier ce sommet avec la plus petite couleur possible
  5. Si tous les sommets sont coloriés alors stop. Sinon aller en 3.

Calcul de DSAT

   Si aucun voisin de v n'est coloré alors
       DSAT(v)=degré(v) 
   sinon
       DSAT(v)= le nombre de couleurs différentes utilisées dans le premier voisinage de v

Qualité de l'heuristique

Le plus petit graphe 3-colorable qui trompe l'algotithme DSATUR qui trouve un 4-coloriage.

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

Le plus petit graphe qui prend DSATUR en défaut a avoir été exhibé possède 8 sommets et 12 arrêtes[2], il s'agit du plus petit possible pour cet algorithme.


Références

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article DSATUR de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Dsatur — DSAT[1] ou DSATUR est un algorithme de coloration de graphes créé par Daniel Brélaz en 1979 à l EPFL. Pour une classification: c est un algorithme de coloration séquentiel par heuristique; DSAT pour Degree SATuration. On considère un graphe… …   Wikipédia en Français

  • Coloration de graphe — En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets reliés par une arête soient de couleur différente. Est souvent recherchée l utilisation d un nombre minimal de… …   Wikipédia en Français

  • Coloration De Graphe — En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon qu aucun nœud du… …   Wikipédia en Français

  • Nombre chromatique — Coloration de graphe En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon… …   Wikipédia en Français

  • Theoreme quatre couleurs — Coloration de graphe En mathématiques, la coloration de graphe renvoie à un champ d études appartenant à la théorie des graphes. Il s agit de déterminer combien de couleurs différentes suffisent pour colorer entièrement un graphe de telle façon… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”