algorithme de coloration

CALCUL
COMBINATOIRE

Algorithme de théorie des graphes. Il s’agit d’attribuer une couleur aux sommets d’un graphe non orienté, de façon à ce que deux sommets adjacents n’aient pas la même coloration. Le nombre minimal de couleurs nécessaires est appelé nombre chromatique du graphe. Un des algorithmes est celui de Welsh et Powell , qui donne une bonne coloration en ce sens qu’il n’utilise pas un trop grand nombre de couleurs mais n’assure pas que la coloration est minimale.