Graphe orienté

graphe dont les noeuds sont reliés par des arcs.

Dans la théorie des graphes, un graphe orienté G=(E,A) est un couple formé de E un ensemble, appelé ensemble de nœuds et A une partie de E×E appelée 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=(E,A).
(Figure 1)

Définitions

modifier
  • É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 : ∑x∈Ed+(x)=∑x∈Ed−(x)=Card(A).
  • x1x2,x2x3,⋯,xn−1xn est un chemin si et seulement si ∀p∈{1,2,⋯,n−1},(xp,xp+1) est un arc ; on dit que le chemin est élémentaire si tous les xi sont distincts.
  • le chemin x1x2,x2x3,⋯,xn−1xn est un circuit si et seulement si xn=x1, autremnent écrit quand le nœud de début du chemin est également sa fin.
  • le graphe G′=(E′,A′) est un sous-graphe du graphe orienté G=(E,A) si et seulement si G contient G′. Plus précisément, G′⊆G si et seulement si E′⊆E et A′⊆{(x,y)∈A∣x∈E′∧y∈E′}.
  • Le graphe transposé GT d'un graphe orienté G=(E,A) est obtenu en conservant tous les nœuds de E et en inversant tous les arcs de A. Autrement dit, GT=(E,AT) avec AT={(y,x)∣(x,y)∈A}. On parle aussi de graphe inverse[1].
  • Une chaîne[2] est une séquence de noeuds x1,x2,... telle que (xi−1,xi)∈A ou (xi,xi−1)∈A[3].

Exemples relatifs aux figures 1 et 2

modifier
G′, un sous-graphe du graphe G.
(Figure 2)
  • le graphe dessiné dans la figure 1 est défini par E={1,2,3,4} et parA={(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.
  • 1,3,2 est un chemin de G.
  • G′=({1,2,3},{(1,3),(3,2)}) est un sous-graphe de G.
  • GT=({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

modifier

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
  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

modifier

Articles connexes

modifier

Sur les autres projets Wikimedia :