Fiche de cours
Vocabulaire des graphes orientés
On considère dans la suite le graphe orienté suivant :
Vocabulaire
Un graphe orienté est un graphe dans lequel chaque arête a un sens.
Une arête s'appelle alors un arc.
Une boucle est un arc pour lequel l'événement de départ et l'événement d'arrivée sont identiques : on part de l'événement et on revient sur lui même.
Un chemin est une chaîne formée d'arcs, en respectant le sens des flèches, comme par exemple $ABED$. Un chemin peut être fermé, comme par exemple $ADCA$.
Un circuit est un chemin fermé pour lequel chaque arc est utilisé exactement une fois : on ne passe pas deux fois au même endroit et tous les arcs sont différents.
Matrice associée
On peut également représenter le graphe sous forme d'une matrice.
On voyage des lignes vers les colonnes et on indique par un 1 si il existe un arc liant les deux sommets et par un