Graphe orienté acyclique

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Graphe acyclique orienté)
Aller à : navigation, rechercher
Un exemple de graphe orienté acyclique

En théorie des graphes, une hiérarchie est un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), ou graphe orienté qui ne possède pas de circuit (ni simple ni élémentaire).

La notion formalise un outil traditionnel d’analyse, dont on trouve des exemples :

En informatique, la notion s'applique en particulier pour la représentation des termes avec partage, pour l'organisation des démonstrations en déduction naturelle ou pour la théorie des langages de l’orientation objet, en ce qui concerne la classification des types.


Remarque : un graphe non orienté acyclique est simplement un arbre s'il est connexe, une forêt, ou ensemble d'arbres sinon.

Propriétés[modifier | modifier le code]

  • On peut toujours trouver un sous-graphe couvrant d’une hiérarchie qui soit un arbre (resp. une forêt).
  • Dans une hiérarchie, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre. L'algorithme du tri topologique permet de numéroter les sommets d'une hiérarchie de manière compatible avec cet ordre (autrement dit, s'il existe un chemin de u à v dans le graphe, alors le numéro de u est inférieur à celui de v).
  • Cette numérotation facilite la représentation par niveaux. Pour la hiérarchie ci-dessus, les sommets (7, 5, 3) forment le niveau 1, (11, 8) formant le niveau 2, (2, 9, 10) le niveau 3. Un arc de 8 vers 11 introduirait 4 niveaux, imposés par le chemin (3, 8, 11, 2).
  • Le problème des plus courts chemins à partir d'une source peut être résolu en temps linéaire dans un tel graphe.
  • Il est possible de trouver une couverture par chemins minimale en temps polynomial, alors que c'est un problème NP-complet dans un graphe orienté quelconque.[réf. nécessaire]

Articles connexes[modifier | modifier le code]