Coloration de graphe
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Le problème de la coloration de graphe est en fait à l'origine de la théorie des graphes elle-même, puisque cette théorie est motivée, à l'origine, par le regroupement de diverses questions (et réponses) portant sur des structures combinatoires proches les unes des autres. Ainsi le problème des quatre couleurs (voir Théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir d'axiomes. Un théorème est à distinguer...) des quatre couleurs) consistait à trancher la question suivante : peut-on colorer chacune des faces d'un polyèdre (Traditionnellement, un polyèdre est une forme géométrique à 3 dimensions ayant des faces planes qui se rencontrent le long d'arêtes droites. Le mot polyèdre provient du grec classique...) (de l'espace usuel) sans que deux faces adjacentes aient la même couleur (La couleur est la perception subjective qu'a l'œil d'une ou plusieurs fréquences d'ondes lumineuses, avec une (ou des) amplitude(s) donnée(s).) en n'utilisant que quatre couleurs au maximum ? Ce problème dépend uniquement de la structure combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.) de graphe planaire (Dans la théorie des graphes, un graphe planaire est un graphe quelconque qui a la particularité de pouvoir se représenter sur un plan sans...) que l'on peut associer naturellement à tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) polyèdre (les faces correspondent aux sommets et l'adjacence entre faces à l'adjacence entre sommets). L'extension du problème aux graphes quelconques (pas nécessairement planaires) a trouvé sa motivation (La motivation est, dans un organisme vivant, la composante ou le processus qui règle son engagement dans une action ou expérience. Elle en détermine le déclenchement dans une certaine...) théorique principale avec la conjecture (En mathématiques, une conjecture est une assertion qui a été proposée comme vraie, mais que personne n'a encore pu démontrer ou réfuter.) de Berge (récemment résolue, voir Théorème des graphes parfaits), et une motivation liée à diverses applications concrètes (notamment dans l'affection de fréquence).

Donnons maintenant une définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) du problème.

Définition

La notion de coloration n'est définie que pour les graphes sans boucle, et la multiplicité des arêtes ne joue (La joue est la partie du visage qui recouvre la cavité buccale, fermée par les mâchoires. On appelle aussi joue le muscle qui sert principalement à ouvrir et fermer la...) aucun rôle. Donc, soit G un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) simple (sans boucle ni arête multiple), un stable de G est un sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B. Il peut par contre y avoir des...) de sommets deux-à-deux non-adjacent, et une coloration de G est une partition de son ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme l'énonçait...) de sommets en stables.

