Techniques et concepts de l'entreprise, de la finance et de l'économie 
(et fondements mathématiques)

Les graphes non orientés

logo

 

 

 

 

 

 

 

 

 

 

Vocabulaire des graphes non orientés et exemple

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, par exemple) 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.

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. Ces dernières sont représentées par des traits simples, contrairement aux arêtes 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 appelé 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.

arêtes

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, cette chaîne est fermée : c’est un circuit. Si l'on ne passe jamais par la même arête pour faire le tour du circuit, 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 ou un cycle est eulérien 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é χ(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).

graphe complet

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.

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).

planning

Sans dessiner de graphe, on constate sur l’emploi du temps que l’engorgement se situera entre 15h30 et 16h puisque 5 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.

1er graphe

Ensuite, on classe les sommets par degrés décroissants.

classement

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à :

jaune et vert

On continue avec d’autres couleurs qui correspondent à autant de salles à louer. L’étape suivante peut être celle-ci :

3 couleurs

Et pour finir, on obtient non seulement le nombre de salles à louer mais aussi leur planning :

toutes couleurs

Note : voir aussi la page graphes et matrices.

 

graphe

 

© JY Baudot - Droits d'auteur protégés