Vocabulaire des graphes orientés
Les graphes orientés sont enseignés dans différents cursus liés à l'économie et à l'informatique. Cette page introduit cet outil mathématique et le vocabulaire qui lui est lié, parfois différent de celui des graphes non orientés. Précisons au passage que les arbres de probabilités et les organigrammes sont eux aussi des graphes orientés.
On ne présentera ici que les graphes non pondérés (pour les pondérés, voir l'algorithme de Dijkstra et les graphes probabilistes).
Définition
On dit qu’un graphe est orienté lorsque ses arêtes (appelées arcs) ou seulement une partie de celles-ci ne peuvent être parcourues que dans un sens.
Si un arc part du sommet \(A\) pour arriver à \(B,\) on dit que \(A\) est l’origine de l’arc et \(B\) est son extrémité.
L’origine et l’extrémité d’un arc permettent de le nommer (exemple : \((A,B)\)).
Représentation
Les arcs sont représentés par des flèches. Si dans un graphe orienté une arête peut être parcourue dans les deux sens, il est fréquent de tracer deux flèches, du moins lorsque les arcs sont peu nombreux. Toutefois les problèmes concrets peuvent nécessiter des graphes très complexes et les flèches doubles évitent alors d’amplifier la confusion.
Exemple ci-dessous entre \(A\) et \(C\) :
Un arc peut partir d’un sommet et y revenir. On parle alors de boucle, comme ici en \(B\) :
Chemins
Un chemin est une suite d’arcs consécutifs (qui s’enchaînent comme des chenilles processionnaires, si ça vous parle). Le nombre d’arcs est la longueur du chemin.
Exemple d’un chemin de longueur 3 ci-dessous en rouge \((C-A-B-B)\) :
Dans le cas des graphes non orientés, on parle de chaîne et si elle est fermée il s’agit d’un cycle. Ici, un chemin fermé est un circuit.
| Non orientés | Orientés |
| Arête | Arc |
| Chaîne | Chemin |
| Cycle | Circuit |
Les notions d'adjacence, de boucle et de degré sont communes aux deux types de graphes.
Matrice associée
Voir l’exemple 2 de la page sur les graphes et matrices et, si vous avez un niveau un peu plus avancé, les classes de connexité. Voir aussi les exercices sur graphes représentatifs de réseaux sociaux.
Exercice
On considère le graphe orienté suivant :
- Déterminer un chemin de longueur 3 reliant \(A\) à \(I.\)
- Déterminer un chemin de longueur 4 reliant \(A\) à \(I.\)
- Déterminer un chemin de longueur 5 reliant \(A\) à \(I.\)
- Déterminer un chemin de longueur 7 reliant \(A\) à \(I.\)
- Déterminer un circuit dont le sommet de départ et d’arrivée est \(A.\)
Corrigé indicatif
1- \(A-D-F-I\)
2- \(A-C-E-G-I\)
3- \(A-D-F-E-G-I\)
4- \(A-H-G-B-C-E-G-I\)
5- \(A-D-F-I-G-B-A\)
