Aller au contenu

Graphe orienté acyclique

Un article de Wikipédia, l'encyclopédie libre.
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 circuit. Un tel graphe peut être vu comme une hiérarchie.

Définition

[modifier | modifier le code]

Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit[1].

Arbre et tri topologique

[modifier | modifier le code]
  • On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. 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 partielle. L'algorithme du tri topologique permet de numéroter les sommets d'un graphe orienté acyclique 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 le graphe orienté acyclique 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).

Aspects algorithmiques

[modifier | modifier le code]

Utilisations

[modifier | modifier le code]

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.

Notes et références

[modifier | modifier le code]
  1. Sylvie Hamel, « Graphes orientés », sur Université de Montréal

Articles connexes

[modifier | modifier le code]