Graphe orienté

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Exemple de dessin d'un graphe orienté.

En théorie des graphes, un graphe orienté est un couple formé de un ensemble de sommets et un ensemble d'arcs, chaque arc étant un couple de sommets.

Définitions[modifier | modifier le code]

  • Étant donné un arc (x, y), on dit que x est l´origine de (x,y) et que y est l´extrémité de (x,y).
  • Le demi-degré extérieur (degré sortant) d'un sommet est le nombre d'arcs ayant ce sommet pour origine. Formellement, .
  • Le demi-degré intérieur (degré entrant) d'un sommet est le nombre d'arcs ayant ce sommet pour extrémité. Formellement, . On a .
  • Une suite (x, y, z... ) est dite un chemin si chaque paire (x y), (y z), (z...) est un arc, et un circuit si le premier et le dernier sommet de la suite 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 une chaîne si pour chaque paire (α,β) ∈{(x y), (y z), (z...), ...} on a que soit (α,β) est un arc, soit que (β,α) est un arc Cette suite est un cycle si, de plus, le premier et le dernier sommet de la suite sont identiques. Ces notions débouchent sur la connexité ou connexité simple.
  • Le graphe transposé d'un graphe orienté est obtenu en inversant toutes les arcs, plus précisément le graphe transposé d'un graphe (V,A) est le graphe (V,A') ou A' = {(y,x) | (x,y)∈A}. On parle aussi de graphe inverse[1].
  • Un sous-graphe d'un graphe est un graphe dont les sommets sont certains sommets de et les arcs certains arcs de ayant leurs origines et leurs extrémités parmi les sommets de . Plus précisément, on doit avoir et .

Exemples[modifier | modifier le code]

  • La figure représente le graphe .
  • Dans ce graphe est un chemin, est un circuit.
  • Le graphe transposé de ce graphe est .
  • Dans ce graphe est un sous-graphe.

Applications[modifier | modifier le code]

Les graphes orientés modélisent diverses situations.

  • 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).
  • Le flot de contrôle d'un programme.
  • Les réseaux de flot sont des graphes orientés dont les arcs sont étiquetés par des capacités.

Notes et références[modifier | modifier le code]

  1. Les deux termes sont utilisés, voir Olivier Carton, « Algorithmes sur les graphes » pour graphe transposé, et Jean-Charles Régin et Arnaud Malapert, « Théorie des graphes », pour graphe inverse.

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Sur les autres projets Wikimedia :