Глава 18. Поиск на графе. Ситуация, по-видимому, не такая безнадежная, как она описана выше, по одной про­стой причине: многие из рассматриваемых алгоритмов на графах оптимальны в

Ситуация, по-видимому, не такая безнадежная, как она описана выше, по одной про­стой причине: многие из рассматриваемых алгоритмов на графах оптимальны в худшем случае, так что прогнозирование производительности алгоритмов не представляет труд­ностей. Например, программа 18.7 обнаруживает мосты по результатам лишь одного ис­следования каждого ребра и каждой вершины. Это требует таких же затрат, как и пост­роение структуры данных графа, и мы можем с достаточной точностью предсказать, например, что удвоение числа ребер приводит к увеличению времени выполнения в два раза независимо от того, обработку каких типов графов мы выполняем.

Когда время выполнения алгоритма зависит от структуры входного графа, такого рода прогнозы делать намного труднее. Тем не менее, если возникает необходимость обработ­ки очень большого числа крупных графов, нам нужны эффективные алгоритмы по той же причине, по какой они требуются и в любой другой проблемной области, поэтому мы продолжим изучение основных свойств алгоритмов и приложений и будем стараться вы­явить те методы, которые обеспечивают наилучшую обработку графов, которые могут возникать на практике.

Чтобы проиллюстрировать некоторые из этих проблем, мы вернемся к изучению свой­ства связности графа, к задаче, которую анализировалась еще в главе 1 (!). Связность слу­чайных графов привлекала к себе внимание математиков в течение многих лет, этой теме посвящено множество пространных публикаций. Эта литература выходит за рамки насто­ящей книги, в то же время она представляет собой фон, который оправдывает исполь­зование этой задачи как основы для некоторых экспериментальных исследований, углуб­ляющих наше понимание базовых алгоритмов, которые мы используем, и типов графов, которые мы изучаем.

Например, наращивание графов за счет добавления случайных ребер во множество первоначально изолированных вершин (по существу, этот процесс реализуется програм­мой 19.12) представляет собой подробно исследованный процесс, который послужил ос­новой классической теории случайных графов. Хорошо известно, что по мере возраста­ния числа ребер, такой граф сливается, образуя одну гигантскую компоненту. Литература по случайным графам дает обширную информацию о природе этого процесса. Например,

Свойство 18.13. Если Е > z VlnV/2 + μ V(при положительном значении μ), то слу­чайный граф с V вершинами и Е ребрами состоит из одной связной компоненты и изо­лированных вершин, среднее число которых не превышает e^2μ , с вероятностью, прибли­жающейся к 1 при бесконечном возрастании V.

Доказательство: Этот факт был установлен в пионерской работе Эрдеша (Erdos) и Ре-ньи (Renyi) в 1960 г. Само доказательство выходит за рамки данной книги (см. раз­дел ссылок). ■

Таблица 18.1. Связность на примере двух моделей случайного графа___________________

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

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

на выбор ребер, которые выбираются из числа соединяющих каждую вершину с только одной из 10 указанных соседних вершин.

Обозначения:

С - число связных компонентов

L - размер наибольшей связной компонентой

Это свойство говорит о том, что мы вполне можем ожидать, что крупные неразрежен­ные случайные графы являются связными. Например, если V> 1000 и Е > 10V, то

μ > 10 - -(ln 1000)/2 > 6.5 и среднее число вершин, не содержащихся в гигантской компо­ненте, (почти наверняка) меньше, чем е^-13< 0.000003. Если вы генерируете миллион слу­чайных графов, в которые входят 1000 вершин с плотностью, превосходящей 10, можно получить несколько графов с одной изолированной вершиной, зато все остальные гра­фы будут связными.

На рис. 18.30 случайные графы сравниваются со случайными близкими графами, в которые мы включаем только ребра, соединяющие вершины с другими вершинами, ин­дексы которых различаются на некоторое небольшое постоянное значение. Модель близ­кого графа порождает графы, которые по своим характеристикам существенно отлича­ются от случайных графов. В конечном итоге мы получим крупную компоненту, но она появится внезапно, когда произойдет слияние двух крупных компонент.

Из таблицы 18.2 следует, что эти структурные различия между случайными графами и близкими графами сохраняются и тогда, когда V и Е находятся в пределах, представляю­щих практический интерес. Такие структурные различия, несомненно, могут отразиться на производительности разрабатываемых нами алгоритмов.

Таблица 18.2. Эмпирическое исследование алгоритмов поиска на графе__________________

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

Глава 18. Поиск на графе

РИСУНОК 18.30. СВЯЗНОСТЬ В СЛУЧАЙНЫХ ГРАФАХ

На этом рисунке показана эволюция двух типов случайных графов на 10 равных шагах в условиях, когда в общем случае в первоначально пустые графы добавляются 2Е ребер. Каждая диаграмма представляет собой гистограмму числа вершин в компонентах размером от 1 до V (слева направо). Мы отталкиваемся от ситуации, когда все вершины содержатся в компонентах размера 1 и закан­чиваем, когда практически все вершины входят в одну компоненту гигантских размеров. Диаграмма слева отображает стандартный случайный граф: гигантская компонента формируется быстро, а все другие компоненты малы. Диаграмма справа отображает случайный граф с близкими связями: компоненты различных размеров сохраняются в течение более длительного времени.

⇐ Предыдущая74757677787980818283Следующая ⇒