Graphe orienté

Dans la théorie des graphes, un graphe orienté $G=(V,A)$ est un couple formé de $V$ un ensemble, appelé ensemble de nœuds et $A$ un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche.

Un graphe orienté $G=(V,A)$.
(Figure 1)

Définitions

• Étant donné un arc $(x,y)$, on dit que $x$ est l'origine (ou la source ou le départ ou le début) de $(x,y)$ et que $y$ est la cible (ou l'arrivée ou la fin) de $(x,y)$.
• Le demi-degré extérieur (degré sortant) d'un nœud, noté $d^{+}(x)$, est le nombre d'arcs ayant ce nœud pour origine.
• Le demi-degré intérieur (degré entrant) d'un nœud, noté $d^{-}(x)$, est le nombre d'arcs ayant ce nœud pour cible.
• Chaque arc ayant une seule origine et une seule cible, le graphe comporte autant de degrés sortants que de degrés entrants : $\sum _{x\in V}d^{+}(x)=\sum _{x\in V}d^{-}(x)$.
• $x_{1}x_{2},x_{2}x_{3},\cdots ,x_{n-1}x_{n}$ est un chemin si et seulement si $\forall p\in \{1,2,\cdots ,n-1\},(x_{p},x_{p+1})$ est un arc ; on dit que le chemin est élémentaire si tous les $x_{i}$ sont distincts.
• le chemin $x_{1}x_{2},x_{2}x_{3},\cdots ,x_{n-1}x_{n}$ est un circuit si et seulement si $(x_{n},x_{1})$ est un arc. Ce qui est équivalent à dire que le nœud de début du chemin est également sa fin.
• le graphe $G'=(V',A')$ est un sous-graphe du graphe orienté $G=(V,A)$ si et seulement si $G$ contient $G'$. Plus précisément, $G'\subseteq G$ si et seulement si $V'\subseteq V$ et $A'\subseteq \{(x,y)\in A\mid x\in V'\wedge y\in V'\}$.

• Le graphe transposé $G^{T}$ d'un graphe orienté $G=(V,A)$ est obtenu en conservant tous les nœuds de $V$et en inversant tous les arcs de $A$. Autrement dit, $G^{T}=(V,A^{T})$ avec $A^{T}=\{(y,x)\mid (x,y)\in A\}$. On parle aussi de graphe inverse.
• Une chaîne est une séquence de noeuds $x_{1},x_{2},...$ telle que $(x_{i-1},x_{i})\in V{\text{ ou }}(x_{i},x_{i-1})\in V$.

Exemples relatifs aux figures 1 et 2

$G'$, un sous-graphe du graphe $G$.
(Figure 2)

• le graphe dessiné dans la figure 1 est défini par $V=\{1,2,3,4\}$ et par$A=\{(1,2),(1,3),(3,2),(3,4),(4,3)\}$.
• le degré sortant $d^{+}(1)=2$. Deux arcs ont pour origine le nœud $1$.
• le degré entrant $d^{-}(1)=0$. Aucun arc n'a pour cible le nœud $1$.
• $1,3,2$ est un chemin du graphe $G$ (puisque $(1,3)$ et $(3,2)$ appartiennent à $A$) .
• $3,4$ est un circuit du graphe $G$ (et c'est le seul circuit élémentaire si on l'identifie au circuit $(4,3)$), car les arcs $(3,4)$ et $(4,3)$ appartiennent à $A$.
• $4,3,1,2,3$ est une chaîne de $G$.
• $G'=(\{1,2,3\},\{(1,3),(3,2)\})$ est un sous-graphe de $G$.
• $G^{T}=(\{1,2,3,4\},\{(2,1),(3,1),(2,3),(4,3),(3,4)\})$ est le transposé de $G$.

Modélisation par graphes orientés

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.

Bibliographie

• Claude Berge, Théorie des graphes et ses applications, Paris, Dunod, 1958, 275 p. (OCLC 780360).

Articles connexes

• Lexique de la théorie des graphes
• Graphe non orienté
• Automate fini
• Rang cyclique