Mathématiques 514

Méthode du coloriage

Cette méthode peut être nécessaire pour résoudre des conflits.  Par exemple, chaque sommet représente un conférencier et chaque arête signifie que les deux conférenciers sont susceptibles d'attirer le même auditoire.

Dans ce graphe, les conférenciers A et H ne doivent pas être placés en même temps.

Pour résoudre ce problème, il suffit d'utiliser de la couleur.  Pour y arriver, il faut suivre les étapes suivantes:

1- Compter le degré de chaque sommet et les classer en ordre décroissant.

2- Prendre le sommet le plus élevé et lui attribuer une couleur. Disons rouge.  Alors F sera de sommet rouge.  Par la suite, il faut placer la couleur rouge à d'autres sommets de telle sorte que deux sommets adjacents (qui sont reliés par la même arête) portent des couleurs différentes.  Dans ce cas-ci, on pourrait attribuer la couleur rouge aux sommets A et G car ces deux sommets ne sont pas adjacent l'un de l'autre et ne sont pas adjacent à F.

3- Maintenant, attribuons la couleur bleue au sommet ayant le degré le plus élevé parmi ceux qui restent. Allons-y avec le sommet C. B et E sont adjacents à C donc prenons les sommets H et D.

4- Maintenant, attribuons la couleur verte au sommet ayant le degré le plus élevé parmi ceux qui restent. Il reste les sommets B et E et ils ne sont pas adjacents.

Conclusion: Comme il y a trois couleurs qui ont été utilisées dans ce graphe, il faudra tenir des conférences à 3 moments séparés. Dans un premier temps, il y aura les conférenciers A,F et G qui donneront leur conférence ensemble dans des locaux distincts évidemment. Dans un deuxième temps, ce sera au tour des conférenciers C,D et H.  Pour terminer, il y aura les conférenciers B et E.  Il faut savoir que l'ordre des conférences importe peu.

Dernière mise à jour effectuée le 29 décembre 2005