Graphe orienté

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

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.

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 $\mathrm{\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^{\prime }=(V^{\prime },A^{\prime })$ est un sous-graphe du graphe orienté $G=(V,A)$ si et seulement si $G$ contient $G^{\prime }$. Plus précisément, $G^{\prime }\subseteq G$ si et seulement si $V^{\prime }\subseteq V$ et $A^{\prime }\subseteq \{(x,y)\in A\mid x\in V^{\prime }\wedge y\in V^{\prime }\}$.

• 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^{\prime }$, 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^{\prime }=(\{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

• Modèle:Ouvrage.

Articles connexes

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