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.
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 à un point
mais pas de chemin
de
vers
. 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é.