Dans ce paragraphe nous donnons quelques définitions sur les graphes orientés et quelques exemples, nous nous limitons ici aux définitions les plus utiles de façon à passer très vite aux algorithmes.
Un arc 
a pour origine le sommet 
et pour extrémité le sommet 
. On note
Dans la suite on suppose que tous les graphes considérés sont
finis, ainsi 
et par conséquent 
sont des ensembles finis. On
dit que le sommet est un successeur de si 
, est alors un prédécesseur de .
L'origine d'un chemin 
, notée 
est celle de son
premier arc 
et son extrémité, notée 
est
celle de son dernier arc 
, la longueur du chemin est
égale au nombre d'arcs qui le composent, c'est-à-dire 
. Un
chemin tel que 
est appelé un circuit.
Les sommets d'un tel graphe sont les suites de longueur 
formées
de symboles 
ou 
, un arc joint la suite à la suite 
si
où et sont des symboles ( ou
) et où 
est une suite quelconque de 
symboles.
Figure: Le graphe de De Bruijn pour 
Les sommets sont les nombres 
, un arc joint à
si divise .
Figure: Le graphe des diviseurs, 