Graphe orienté

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Exemple de 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) — notés respectivement xy et yx — 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.

Remarquons que dans un graphe non orienté G=(V,E), les arêtes remplacent les arcs et sont des paires de sommets (par exemple, si x et y sont des sommets, la paire {x, y}, notée xy, peut être une arête du graphe G).

  • Une suite (x, y, z... ) est dite chaîne si chaque paire (x y), (y z), (z...) est une arête, et un cycle si le premier et le dernier sommet sont identiques. Ces notions débouchent sur la connexité simple.

Les graphes étudiés en théorie des graphes sont en général des graphes simples, sans arêtes/arcs multiples (par opposition aux multigraphes) et souvent sans boucles.

Applications[modifier | modifier le code]

Les graphes orientés modélisent entre autres

  • les système routiers possédant des sens uniques, les systèmes de transport dissymétriques...
  • les graphes d'état mêlant transitions réversibles et irréversibles (exemple : les automates à états finis).

Annexes[modifier | modifier le code]

Sur les autres projets Wikimedia :

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]