Алгоритм Демукрона

Алгоритм Демукрона — алгоритм решения задачи топологической сортировки, то есть упорядочения вершин графа по их уровням для бесконтурного ориентированного графа. Уровни вершин графа можно рассматривать как длины максимальных путей от входов до этих вершин.

Формулировка

Основная идея алгоритма Демукрона состоит в последовательном удалении из графа, начиная со входов, вершин и исходящих из них дуг[1].

Примечания
  1. Дискретная математика, 2006, с. 351.

Литература
  • Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.