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

Если орграф сам является DAG, то вычисления сильных компонент не дают никакой новой информации, а этот алгоритм тот же, что реализованный программой 19.9; одна­ко в орграфах общего вида, в которых имеются циклы, этот алгоритм, по-видимому, об­ладает значительно более высоким быстродействием, чем алгоритм Уоршалла или реше­ние на базе поиска в ширину. Например, из свойства 19.18 немедленно вытекает следующий результат.

Свойство 19.19. Мы можем поддерживать постоянное время запроса для транзитивного замыкания любого графа, в базовом DAG которого содержится менее 3√ V вершин, при затратах на предварительную обработку пространства памяти, пропорционального V, и времени, пропорционального Е + V.

Доказательство: Установим неравенство v < 3 √ у в свойстве 19.18 и примем во внима­ние, что х < v2. ■

Мы можем рассматривать другие вариации этих границ. Например, если мы хотим использовать пространство, пропорциональное Е, мы можем достичь тех же временных границ, когда в базовом DAG содержатся до 3 √ E вершин. Более того, эти временные границы консервативны, поскольку они предполагают, что базовый DAG насыщен по­перечными ребрами, — разумеется, это совсем не обязательно.

Главный ограниченный фактор применимости этого метода — это размер базового DAG. Чем больше рассматриваемый нами орграф приближается по своим характеристи­кам к графу DAG (чем больше его базовый DAG), тем с большими трудностями прихо­дится сталкиваться при вычислении его транзитивного замыкания. Обратите внимание на тот факт, что мы (естественно) не нарушили нижней границы, устанавливаемой по свой­ству 19.9, поскольку рассматриваемый алгоритм выполняется для насыщенных DAG за вре­мя, пропорциональное К³, однако мы существенно расширили класс графов, для которых можно избежать условий функционирования для худшего случая. В самом деле, построение модели случайного орграфа, генерирующей орграфы, на которых рассматриваемый алгоритм показывает низкое быстродействие, - задача не из легких (см. упражнение 19.142).

В таблицу 19.2 сведены результаты эмпирических исследований; она показывает, что случайные орграфы обладают небольшими базовыми графами даже для графов со сред­ней насыщенностью и моделей с серьезными ограничениями на расположение ребер. И хотя в худшем случае нет никаких гарантий, на практике мы можем рассчитывать на по­лучение орграфов с малыми базовыми DAG. Когда в нашем распоряжении имеются та­кие орграфы, мы можем надеяться, что получим эффективную реализацию АТД абстрак­тно-транзитивного замыкания.

Таблица 19.2. Свойства случайных орграфов___________________________________________

В данной таблице показано число вершин и ребер в базовых DAG случайных орграфов, построенных на базе двух различных моделей (ориентированные версии моделей из таблицы 18.1). В обоих случаях базовый граф DAG уменьшается (будучи разреженным) по мере возрастания насыщенности.

Часть 5. Алгоритмы на графах

v - число вершин в базовом DAG е - число ребер в базовом DAG

Упражнения