graphe orienté

En théorie des graphes, un graphe orienté G = (V, A) est défini par la donnée d'un ensemble de sommets V et d'un ensemble d'arcs A, chaque arc étant un couple de sommets (par exemple, si x et y sont des sommets, les couples (x,y) et (y,x) peuvent être des arcs du graphe G).

• Une suite (x, y, z... ) est dite chemin si chaque paire (x y), (y z), (z...) est un arc, et un circuit si le premier et le dernier sommet sont identiques. Une boucle est un circuit d'un seul arc. Ces notions débouchent sur la connexité forte.