Graphe orienté

Un graphe orienté G = ( V , A ) {\displaystyle G=(V,A)} .
(Figure 1)

Dans la théorie des graphes, un graphe orienté G = ( V , A ) {\displaystyle G=(V,A)} est un couple formé de V {\displaystyle V} un ensemble, appelé ensemble de nœuds et A {\displaystyle 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 ) {\displaystyle (x,y)} , on dit que x {\displaystyle x} est l'origine (ou la source ou le départ ou le début) de ( x , y ) {\displaystyle (x,y)} et que y {\displaystyle y} est la cible (ou l'arrivée ou la fin) de ( x , y ) {\displaystyle (x,y)} .
  • Le demi-degré extérieur (degré sortant) d'un nœud, noté d + ( x ) {\displaystyle 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 ) {\displaystyle 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 : ∑ x ∈ V d + ( x ) = ∑ x ∈ V d − ( x ) {\displaystyle \sum _{x\in V}d^{+}(x)=\sum _{x\in V}d^{-}(x)} .
  • x 1 x 2 , x 2 x 3 , ⋯ , x n − 1 x n {\displaystyle x_{1}x_{2},x_{2}x_{3},\cdots ,x_{n-1}x_{n}} est un chemin si et seulement si ∀ p ∈ { 1 , 2 , ⋯ , n − 1 } , ( x p , x p + 1 ) {\displaystyle \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 {\displaystyle x_{i}} sont distincts.
  • le chemin x 1 x 2 , x 2 x 3 , ⋯ , x n − 1 x n {\displaystyle 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 ) {\displaystyle (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 ′ ) {\displaystyle G'=(V',A')} est un sous-graphe du graphe orienté G = ( V , A ) {\displaystyle G=(V,A)} si et seulement si G {\displaystyle G} contient G ′ {\displaystyle G'} . Plus précisément, G ′ ⊆ G {\displaystyle G'\subseteq G} si et seulement si V ′ ⊆ V {\displaystyle V'\subseteq V} et A ′ ⊆ { ( x , y ) ∈ A ∣ x ∈ V ′ ∧ y ∈ V ′ } {\displaystyle A'\subseteq \{(x,y)\in A\mid x\in V'\wedge y\in V'\}} .
  • Le graphe transposé G T {\displaystyle G^{T}} d'un graphe orienté G = ( V , A ) {\displaystyle G=(V,A)} est obtenu en conservant tous les nœuds de V {\displaystyle V} et en inversant tous les arcs de A {\displaystyle A} . Autrement dit, G T = ( V , A T ) {\displaystyle G^{T}=(V,A^{T})} avec A T = { ( y , x ) ∣ ( x , y ) ∈ A } {\displaystyle A^{T}=\{(y,x)\mid (x,y)\in A\}} . On parle aussi de graphe inverse[1].
  • Une chaîne[2] est une séquence de noeuds x 1 , x 2 , . . . {\displaystyle x_{1},x_{2},...} telle que ( x i − 1 , x i ) ∈ V  ou  ( x i , x i − 1 ) ∈ V {\displaystyle (x_{i-1},x_{i})\in V{\text{ ou }}(x_{i},x_{i-1})\in V} [3].

Exemples relatifs aux figures 1 et 2

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

Notes et références

  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.
  2. ↑ Claude Berge, Espaces topologiques, fonctions mutivoques, Paris, Dunod, , p. 29
  3. ↑ Marc Lipson, Discrete mathematics, McGraw-Hill, (ISBN 978-0-07-161586-0), p. 203

Bibliographie

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

Articles connexes

Sur les autres projets Wikimedia :

  • Graphe orienté, sur Wikimedia Commons
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail des mathématiques