Graphe orienté : définition (Maths expertes)

Un graphe orienté est formé de sommets et d'arcs : un arc est une flèche allant d'un sommet (origine) vers un sommet (extrémité). Un arc dont l'origine et l'extrémité sont confondues est une boucle.

Un chemin est une suite de sommets telle que, pour deux sommets consécutifs, il existe un arc allant du premier au second. Sa longueur est le nombre d'arcs parcourus. Un chemin est fermé si son origine et son extrémité sont égales.