Алгоритм Демукрона
Алгоритм Демукрона — алгоритм решения задачи топологической сортировки, то есть упорядочения вершин графа по их уровням для бесконтурного ориентированного графа. Уровни вершин графа можно рассматривать как длины максимальных путей от входов до этих вершин.
Формулировка
Основная идея алгоритма Демукрона состоит в последовательном удалении из графа, начиная со входов, вершин и исходящих из них дуг[1].
Примечания
- ↑ Дискретная математика, 2006, с. 351.
Литература
- Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.
Для улучшения этой статьи желательно:
|