Voir : http://oneweb.utc.edu/~Christopher-Mawata/petersen/lesson8.htm
Définition 1
Colorer un graphe, c'est affecter une couleur à chacun de ses sommets de telle manière que deux sommets adjacents ne portent pas la même couleur.
Illustration : différentes colorations d'un même graphe
Définition 2
On appelle graphe d'incompatibilité, un graphe où chaque arête relie deux sommets incompatibles pour une relation donnée.
Illustration : cliquer sur le graphe pour découvrir l'animation
|
Des étudiants sont inscrits à un examen dans les disciplines suivantes :
Plusieurs candidats peuvent passer une même matière dans la même demi-journée, mais chaque candidat ne doit avoir qu'un examen par demi-journée. |
|
||||||||||||||||||||||||||||
Définition 2
On appelle nombre chromatique d'un graphe le plus petit nombre de couleurs permettant de le colorer.
Théorème 1
Le nombre chromatique d'un graphe complet est égal au nombre de sommets du graphe.
Théorème 2
Le nombre chromatique d'un graphe :
- est supérieur ou égal à l'ordre du plus grand sous graphe complet de ce graphe,
- est inférieur ou égal au plus haut degré des sommets de ce graphe augmenté de 1.
Un exemple d'algorithme de coloration : l'algorithme "glouton" de Welsh-Powell
Cliquer sur le graphe proposé pour en voir la mise en œuvre
