Graphes non orientés et coloration
En entreprise, certains problèmes d’affectation apparaissent comme de vrais casse-têtes lorsqu’on cherche à les résoudre sans méthode. Même les analystes qui ont étudié les graphes au lycée (terminale ES spécialité maths ou aujourd'hui maths expertes) ou durant leurs études supérieures pensent rarement à réactiver la zone cérébrale dans laquelle ils ont mis en sommeil cette branche si particulière des mathématiques. Il est vrai que les graphes sont surtout affaires de spécialistes.
Vocabulaire
Un graphe est constitué de deux ensembles finis, l’un de sommets ou nœuds (graphiquement, des points) et un autre d’arêtes (quoique l'ensemble des arêtes peut être vide). Ces dernières sont représentées par des traits simples, contrairement aux arcs des graphes orientés qui prennent la forme de flèches. À leurs extrémités se trouvent les sommets. Une arête qui a le même sommet à ses deux extrémités est tout simplement une boucle. Le nombre de sommets d’un graphe est l’ordre de ce graphe. Il peut aussi exister des arêtes multiples. Les sommets du graphe ci-dessous sont représentés par des losanges. Les traits indiquent une boucle et une arête triple.
Le degré d’un sommet est le nombre d’extrémités qui lui sont rattachées (et non pas le nombre d’arêtes puisqu’une boucle compte pour deux), si bien que la somme des degrés d'un graphe est égale au double du nombre d'arêtes. Notez au passage que ce vocabulaire est aussi utilisé pour définir des polyèdres (à titre d'exemple, un octaèdre régulier comprend six sommets de degré 4).
Lorsque deux sommets sont liés par au moins une arête, ils sont voisins ou adjacents. L’ensemble de \(n\) sommets voisins forme une chaîne de longueur \(n.\) Si un sommet a pour arêtes la première et la dernière d’une chaîne, on a affaire à un cycle. Un graphe est complet lorsque tous ses sommets sont voisins entre eux.
Le sous-ensemble d’un graphe dans lequel chaque couple de sommets est relié par une chaîne est un sous-graphe connexe.
Une chaîne est eulérienne lorsque toutes les arêtes du graphe en font partie (une seule fois). Il faut pour cela que deux sommets (et pas un de plus) soient de degré impair.
Le nombre chromatique d’un graphe \(G,\) noté \(\chi (G),\) est le nombre de couleurs nécessaires pour colorier chaque sommet, sachant que deux voisins ne peuvent avoir la même couleur. Le nombre chromatique d’un graphe complet est évidemment égal à son ordre (soit 4 dans l’exemple ci-dessous).
Le nombre chromatique d’un graphe planaire, c’est-à-dire dans lequel les arêtes ne se croisent jamais, est toujours inférieur ou égal à 4. Ainsi, quatre couleurs suffisent pour teinter un planisphère où aucun pays n’a la même couleur que l’un de ses voisins. Cette particularité étonnante a occupé les mathématiciens pendant plus d'un siècle et la preuve n'a été établie qu'en 1976. Le théorème des quatre couleurs fut d'ailleurs le premier théorème a être démontré avec le soutien d'un ordinateur.
Sur un graphe simple, c’est-à-dire sans boucle et sans arête multiple, le nombre chromatique ne peut pas être supérieur au nombre 1 + degré maximal.
Exemple d’un algorithme de coloration
Lors d’un salon, huit conférences sont prévues. Mais les orateurs ont des emplois du temps surchargés et c’est en fonction de leurs disponibilités que leurs conférences sont programmées. La seule latitude de l’organisateur consiste à louer le moins de salles possible (horaires des conférences en bleu).
Sans dessiner de graphe, on constate sur l’emploi du temps que l’engorgement se situera entre 15h30 et 16h puisque cinq salles seront requises. Heureusement, toutes les applications des graphes ne sont pas aussi inutiles…
Bref. Une représentation des contraintes consiste à considérer les orateurs comme des sommets, les arêtes indiquant leurs présences simultanées.
Ensuite, on classe les sommets par degrés décroissants.
Puis on prend un des sommets qui a le degré maximum (ici, pas le choix puisqu’il n’y en a qu’un) et on lui affecte une couleur. Par exemple le jaune. On jaunit également le ou les sommets non adjacents , ni avec lui ni entre eux. Ensuite, on passe au suivant et on lui affecte une autre couleur. Par exemple le vert. Nous en sommes là :
On continue avec d’autres couleurs qui correspondent à autant de salles à louer. L’étape suivante peut être celle-ci :
Et pour finir, on obtient non seulement le nombre de salles à louer mais aussi les informations qui permettront d'établir un planning de leurs utilisations :
Note : voir aussi la page sur les graphes et matrices et l'exercice sur graphes non orientés, issu d'une épreuve du bac ES spé maths. Voir aussi la représentation des réseaux sociaux et les exercices associés.
