Définitions élémentaires
Définition : Définition d'un graphe
Un graphe est un couple (X,E) où X est un ensemble et E est un sous-ensemble de X x X.
Définition : Définition des objets
Les éléments de X du graphe (X,E) sont appelés les points ou les sommets ou les nœuds du graphe.
Ces différentes dénominations sont issues des domaines d'application de la théorie des graphes. Par exemple, le terme de nœud est le plus fréquemment utilisé lorsque le graphe est un réseau de communication.
Définition : Définition des liens
On appelle arc du graphe (X,E) tout couple (x,y) de E noté aussi x Γ y,
x est appelé origine de l'arc (ou encore extrémité initiale),
y est appelé extrémité de l'arc (ou encore extrémité terminale),
l'arc (x,x) est appelé boucle.
On appelle arête du graphe (X,E) tout sous ensemble de deux points {x,y} où x est différent de y et le couple (x,y) ∈ E.
x et y sont appelés les extrémités de l'arête.
Remarque :
Dans un graphe orienté, les deux arcs (x,y) et (y,x) ne correspondent qu'à une seule arête. Une boucle n'est pas une arête.
Dans un graphe non orienté, l'ensemble E contient des sous-ensembles de deux points {x,y} avec x ≠ y.
D'un point de vue pratique, selon les représentations du graphe, l'arête {x,y} et la même arête {y,x} est représentée une seule fois ou deux fois.
Si l'arête {x,y} existe, il est tout aussi correct d'écrire {y,x} ∈ E que {x,y} ∈ E.
Remarque : Première représentation d'un graphe
Il est à noter qu'un graphe orienté est défini par la liste de ses points et la liste de ses arcs (ou de ses arêtes pour les graphes non orientés).
Cette représentation est intéressante si on doit, dans un algorithme, "visiter" les arcs ou les arêtes d'un graphe, c'est par exemple le cas pour l'algorithme de Kruskal pour les arbres de recouvrement minimaux (voir le chapitre sur les arbres dans le module "Algorithmes de graphe").
Définition : Successeurs d'un point
L'ensemble des successeurs d'un point x est l'ensemble des points y tels que (x, y) ∈ E (ou encore x Γ y) et est noté Γ(x).
Cet ensemble est aussi dénommé liste des successeurs d'un point.
Remarque : Deuxième représentation d'un graphe
Il est à noter qu'un graphe orienté est entièrement défini par les listes des successeurs de tous les points.
Cette représentation est intéressante lorsque l'on a besoin de "visiter" les successeurs des points. C'est par exemple le cas lorsque l'on cherche les descendants d'un point (voir les algorithmes les plus simples présentés dans ce chapitre). Cela permet une exploration systématique en partant d'un point donné.
Illustration de l'ensemble des successeurs des points d'un graphe
Le schéma ci-dessus présente un exemple de graphe orienté et fournit les ensembles de successeurs de tous ses points.
Illustration de la notion de successeurs sur la représentation graphique de graphes
Cliquez sur les flèches pour faire tourner les exemples proposés.
Définition : Prédécesseur d'un point
L'ensemble des prédécesseurs d'un point x est l'ensemble des points y tels que (y, x) ∈ E (ou encore x Γ-1 y ou encore y Γx) et est noté Γ-1(x). Γ-1 est la relation réciproque de Γ.
Cette ensemble est aussi dénommé liste des prédécesseurs d'un point.
Remarque : Troisième représentation d'un graphe
Il est à noter qu'un graphe orienté est entièrement défini par les listes des prédécesseurs de tous les points.
Cette représentation est intéressante lorsque l'on a besoin de "visiter" les prédécesseurs des points. C'est par exemple le cas lorsque l'on cherche les plus courts chemins qui partent d'un point donné en utilisant la programmation dynamique (voir le chapitre sur les problèmes de cheminement du module "Algorithmes de graphe").
Illustration de l'ensemble des prédécesseurs des points d'un graphe
Le schéma ci-dessus présente un exemple de graphe orienté et fournit les ensembles de prédécesseurs de tous ses points.
Illustration de la notion de prédécesseurs sur la représentation graphique de graphes
Cliquez sur les flèches pour faire tourner les exemples proposés.
Exercice sur les notions de successeurs et de prédécesseurs
Cliquez sur Anim pour démarrer l'animation ou sur Guide pour avoir les explications sur le fonctionnement de l'animation.
