Graphe orienté

type de graphe

Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble de nœuds et un ensemble d'arêtes alors nommées arcs, chaque arc étant associé à un couple de sommets alors nommés nœuds selon une direction représentée par une flèche.

Un graphe orienté .
(Figure 1)

DéfinitionsModifier

  • Étant donné un arc  , on dit que   est l'origine (ou la source ou le départ ou le début) de   et que   est la cible (ou l'arrivée ou la fin) 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 cible.
  • Chaque arc ayant une seule origine et une seule cible, le graphe comporte autant de degrés sortants que de degrés entrants :  .
  •   est un chemin si et seulement si   est un arc ; on dit que le chemin est élémentaire si tous les   sont distincts.
  • le chemin   est un circuit si et seulement si   est un arc. Ce qui est équivalent à dire que le nœud de début du chemin est également sa fin.
  • 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 2Modifier

 
 , 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 cible le nœud  .
  •   est un chemin du graphe   (puisque   et   appartiennent à  ) .
  •   est un circuit du graphe   (et c'est le seul circuit élémentaire 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ésModifier

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

  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.

BibliographieModifier

Articles connexesModifier

Sur les autres projets Wikimedia :