Graphe orienté

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un graphe orienté .
(Figure 1)

Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble de nœuds et un ensemble d'arcs, chaque arc étant un couple de nœuds.

Définitions[modifier | modifier le code]

  • Étant donné un arc , on dit que est l'origine "source" de et que est l'extrémité "cible" de .
  • Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.
  • Le demi-degré intérieur (degré entrant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour extrémité.
  • Chaque arc ayant une seule origine et une seule extrémité, le graphe comporte autant de degrés sortants que de degrés entrants: .
  • est un chemin si et seulement si est un arc.
  • le chemin est un circuit si et seulement si est un arc.
  • le graphe est un sous-graphe du graphe orienté si et seulement si contient . Plus précisément, si et seulement si et .
  • Le graphe transposé d'un graphe orienté est obtenu en conservant tous les nœuds de et en inversant tous les arcs de . Autrement dit, avec . On parle aussi de graphe inverse[1].

Exemples relatifs au figures 1 et 2[modifier | modifier le code]

, un sous-graphe du graphe .
(Figure 2)
  • le graphe s'écrit aussi
  • le degré sortant . Deux arcs partent du nœud .
  • le degré entrant . Aucun arc n'arrive au nœud .
  • est un chemin du graphe .
  • est un circuit du graphe .
  • est un sous-graphe de .
  • est le transposé de .

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 :