Algorithme de coloration de graphe

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