Graphe orienté

type de graphe
Un graphe orienté .
(Figure 1)

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

DéfinitionsModifier

  • Étant donné un arc  , on dit que   est l'origine (ou la source) de   et que   est l'extrémité (ou la cible) 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 extrémité.
  • Chaque arc ayant une seule origine et une seule extrémité, 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.
  • 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 extrémité 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 :