Graphe orienté

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques image illustrant l’informatique théorique
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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) peuvent être des arcs du graphe G : dans ce cas, ils sont notés respectivement xy et yx.

  • 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.
  • 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.

Mise en garde

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).

Applications[modifier | modifier le code]

Les graphes orientés modélisent entre autres

  • les systèmes 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]