Algorithme de coloration de graphe

- Principe de l'algorithme:

     L’algorithme de Widgerson est un algorithme de coloration assez spécial, car il n’est applicable que pour les graphes où 3 couleurs sont nécessaires. De plus, il fait appel à deux autres algorithmes de la coloration de graphe. Cet algorithme consiste à trouver tous les sommets avec au moins  voisins non coloriés, où n est égal au nombre de sommets du graphe. On applique à ces sommets l’algorithme de ‘2-coloriage’. On va donc utiliser deux couleurs différentes, pour colorier les voisins de ces sommets. Une fois cette étape réalisée, on applique l’algorithme glouton aux sommets restants.

- Analyse de l'algorithme:

     L’algorithme Widgerson ne s’applique que pour les algorithmes 3-coloriables. Pour utiliser cet algorithme il faut donc s’assurer préalablement que le graphe à colorier rempli cette condition. Ensuite, il nécessite la connaissance des algorithmes glouton et 2-coloriage, ce qui peut rendre son exécution plus compliquée.

- Principe de l'algorithme:

     Tout comme l’algorithme de Welsh-Powell, l’algorithme Dsatur utilise un tri des sommets par ordre de degrés décroissants. Son fonctionnement est assez similaire à l’algorithme glouton. Une fois le tri des sommets effectué, on colorie le sommet de degré maximum avec la couleur 1. Ensuite, le prochain sommet à traiter est le sommet avec le plus haut degré de saturation (DSAT, nombre de couleurs différentes utilisées pour colorier ses voisins). Si plusieurs sommets ont le même degré de saturation, celui choisi est celui avec le plus grand nombre de degrés. On associe à ce sommet le plus petit entier possible, et on le colorie en la couleur associée. On répète ce procédé jusqu’à ce que tous les sommets soient coloriés.

- Analyse de l'algorithme:

     L’algorithme Dsatur, comme nous l’avons vu précédemment, utilise également un tri des sommets préalable. De la même manière que pour l’algorithme de Welsh-Powell, cette étape peut donc demander du temps. Ensuite, de même que pour l’algorithme glouton, l’algorithme Dsatur est assez simple à exécuter. Concernant, le résultat obtenu, l’algorithme fournit un résultat optimal dans 90% des cas, mais il est possible d’obtenir un mauvais résultat pour certains graphes.

- Principe de l'algorithme:

     Un algorithme glouton consiste à résoudre un problème « pas à pas » et de choisir à chaque étape le meilleur choix possible. En coloration de graphe, l’algorithme glouton associe des couleurs à des entiers naturels. Pour chaque sommet, il s’agit de choisir le plus petit entier qui n’appartient pas à l’ensemble des entiers utilisés pour colorier les voisins de ce sommet. On colorie alors le sommet en la couleur associée à l’entier.

- Analsye de l'algorithme:

     L'exécution de l'algorithme glouton est plutôt simple et intuitive. Cependant, pour des graphes possédant beaucoup d’arêtes, son exécution peut s’avérer plus longue et compliquée. De plus, il existe des graphes où le résultat obtenu est très loin d’une coloration optimale.

- Principe de l’algorithme :

Cet algorithme se décompose en plusieurs étapes :

• classer les sommets par ordre de degrés décroissant
• traiter le premier sommet de la liste, en lui attribuant une couleur
• attribuer la même couleur à au premier sommet non-adjacent
• attribuer également la même couleur au prochain sommet non-adjacent au premier et au second
• poursuivre ce procédé jusqu’à la fin de la liste des sommets
• attribuer une deuxième couleur au premier sommet pas encore coloré
• répéter les précédentes opérations tant que tous les sommets ne sont pas colorés

- Analyse de l'algorithme:

     L’une des faiblesses de l'algorithme de Welsh-Powell pourrait reposer sur le temps nécessaire à son exécution. En effet, il est nécessaire de trier préalablement les sommets du graphe. Pour des graphes avec de nombreux sommets, cela peut donc prendre du temps. Ensuite, cet algorithme présente également des limites, puisque qu’il existe des contre-exemples, où la coloration obtenue n’est pas optimale. Cet algorithme n’est donc pas parfait, même si dans la plupart des cas, il propose un résultat correct.