Notons que la définition originale de la coloration est la suivante[1] : une coloration de G est une fonction associant à tout sommet de G une couleur (généralement un élément de l'ensemble d'indices des couleurs {1,2,...,n}n est le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de sommets du graphe) telle que deux sommets adjacents n'ont pas la même couleur. On lui préfère généralement la définition que nous avons donné en premier, car, pour la plupart des questions liées au concept de coloration, on ne souhaite pas différencier les colorations qui ne sont distinctes que à permutation (En mathématiques, la notion de permutation exprime l'idée de réarrangement d'objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à...) des indices de couleurs près [2]. C'est le cas pour le problème central lié à la coloration, celui de déterminer le nombre chromatique d'un graphe: le nombre chromatique de G est le nombre minimum de couleur dans une coloration de G. Dans ses différents ouvrages (en français ou en anglais), Claude Berge (Claude Berge, né le 5 juin 1926 et décédé le 30 juin 2002, était un mathématicien et artiste français.) a utilisé les deux notations γ(G) et χ(G) pour désigner le nombre chromatique de G. De nos jour (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons du Soleil éclairent le ciel. Son début (par rapport à minuit heure locale) et sa durée...), la plupart des ouvrages adoptent le symbole χ(G) pour désigner le nombre chromatique de G (γ(G) concerne généralement un invariant lié au concept de cycle).

  1. Dans certains contextes (marginaux), on parle aussi de coloration pour désigner une fonction associant une couleur aux sommets d'un graphe mais satisfaisant d'autres propriétés (e.g. dans le contexte (Le contexte d'un évènement inclut les circonstances et conditions qui l'entourent; le contexte d'un mot, d'une phrase ou d'un texte inclut les mots qui...) de l'optimisation de la génération de code sur une machine comportant un grand nombre de registres).
  2. Par-exemple, si G est constitué de deux sommets u et v et d'une arête les reliant, alors les deux fonctions f et g sont des colorations différentes pour la deuxième définition mais équivalentes pour la première, avec f(u)=1, f(v)=2, et g(u)=2, g(v)=1.

Aspects algorithmiques généraux

Déterminer le nombre chromatique d'un graphe est un problème NP-Complet dans le cas général. En fait, on peut en dire plus si l'on considère le problème de décision (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre,...) suivant: Soit G un graphe et k un entier, peut-on colorer G avec moins de k couleurs ?

Si k=2 il s'agit de décider si G est biparti ou non. Ceci est facile car ces graphes sont caractérisés par la non présence d'un structure interdite: celle de cycle impair. Par-contre pour tout k fixé supérieur à 3 le problème devient NP-Complet.

Ainsi, à moins que P=NP, il n'existe pas d'algorithme polynomial déterminant le nombre chromatique d'un graphe arbitraire. Pour certaines classes de graphes par-contre de tels algorithmes existent. C'est notamment le cas pour les graphes triangulés (ou chordaux) dans lequel le problème se résoud en temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) linéaire. Un résultat nettement plus difficile (de László Lovász et al.) établit (en développant toute une théorie) que l'on peut déterminer en temps polynomial le nombre chromatique de tout graphe parfait (pour une définition voir Théorème des graphes parfaits).

Parmi les algorithmes exactes (donc de complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri...) exponentielle (La fonction exponentielle est l'une des applications les plus importantes en analyse, ou plus généralement en mathématiques et dans ses domaines d'applications. Il existe plusieurs définitions équivalentes : un...) dans le cas général) citons l'algorithme de Zykov (par la méthode de Branch and Bound). L'importance du problème a donné lieu à l'élaboration de nombreuses heuristiques spécifiques au problème, spécialement des algorithmes séquentiels de coloration sommet par sommet (dsatur, cosine, maya, etc.). Elle a aussi sucité de nombreuses expérimentations des méthodes approchées générales: méta-heuristique (recuit simulé, tabou search), ou encore algorithme génétique (La génétique (du grec genno γεννώ = donner naissance) est la science qui étudie l'hérédité et les gènes.)...

Donnons quelques exemples des méthodes approchées spécifiques au problème de la coloration.

Algorithme de Welsh et Powell

Voici un exemple qui, en plus, fournit une preuve constructive du fait suivant: \chi(G) \le \Delta(G)+1, où Δ(G) représente le degré maximum d'un sommet de G (le degré d'un sommet étant le nombre des arêtes qui lui sont incidentes). Pour s'en convaincre, appliquons l'algorithme suivant (Welsh et Powell):

  1. Repérer le degré de chaque sommet.
  2. Ranger les sommets par ordre de degrés décroissants. (dans certains cas plusieurs possibilités)
  3. Attribuer au premier sommet (A) de la liste une couleur.
  4. Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A).
  5. Suivre (si possible) la liste jusqu'au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
  6. Continuer jusqu'à ce que la liste soit finie.
  7. Prendre une deuxième couleur pour le premier sommet (D) non encore colorié de la liste.
  8. Répéter les opérations 4 à 6.
  9. Continuer jusqu'à avoir coloré tous les sommets.

