Coloration de graphe

Un article de Wikipédia, l'encyclopédie libre.

Sommaire 1 Définition 2 Propriétés 3 Méthodes 3.1 Algorithme de Welsh et Powell 3.2 Partition en sous-graphes stables 3.3 Implémentation Fortran 95 de Welsh Powell (partiel)

[modifier] Définition

Il existe deux façons de colorer un graphe.

• La première consiste à attribuer à chaque sommet une couleur sans que deux sommets reliés par une arête soient de la même couleur. C'est cette notion qui est utilisée dans le théorème des quatre couleurs et ses dérivés. Le nombre minimal de couleurs est appelé nombre chromatique qui se note γ(G). Il s'agit d'un problème classique en théorie des graphes.

• La seconde consiste au contraire à affecter certains sommets d'une couleur et à propager celle-ci. C'est la méthode dite du graphe chromatique qui est utilisée pour optimiser la génération de code sur une machine comportant un grand nombre de registres. Les méthodes de graphe chromatique permettent parfois de gagner un facteur de vitesse de 3 et plus sur un programme.

[modifier] Propriétés

• Déterminer le nombre chromatique d'un graphe est un problème NP-Complet dans le cas général. Il existe cependant des algorithmes polynomiaux pour certaines familles de graphes.
• Pour tout graphe biparti, γ(G) = 2.
• Soit un graphe G=(S,A), γ(G) peut-être de façon équivalente définit comme étant le plus petit entier r tel qu'il existe un homomorphisme de S vers K_r.
• Si D est le degré maximal du graphe, c'est-à-dire le plus grand degré parmi les degrés des sommets, alors le nombre chromatique est inférieur ou égal à 1 + D. Le nombre chromatique est aussi supérieur ou égal à l'ordre du plus grand sous-graphe complet du graphe.

[modifier] Méthodes

[modifier] Algorithme de 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 colorié tous les sommets.

Cette méthode n'aboutit pas forcément à une coloration minimale. Il faut donc observer si on peut faire mieux (c'est-à-dire avec moins de couleurs).

[modifier] Partition en sous-graphes stables

Un sous-graphe stable est un sous-graphe dont les sommets ne sont pas adjacents. Ses sommets peuvent donc être colorés de la même couleur. Le but est de trouver un nombre minimal de sous-graphes stables pour utiliser le moins de couleurs possible.

[modifier] Implémentation Fortran 95 de Welsh Powell (partiel)

 !----------------------!
 !                      !
 ! 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 sommet colorié
   j=1 ! indice du prochain sommet à traiter
   color=1 ! couleur du prochain sommet à colorier
   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