Le vocabulaire des graphes

Cet article a pour vocation de faire un glossaire de tout le vocabulaire des graphes. Il est réparti dans l’ordre alphabétique.

Prérequis

• Graphes, sommets, arêtes

Les mots des graphes

Dans toute la suite, on désignera G = (V,E) un graphe.

Chaîne

Soient x et y deux sommets d’un graphe. Une chaîne reliant x à y est un ensemble d’arêtes consécutives reliant x à y. C’est donc une suite d’arêtes vérifiant :

(v_1, \ldots, v_n) : v_0 = x, v_n = y, (v_i,v_{i+1}) \in E

Une chaîne est dite élémentaire si elle ne passe pas 2 fois par le même sommet.

Une chaîne est dite simple si elle ne passe pas 2 fois par la même arête.

La longueur d’une chaîne est tout simplement caractérisée par le nombre d’arêtes la constituant.

Cycle

Un cycle est une chaîne pour laquelle les sommets de départ et d’arrivée sont les mêmes, c’est-à-dire x = y.

Diamètre

Le diamètre d’un graphe est la plus grande distance possible qui puisse exister entre deux de ses sommets. C’est l’excentricité maximale.

Degré

• Le degré d’un sommet est le nombre d’arêtes partant de ce sommet.
• Dans le cas d’un graphe orienté, on définit d^-(s) le nombre d’arêtes entrantes dans s et d^+(s) le nombre d’arêtes sortantes dans s. On a alors \deg(s) = d^+(s) + d^-(s).
• On note \Delta(G) le maximum des degrés des sommets d’un graphe et \delta(g) le minimum des degrés des sommets d’un graphe.

Excentricité

L’excentricité d’un sommet est la distance maximale entre un sommet et les autres sommets du graphe.

Graphe complet

Un graphe est dit complet si et seulement si tous ses sommets sont reliés par une arête. Mathématiquement, cela peut s’écrire si le graphe n’est pas orienté :

\forall x,y \in V, (x,y) \in E 

Si le graphe est orienté :

\forall x,y \in V, (x,y) \in E \wedge (y,x) \in E 

Graphe connexe

Un graphe est dit connexe si pour tout sommet il existe une chaîne le reliant à tout autre sommet.

Graphe fini

Un graphe est dit fini si son ordre est fini.

Graphe planaire

Un graphe est dit planaire si on peut le dessiner dans le plan sans que 2 arêtes ne se croisent.

Ordre d’un graphe

L’ordre d’un graphe est tout simplement le nombre de sommets d’un graphe.

Rayon

Le rayon d’un graphe est la plus petite distance à laquelle puisse se trouver un sommet de tous les autres. En d’autres termes c’est l’excentricité minimale.

Sommets adjacents

Deux sommets sont dits adjacents si et seulement si ils sont reliés par une arête.