Vocabulaire des graphes

Un graphe est une structure de données à la fois simple et riche dans ses applications. Des sommets sont liés entre eux par des arcs ou des arêtes. Nous présentons ici le vocabulaire de base des graphes.

I. Exemples de graphes et définitions

On appelle graphe la donnée d’un ensemble fini V de points (ou sommets, ou vertices en anglais) et d’un ensemble E de liens entre ces points.

Exemples de réseaux pris dans la vie courante : représentation schématique du réseau Internet ; des personnes suivent d’autres personnes ; distances entre villes par la route.

Ces liens sont le choix d’un sommet s1 de départ et d’un sommet s2 d’arrivée. Lorsque les liens sont symétriques, c’est-à-dire lorsque l’existence d’un lien de s1 vers s2 implique l’existence d’un lien de s2 vers s1, le graphe est dit non orienté (les liens sont représentés par de simples lignes, premier exemple). Dans le cas contraire, on parle de graphe orienté (les liens sont représentés par des flèches, deuxième exemple).

Des poids peuvent être associés aux liens d’un graphe (orienté ou non), par exemple pour représenter la distance, le temps ou le coût nécessaires pour passer d’un état à un autre. On parle alors de graphe pondéré (troisième exemple).

On appelle ordre d’un graphe son nombre de sommets.

II. Vocabulaire des graphes non orientés

Les liens d’un graphe non orienté s’appellent des arêtes (edges en anglais).

Une chaîne est une suite (finie) consécutive d’arêtes sur un graphe non orienté. Par exemple 0,3,1,2 est une chaîne sur le graphe ci-contre.

Lorsqu’un graphe non orienté est « en un seul morceau », c’est-à-dire lorsqu’il existe pour tous sommets s1 et s2 une chaîne les reliant, le graphe est dit connexe. C’est le cas du graphe ci-contre, mais a contrario pas du réseau routier mondial.

Lorsqu’une chaîne mène d’un sommet s à lui-même, on parle de cycle. Par exemple le chemin 0,4,1,2,0 est un cycle.

III. Vocabulaire des graphes orientés

Les liens d’un graphe orienté s’appellent des arcs.

Un chemin est une suite (finie) consécutive d’arcs sur un graphe orienté. Par exemple 0,2,3 est un chemin sur le graphe ci-contre.

Un graphe orienté est dit connexe si le graphe non orienté associé, obtenu en transformant les arcs de ce graphe en arêtes, est connexe (le graphe ci-contre est connexe).

Lorsqu’il existe pour tous sommets s1 et s2 un chemin les reliant, le graphe est dit fortement connexe. Le graphe ci-contre n’est pas fortement connexe car il n’existe pas de chemin menant de 3 à 2.