human
Veuillez expliquer ce qu'est un "graphe acyclique dirigé"
gpt
En mathématiques , en particulier en théorie des graphes et en informatique , un graphe acyclique orienté ( DAG ) est un graphe orienté sans cycles orientés . Autrement dit, il se compose de sommets et d'arêtes (également appelés arcs), chaque arête étant dirigée d'un sommet à l'autre, de sorte que suivre ces directions ne formera jamais de boucle fermée. Un graphe orienté est un DAG si et seulement s'il peut être ordonné topologiquement, en organisant les sommets selon un ordre linéaire cohérent avec toutes les directions des bords. Les DAG ont de nombreuses applications scientifiques et informatiques, allant de la biologie (évolution, arbres généalogiques, épidémiologie) aux sciences de l'information (réseaux de citations) en passant par l'informatique (ordonnancement).
Les graphes acycliques dirigés sont parfois appelés graphes dirigés acycliques ou digraphes acycliques.