Graphes orientés

Un graphe orienté est un graphe dont les arêtes sont orientées, à savoir qu'il est possible de distinguer l'extrémité initiale d'une arête de son extrémité finale. Dans ce cas, on parlera d'arc plutôt que d'arête.

Définition 7.1   Un arc est un objet $a$ avec un sommet extrémité initiale (noté $T(a)$ pour l'anglais ``tail'') et un sommet extrémité finale (noté $H(a)$ pour l'anglais ``head'').

Les graphes orientés sont souvent nécessaires pour modéliser des routes. La raison est qu'il peut y avoir un chemin d'un point $A$ à un point $B$ mais pas de chemin de $B$ vers $A$. Cela peut être le cas de voies à sens unique ou de lignes aériennes. Un exemple de graphe orienté est présenté figure 7.1

Les graphes orientés sont souvent utilisés en informatique, car ils sont plus faciles à représenter dans la mémoire d'un ordinateur. En fait, un graphe non orienté est souvent représenté sous la forme d'un graphe orienté dans lequel chaque couple d'arcs représente une arête du graphe non orienté.

Figure: Un graphe orienté