Graphe orienté acyclique
- Graphe orienté acyclique
-
Un exemple de graphe orienté acyclique
En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG) est un graphe orienté qui ne possède pas de cycle.
La notion est usuelle dans plusieurs domaines de l’informatique, 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.
Pourtant, elle est en fait beaucoup plus générale, et exprime formellement un outil traditionnel d’analyse, dont on trouve des exemples dans tous les modèles par couches, tel que le Modèle OSI, le modèle des fonctions du langage, de Bühler (ou de Taber-Nida), ou la Pyramide des besoins de Maslow.
Remarque : un graphe non orienté acyclique est simplement une forêt, c'est-à-dire un ensemble d'arbres.
Propriétés
- On peut toujours trouver un sous-graphe couvrant d’un DAG qui est un arbre (plus précisément une forêt).
- Dans un graphe orienté acyclique, 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'un DAG 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).
- 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.
Articles connexes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe orienté acyclique de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe acyclique — Un graphe acyclique est un graphe ne contenant aucun cycle. Il y a deux notions différentes de graphes acycliques selon qu on considère des graphes orientés ou non orientés. Graphes orientés : voir l article détaillé, graphe orienté… … Wikipédia en Français
Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A … Wikipédia en Français
Graphe Acyclique Orienté — Un exemple de graphe acyclique orienté Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés. La notion est usuelle dans … Wikipédia en Français
Graphe acyclique oriente — Graphe acyclique orienté Un exemple de graphe acyclique orienté Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés.… … Wikipédia en Français
Graphe acyclique orienté — Un exemple de graphe acyclique orienté Dans la théorie des graphes, un graphe acyclique orienté (en anglais directed acyclic graph ou DAG) identifie un graphe qui ne possède pas de cycle, et dont les arcs sont orientés. La notion est usuelle dans … Wikipédia en Français
Graphe Acyclique — Un graphe acyclique est un graphe ne contenant aucun cycle. Ce terme concerne les graphes orientés puisque les graphes non orienté sans cycle sont les forêts (chaque composante connexe est un arbre). Afin de distinguer les cycles non orientés des … Wikipédia en Français
Acyclique — Graphe acyclique Un graphe acyclique est un graphe ne contenant aucun cycle. Ce terme concerne les graphes orientés puisque les graphes non orienté sans cycle sont les forêts (chaque composante connexe est un arbre). Afin de distinguer les cycles … Wikipédia en Français
Graphe sans cycle — Graphe acyclique Un graphe acyclique est un graphe ne contenant aucun cycle. Ce terme concerne les graphes orientés puisque les graphes non orienté sans cycle sont les forêts (chaque composante connexe est un arbre). Afin de distinguer les cycles … Wikipédia en Français
Graphe cycle — Ne doit pas être confondu avec Graphe des cycles ni Cycle (théorie des graphes). Graphe cycle C8 … Wikipédia en Français
Lexique (graphe) — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A … Wikipédia en Français
