Graphe orienté

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
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 associé à un couple de nœuds selon une direction représentée par une flèche.

Définitions[modifier | modifier le code]

  • Étant donné un arc , on dit que est l'origine (ou la source) de et que est l'extrémité (ou la 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 aux figures 1 et 2[modifier | modifier le code]

, un sous-graphe du graphe .
(Figure 2)
  • le graphe dessiné dans la figure 1 est défini par et par.
  • le degré sortant . Deux arcs ont pour origine le nœud .
  • le degré entrant . Aucun arc n'a pour extrémité le nœud .
  • est un chemin du graphe (puisque et appartiennent à ) .
  • est un circuit du graphe (et c'est le seul si on l'identifie au circuit ), car les arcs et appartiennent à .
  • est un sous-graphe de .
  • est le transposé de .

Modélisation par graphes orientés[modifier | modifier le code]

Les graphes orientés sont des modèles pour 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 :