Направленные ациклические графы и топологическое упорядочение

Если ненаправленный граф не содержит циклов, то его структура чрезвычайно проста: каждая из его компонент связности представляет собой дерево. Однако направленный граф может и не иметь (направленных) циклов, обладая при этом довольно богатой структурой.
Например, такие графы могут иметь большое коли- чество ребер: если начать с множества узлов {1,2,...,;?} и включать ребро (i,j) для

** .

всех i < jy то полученный направленный граф состоит из ребер, но не содержит циклов.

Если направленный граф не содержит циклов, он называется (вполне естествен- но) направленным ациклическим графом, или сокращенно DAG (Directed Acyclic Graph). Пример направленного ациклического графа изображен на рис. 3.7, а, хотя чтобы убедиться в том, что он не содержит направленных циклов, придется немного потрудиться.


В топологически упорядоченном графе все ребра указывают слева направо

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Направленные ациклические графы и топологическое упорядочение:

  1. IV. 1. 2. Графы как средство описания систем.
  2. ПСИХОЛОГИЯ ТОПОЛОГИЧЕСКАЯ
  3. Направленность
  4. § 6. Направленность личности
  5. НАПРАВЛЕННОСТЬ ЛИЧНОСТИ
  6. ПОВЕДЕНЧЕСКОЕ НАПРАВЛЕНИЕ 1.
  7. НАПРАВЛЕНИЕ СПРАШИВАНИЯ
  8. 2.1. Направления объективного подхода
  9. Глава 1 ПСИХОДИНАМИЧЕСКОЕ НАПРАВЛЕНИЕ
  10. Глава 3 КОГНИТИВНОЕ НАПРАВЛЕНИЕ
  11. НАПРАВЛЕННОСТЬ ЛИЧНОСТИ
  12. ЛИЧНОСТЬ: НАПРАВЛЕННОСТЬ
  13. Б. Классификация гражданских договоров по признаку направленности
  14. Профессиональная направленность юриста
  15. 2.2.3. Психологическое направление
  16. Сущность и значение профессиональной направленности.
  17. § 9. Страховая направленность
  18. 5.3.1. Недостаток направленного воображения
  19. А. Общая характеристика признака направленности
  20. § 7. Направленность на замену лица в обязательстве