Mathématiques 2: Géométrie
Les graphes
L'optimisation par les graphes
Nombre chromatique
Méthode du coloriage

1. Introduction

Lorsqu'une situation implique une planification de partage d'un ensemble en groupes, il peut s'avérer utile d'utiliser un graphe coloré.

C'est le cas par exemple pour planifier la façon de placer des individus devant des tables dans une salle, de gérer les horaires d'examens.

Dans ce type de graphe, un sommet représente un élément impliqué, et une arête, une incompatibilité ou un conflit entre deux de ces éléments.

Le nombre chromatique est le nombre minimal de couleurs différentes nécessaires pour colorer tous les sommets de ce graphe sans que deux sommets adjacents aient la même couleur.

Ce nombre est égal au plus grand degré des sommets du graphe diminué de 1.

2. Algorithme du nombre chromatique

Voici les 7 étapes de résolution d'un problème avec l'utilisation du nombre chromatique :

1. Représenter la situation à l'aide d'un graphe dans lequel les sommets représentent les éléments et les arêtes représentent les incompatibilités ou les conflits,

2. Énumérer tous les sommets du graphe et les placer en ordre décroissant de degré. Pour deux sommets ayant le même degré, l'ordre n'a pas d'importance,

3. Attribuer une première couleur au sommet ayant le plus grand degré,

4. Appliquer cette même couleur à tous les sommets de degré inférieur qui ne sont pas reliés à ce sommet et qui ne sont pas reliés entre eux,

5. Répéter les étape 3 et 4 avec de nouvelles couleurs jusqu'à ce que tous les sommets soient colorés,

6. Le nombre chromatique du graphe est égal au nombre de couleurs utilisées,

7. Conclure sur ce partage en groupes.

3. Exemple

Voici un graphe qui représente les tests à faire passer aux élèves d'une école secondaire. Les tests se déroulent dans des locaux différents.

Les sommets sont occupés par des matières (ou disciplines). Chaque arête signifie que les deux tests peuvent impliquer un même étudiant.

Le lien « chimie -- arts »: signifie qu'un élève aura à passer les deux tests, de chimie et d'arts.

On sait qu'un élève ne peut pas passer deux tests ou plus simultanément.

Ainsi toutes les arêtes représentées sur le graphe ne doivent pas exister parceque ce sont les sources du conflit d'horaires.

Comment doit-on donc procéder pour que chaque élève puisse passer tous ses tets sans conflit d'horaires?

La méthode de coloriage répond à la question.

• Voici le tableau des sommets énumérés en ordre décroissant de degré:

sommet	degré
Physique	5
histoire	4
arts	4
chimie	4
anglais	4
chimie	3
français	3
maths	3

• On attribue une couleur (orange) pour le sommet de degré le plus haut (physique,5),
• On applique cette couleur orange aux autres sommets qui ne sont pas adjacents à « physique » et ne sont pas adjacents l'un de l'autre. Ces sommets sont: « maths » et « français » .

• Maintenant, on applique une autre couleur (blue) à l'un des sommets de degré immédiatement inférieur qui est 4, soit le sommet «chimie »

• On applique cette couleur blue aux autres sommets qui ne sont pas adjacents à « chimie » et ne sont pas adjacents l'un de l'autre. Ces sommets sont: « histoire » et « sport » .

• Maintenant, on applique une autre couleur (jaune) à l'un des sommets de degré immédiatement inférieur qui est 3, soit le sommet « anglais »

• On applique cette couleur jaune aux autres sommets qui ne sont pas adjacents à « anglais » et ne sont pas adjacents l'un de l'autre. Il ne reste que le sommet « arts » .

Trois couleurs ont été utilisées sur le graphe. Le nombre chromatique est donc égal à 3.


Conclusion:

Trois couleurs ont été utilisées. Il faut donc faire passer les tests à trois séances séparées, dont l'ordre n'a aucune importance.

Au court de la première séance, on fait passer des tests en physique, maths, et français ,

Au court de la deuxième séance, on fait passer des tests en chimie, histoire et sport ,

Au court de la troisième séance, on fait passer des tests sur les deux matières qui restent: anglais et arts .