Remarquons que cette méthode peut aboutir à la pire des colorations possibles, par-exemple si le graphe G a la structure d'étoile (Une étoile est un objet céleste émettant de la lumière de façon autonome, semblable à une énorme boule de plasma comme le Soleil, qui est l'étoile la plus proche de la Terre.) (chacune des arêtes de G est incidente à un même sommet particulier) son nombre chromatique est 2 (si G a au-moins une arête) tandis que Welsh-Powell donne une coloration utilisant autant de couleur que de sommets ! L'heuristique (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :) DSATUR permet d'éviter ce problème.

DSATUR

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) de la manière suivante:

 
 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 (La notion de voisinage correspond à une approche axiomatique équivalente à celle de la topologie. La topologie traite plus naturellement les notions globales...) de v 
 

L'algorithme DSATUR est un algorithme de coloration séquentiel, au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du ralentissement du vieillissement,...) ou il colorie un seul sommet à la fois et tel que:

 
 au départ le graphe n'est pas coloré 
 on colorie un sommet non-déjà coloré 
 on stoppe DSATUR quand tous les sommets de G sont coloré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é. 
 2. Colorer un sommet de degré maximum avec la couleur 1. 
 3. Choisir un sommet non coloré avec DSAT maximum. Si conflit choisir celui avec degré maximum. 
 4. Colorer ce sommet par la plus petite couleur possible 
 5. Si tous les sommets sont colorés alors stop. Sinon aller en 3. 
 

Implémentations des heuristiques présentées

Deux versions de l'algorithme DSATUR sont accessibles:

A titre illustratif, voici une implémentation (Le mot implantation peut avoir plusieurs significations :) (partielle) de Welsh-Powell en Fortran 95:

 
 !----------------------! 
 !                      ! 
 ! Algo de Welsh Powell ! 
 !______________________! 
 function WP(M,nu_heuristique) result(RES) 
 logical, dimension(:,:), intent(in) :: M 
 integer, intent(in):: nu_heuristique 
 TYPE(VOISIN), dimension(:), pointer:: TMP,TMP1,TMP2 
 integer, dimension(:),pointer:: RES 
 integer:: h,i,j,color,last_color 
 i=0 ! nbre de sommets colorés 
 j=1 ! indice du prochain sommet à traiter 
 color=1 ! couleur du prochain sommet à colorer 
 allocate(RES(0:size(M,1))) 
 ! DETERMINATION DE L'HEURISTIQUE A UTILISER: 
 if (nu_heuristique==0) then 
 ! version brute 
 call CONV_VOISINS(M,TMP) 
 else 
 ! version plus fine: 
 call CONV_VOISINS_TRIE(M,TMP) 
 end if 
 RES=0 
 ! tant que tous les sommets ne sont pas marqué 
 do while(j<=size(M,1)) 
 ! si le sommet courant n'est pas marqué 
 if (RES(TMP(j)%NUM)==0) then 
 RES(TMP(j)%NUM)=color ! on colorie le sommet 
 i=i+1 
 last_color=color 
 ! on cherche les non voisins de j dans l'ensemble de la matrice 
 call POINTS_NON_VOISINS(TMP,TMP(j)%NUM,TMP1) 
 ! tant qu'il reste des non voisins 
 h=1 
 do while(h<=size(TMP1,1)) 
 if (RES(TMP1(h)%NUM)==0) then 
 RES(TMP1(h)%NUM)=color 
 i=i+1 
 ! et on déduit le sous ensemble n'étant ni voisin de j et des sommets déjà marqué 
 call POINTS_NON_VOISINS(TMP1,TMP1(h)%NUM,TMP2) 
 if (size(TMP2)==0) exit 
 call COPIE(TMP2,TMP1) 
 h=0 
 end if 
 h=h+1 
 end do 
 j=j+1 ! on passe au sommet suivant 
 color=color+1 ! ainsi qu'à la couleur suivante 
 else 
 j=j+1 ! sinon on passe au sommet suivant 
 end if 
 end do 
 RES(0)=last_color 
 end function WP 
 
Page générée en 0.118 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique