Graphe acyclique dirigé (dag)

Définition - Que signifie le graphe acyclique dirigé (DAG)?

En informatique et en mathématiques, un graphe acyclique dirigé (DAG) est un graphe orienté et sans cycles reliant les autres arêtes. Cela signifie qu'il est impossible de parcourir le graphe entier en commençant par un bord. Les arêtes du graphe orienté ne vont que dans un sens. Le graphe est un tri topologique, où chaque nœud est dans un certain ordre.

Definir Tech explique le graphique acyclique dirigé (DAG)

En théorie des graphes, un graphe est une série de sommets reliés par des arêtes. Dans un graphe orienté, les arêtes sont connectées de telle sorte que chaque arête ne va que dans un sens. Un graphe acyclique dirigé signifie que le graphe n'est pas cyclique ou qu'il est impossible de commencer à un point du graphe et de parcourir le graphe entier. Chaque arête est dirigée d'une arête antérieure vers une arête ultérieure. Ceci est également connu sous le nom de classement topologique d'un graphe.

Une feuille de calcul peut être représentée sous la forme d'un graphe acyclique dirigé, avec chaque cellule un sommet et une arête reliant une cellule lorsqu'une formule fait référence à une autre cellule. D'autres applications incluent la planification, la conception de circuits et les réseaux bayésiens.