Algorithme de coloration de graphe

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