Les graphes orientés

Les graphes orientés sont enseignés en terminale ES spé math et dans plusieurs cursus du supérieur. 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 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 les pages algorithme de Dijkstra et 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 celle-ci est fermée il s’agit d’un cycle. Ici, un chemin fermé est un circuit.

Matrice associée

Voir l’exemple 2 de la page graphes et matrices.

Exercice 1

On considère le graphe orienté suivant :

1. Déterminer un chemin de longueur 3 reliant A à I.
   
2. Déterminer un chemin de longueur 4 reliant A à I.
   
3. Déterminer un chemin de longueur 5 reliant A à I.
   
4. Déterminer un chemin de longueur 7 reliant A à I.
   
5. 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