Algorithme de coloration de graphe

Première étape:

Après avoir analysé différents algorithmes, et réalisé plusieurs tests, nous pensons que l’une des premières étapes de notre algorithme, serait la recherche du type de graphe étudié. Par exemple, nous savons pour certains types de graphes, quel sera le nombre chromatique.

Pour les graphes ‘chemin’ nous savons déjà que le nombre chromatique obtenu sera égal à 2. Pour les graphes ‘complets’ nous savons que le nombre chromatique obtenu sera égal au nombre de sommets du graphe. Enfin, un graphe sans arête aura un nombre chromatique égal à 1.

L’idée serait donc de pouvoir analyser le graphe pour faire en sorte de reconnaître ces graphes spéciaux. Nous étudierons alors le nombre de degrés de chaque sommet, ainsi que le nombre d’arêtes, pour identifier ces graphes.

Exemple d'une solution possible pour la coloration d'un graphe:

Soit un graphe qui n'est pas un 'chemin', 'complet', ou sans arete:

1. On cherche le sommet avec le plus grand nombre de voisins.
2. On colorie ce sommet en une couleur.

3. On colorie les voisins du sommet, qui ne sont pas adjacents entre eux, en une deuxième couleur.

4. On cherche, parmi les sommmets non coloriés, le sommet avec le plus grand nombre de voisins.

5. On répète les étapes 2 à 4 jusqu'à ce que chaque sommet soit colorié .

Analyse de la première solution:

Nous remarquons que cette première solution proposée se rapproche fortement de l'algorithme de Welsh-Powell. En effet nous traitons les sommets dans l'ordre décroissant de leur degré. La différence avec l'algorithme de Welsh-Powell, est que nous traitons et colorons les sommets adjacents au sommet courant. Or, dans l'algorithme de Welsh-Powell, les sommets non adjacents au sommet courant sont d'abord traités et colorés. 

Recherche d'une deuxième solution:

Cette deuxième solution consisterait à choisir un sommet de départ, puis de traiter tous ces voisins. Il s'agirait alors d'analyser, pour chaque sommet, ces différents voisins. La coloration du graphe par cette solution serait donc établie en parcourant un chemin. 

Algorithme de la deuxième solution:

Soit un graphe qui n'est pas un 'chemin', 'complet', ou sans arete:

Soit un sommet courant
    Si déjà colorié

          ne pas changer sa couleur
    Si non colorié

          lui attribuer une couleur
          sommet initial <-- sommet courant

Pour tout ces voisins non coloriés
    Si adjacent d'un sommet déjà traité
          attribuer couleur d'un voisin du sommet courant, non adjacent au voisin courant

    Sinon si sommet initial = sommet courant
           attribuer au premier voisin une nouvelle couleur

    Sinon  
          attribuer couleur différente du sommet courant
  

Choisir comme sommet courant un sommet traité précedemment
repeter l'algorithme tant que tous les sommets ne sont pas coloriés

Exemples de coloration de graphe avec l'algorithme ci-dessus:

• Exemple 1:

On choisit le sommet 1 comme sommet initial:

On colorie le sommet initial, et tous ces voisins:

On choisit le sommet 2 comme sommet courant, et on colorie son voisin.
Le sommet 3 est adjacent à un sommet traité, donc on le colorie en la couleur d'un sommet adjacent au sommet 2, non adjacent au sommet 3.

On choisit le sommet 7 comme sommet courant, et on colorie son premier voisin:

On colorie le deuxième voisin du sommet 7:

• Exemple 2:

On choisit le sommet initial et on colorie ses voisins:

On choisit le sommet 2 et on colorie ses voisins:

On choisit le sommet 8 et on colorie son voisin:

On choisit le sommet 7 et on colorie son voisin: