![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 19. Орграфы и ориентированные ациклические графы
Свойство 19.19. Мы можем поддерживать постоянное время запроса для транзитивного замыкания любого графа, в базовом DAG которого содержится менее 3√ V вершин, при затратах на предварительную обработку пространства памяти, пропорционального V, и времени, пропорционального Е + V. Доказательство: Установим неравенство v < 3 √ у в свойстве 19.18 и примем во внимание, что х < v2. ■ Мы можем рассматривать другие вариации этих границ. Например, если мы хотим использовать пространство, пропорциональное Е, мы можем достичь тех же временных границ, когда в базовом DAG содержатся до 3 √ E вершин. Более того, эти временные границы консервативны, поскольку они предполагают, что базовый DAG насыщен поперечными ребрами, — разумеется, это совсем не обязательно. Главный ограниченный фактор применимости этого метода — это размер базового DAG. Чем больше рассматриваемый нами орграф приближается по своим характеристикам к графу DAG (чем больше его базовый DAG), тем с большими трудностями приходится сталкиваться при вычислении его транзитивного замыкания. Обратите внимание на тот факт, что мы (естественно) не нарушили нижней границы, устанавливаемой по свойству 19.9, поскольку рассматриваемый алгоритм выполняется для насыщенных DAG за время, пропорциональное К3, однако мы существенно расширили класс графов, для которых можно избежать условий функционирования для худшего случая. В самом деле, построение модели случайного орграфа, генерирующей орграфы, на которых рассматриваемый алгоритм показывает низкое быстродействие, - задача не из легких (см. упражнение 19.142). В таблицу 19.2 сведены результаты эмпирических исследований; она показывает, что случайные орграфы обладают небольшими базовыми графами даже для графов со средней насыщенностью и моделей с серьезными ограничениями на расположение ребер. И хотя в худшем случае нет никаких гарантий, на практике мы можем рассчитывать на получение орграфов с малыми базовыми DAG. Когда в нашем распоряжении имеются такие орграфы, мы можем надеяться, что получим эффективную реализацию АТД абстрактно-транзитивного замыкания. Таблица 19.2. Свойства случайных орграфов___________________________________________ В данной таблице показано число вершин и ребер в базовых DAG случайных орграфов, построенных на базе двух различных моделей (ориентированные версии моделей из таблицы 18.1). В обоих случаях базовый граф DAG уменьшается (будучи разреженным) по мере возрастания насыщенности.
Часть 5. Алгоритмы на графах Обозначения: v - число вершин в базовом DAG е - число ребер в базовом DAG
• 19.138. Разработайте версию реализации абстрактного транзитивного замыкания для орграфов, основанных на использовании представлений разреженных графов для базового DAG. Основная ваша задача состоит в устранении дубликатов из списка без излишних затрат времени или пространства памяти (см. упражнение 19.65). > 19.139. Покажите базовый DAG, вычисленный с помощью программы 19.13, и его транзитивное замыкание для орграфа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4. о 19.140. Преобразуйте реализацию абстрактно-транзитивного замыкания, основанную на вычислении сильных компонент (программа 19.13) в эффективную программу, которая вычисляет матрицы смежности транзитивного замыкания орграфа, представленного в виде матрицы смежности, используя для этой цели алгоритм Габова для вычисления сильных компонент и усовершенствованный алгоритм Уоршалла для вычисления транзитивного замыкания графа DAG. 19.141. Выполните эмпирические исследования с целью оценки ожидаемых размеров базовых DAG для различных типов орграфов (см. упражнения 19.11-19.18). •• 19.142. Разработайте модель случайных орграфов, которая генерирует орграфы, имеющие большие базовые DAG. Ваш генератор должен генерировать ребра по одному за раз, но он не должен использовать какие-либо свойства полученного графа. 19.143. разработайте абстрактного транзитивного замыкания орграфа путем выявления сильных компонент и построения базового DAG с последующими утвердительными ответами на запросы о достижимости, если заданные две вершины находятся в одной и той же сильной компоненте, и выполнением в противном случае поиска в глубину в DAG с тем, чтобы определить их достижимость.
|