Ориентированный ациклический граф

Файл:Directed acyclic graph.png

Ориентированный ациклический граф (направленный ациклический граф, DAG от Шаблон:Lang-en) — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).

Направленные ациклические графы широко используются в приложениях: в компиляторах, в искусственном интеллекте (для представления Шаблон:Iw), в статистике и машинном обучении (для представления байесовской сети доверия).

См. также

• Топологическая сортировка

Ссылки

• Weisstein, Eric W. Acyclic Digraph / Wolfram MathWorld Шаблон:Ref-en
• Directed Acyclic Graphs (DAGs) Шаблон:Ref-en