Часть 5. Алгоритмы на графах. лах от 0 до V— 1. Результатом, скорее всего, будет произвольный мультиграф с петлями

лах от 0 до V— 1. Результатом, скорее всего, будет произвольный мультиграф с петлями. Заданной парой может оказаться два идентичных числа (отсюда получаются петли); при этом одна и та же пара может повторяться многократно (отсюда получаются параллель­ные ребра). Программа 17.12 генерирует ребра до тех пор, пока не станет известно, что число ребер в графе достигло значения Е, при этом решение об удалении параллельных ребер остается за реализацией. Если параллельные ребра удалены, то число полученных при генерации ребер должно быть значительно больше, чем число ребер (Е), использо­ванных в насыщенных графах (см. упражнение 17.62); в силу отмеченных особенностей этот метод обычно используется для разреженных графов.

Программа 17.13. Генератор случайных графов (случайный граф)_____________________

Как и в программе 17.13, рассматриваемая функция генерирует пары случайных целых чисел в диапазоне от 0 до V-1 с тем, чтобы добавлять в граф произвольные ребра, однако она использует другую вероятностную модель, по условиям которой каждое возможное ребро появляется независимо от других с вероятностью р. Значение р вычисляется таким образом, чтобы ожидаемое число ребер (рV(V-1)/2) было равно Е. Число ребер в каждом конкретном графе, генерируемых этой программой, близко к Е, однако маловероятно, что оно будет в точности равно Е. Этот метод пригоден в основном применительно к насыщенным графам, поскольку время его выполнения пропорционально V².

Глава 17. Свойства и типы графов

k-соседний граф. Граф, изображенный в верхней ча­сти рис. 17.13, вычерчен по результатам простых измене­ний, внесенных в генератор графов со случайными реб­рами, в процессе которых мы случайным образом выбирали первую вершину v, затем также случайным об­разом выбирали следующую вершину из числа тех вер­шин, индексы которых попадали в диапазон, образован­ный некоторой постоянной к, с центром в v (циклический возврат от V— 1 до 0, когда вершины упо­рядочены в виде окружности, как показано на рис. 17.13). Генерация таких графов не представляет собой трудностей, они, безусловно, обладают свойством ло­кальности, которое не характерно для случайных гра­фов.

Эвклидов граф с близкими связями. Граф, показан­ный в нижней части рис. 17.13, вычерчен генератором, который выбирает на плоскости V точек со случайными координатами в диапазоне от 0 до 1, а затем генерирует ребра, соединяющие две точки, удаленные друг от дру­га на расстояние, не превышающее d. Если d невелико, то граф получается разреженным, если d большое, то граф насыщенный (см. упражнение 17.74). Такой граф моделирует типы графов, с которыми мы обычно стал­киваемся при работе с картами, электронными схемами или другими приложениями, в условиях которых верши­ны привязаны к определенным геометрическим точкам. Их нетрудно представить наглядно, они позволяют под­робно отобразить свойства алгоритмов и структурные свойства, которые обнаруживаются в приложениях по­добного рода.

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

Опять-таки, мы можем протестировать наши алгорит­мы на реальных графах. В условиях многих приложений

РИСУНОК 17.13. СЛУЧАЙНЫЕ ГРАФЫ С БЛИЗКИМИ СВЯЗЯМИ

Примеры, приводимые на этом рисунке, служат иллюстрацией двух моделей разреженных графов. Граф с близкими связями, изобра­женный в верхней части рисунка, содержит 33 вершины и 99 узлов, при этом каждое ребро может соединять заданную вершину с другой вершиной, индекс которой отличается от индекса заданной вершины не больше, чем на 10 (по модулю V). Эвклидов граф с близкими связями, показанный в нижней части рисунка, моделиру­ет типы графов, которые мы можем найти в приложениях, в которых вершины привязаны к конкретным геометрическим точкам. Вершины изображены как случайные точки на плоско­сти; ребра соединяют любую пару вершин, расстояние между которыми не превышает d. Этот граф относится к категории разреженных (177 вершин и 1001 ребер); варьируя значения d, мы можем построить граф любой степени насыщенности.

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

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

Граф транзакций. На рис. 17.14 показан всего лишь небольшой фрагмент графа, который мы можем обна­ружить в компьютерах телефонной компании. В этом графе каждому телефонному номеру определяется соб­ственная вершина, а каждое ребро, соединяющее пару i и j, наделено свойством, согласно которому i произ­водит телефонный звонок j в течение некоторого фик­сированного промежутка времени. Это множество ре­бер представляет собой мультиграф огромных размеров. Он, естественно, разрежен, поскольку каж­дый абонент охватывает своими звонками всего лишь мизерную часть установленных телефонов. Этот граф является представительным для многих приложений. Например, кредитная карточка финансового учрежде­ния и запись в счете торгового агента могут содержать информацию аналогичного характера.

Программа 17.14. Построение графа из пар символов

Данная реализация функции scan из программы 17.4 использует таблицу символов для построения графа путем считывания пар символов из стандартного ввода. Функция index АТД таблицы символов ставит некоторое целое число в соответствие каждому символу: если поиск в таблице размера N закончится неудачно, она добавляет в таблицу символ с привязанным к нему целым числом N+1; если поиск завершится успешно, она просто возвращает целое число, которое ранее было ассоциировано с заданным символом. Любой из методов построения таблиц символов, рассмотренных в

РИСУНОК 17.14. ГРАФ ТРАНЗАКЦИИ

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

Глава 17. Свойства и типы графов

части 4, может быть приспособлен для решения этой задачи (см., например, программу 17.15).

#include " ST.cc" template < class Graph> void IO< Graph>:: scan(Graph & G) { string v, w; ST st; while (cin» v» w)

G.insert(Edge(st.index(v), st.index(w))); }

Граф вызовов функций. Мы можем поставить граф в соответствие любой компьютер­ной программе, отождествляя функции с вершинами графа, при этом ребро соединяет вершину X с вершиной Y всякий раз, когда функция X вызывает функцию Y. Мы можем снабдить программу средствами построения таких графов (или заставить компилятор де­лать это). Для нас интерес представляют два абсолютно различных графа: статическая вер­сия, когда мы строим ребра во время компиляции в соответствии с вызовами функций, которые появляются в программном тексте каждой функции; и динамическая версия, когда мы строим ребра во время выполнения программы, т.е. когда эти вызовы факти­чески происходят. Мы используем статические графы вызовов функций при изучении структуры программы и динамические графы при изучении поведения программы. Как правило, такие графы принимают большие размеры и относятся к категории разрежен­ных.

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

Программа 17.15. Символьная индексация имен вершин________________________

Реализация индексации строковых ключей посредством таблицы символов (описание которой дано в пояснении к программе 17.14) завершает эту задачу добавлением поля index к каждому узлу TST-дерева (ternary search tree -дерево тернарного поиска) таблицы существования (см. программу 15.8). Индекс, ассоциированный с каждым ключом, хранится в поле индекса узла, соответствующего символу конца его строки.

Как обычно, мы используем символы ключа поиска для перемещения по TST-дереву сверху вниз. Когда мы достигнем конца ключа, мы при необходимости устанавливаем значение его индекса, а также устанавливаем значение приватного элемента данных val, которое возвращается вызывающему объекту после того, как все рекурсивные обращения к рассматриваемой функции возвратят соответствующие значения.

#include < string> class ST { int N, val; struct node { int v, d; node* 1, *m, *r;

node(int d): v(-l), d(d), 1(0), m(0), r(0) {}

};

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

typedef node* link; link head;

link indexR(link h, const string & s, int w) { int i =s[w];

if (h == 0) h = new node(i);

if (i == 0)

{

if (h-> v == -1) h-> v = N++; val = h-> v; return h;

}

if (i < h-> d) h-> l = indexR(h-> l, s, w); if (i == h-> d) h-> m = indexR(h-> m, s, w+1); if (i > h-> d) h-> r = indexR(h-> r, s, w); return h; } public:

ST(): head(0), N(0) { } int index(const string & key)

{ head = indexR(head, key, 0); return val; } };

В нескольких таких примерах вершины представляют собой естественные имена объектов, а ребра выступают в виде пары именованных объектов. Например, граф тран­закций может быть построен на базе последовательности пар телефонных номеров, а эв­клидов граф — на базе последовательности пар городов или населенных пунктов. Про­грамма 17.14 представляет собой реализацию функции scan из программы 17.14, которой мы можем воспользоваться для построения графов общей ситуации подобного рода. Для удобства клиентских программ она использует некоторое множество ребер в качестве определения графа и вычисляет множество имен вершин графа по мере того, как они появляются в ребрах. В частности, рассматриваемая программа считывает последователь­ность пар символов из стандартного ввода, использует таблицу символов для того, чтобы поставить в соответствие символам номера вершин в диапазоне от 0 до V - 1 (где V — число различных символов во вводе), и строит граф путем вставки ребер, как это имело место в программах 17.12 и 17.13. Мы можем приспособить реализацию, исполь­зующую таблицу символов, для поддержки средств, необходимых программе 17.14; про­грамма 17.15 представляет собой пример использования TST-деревьев (см. главу 14). Эти программы существенно упрощают задачу тестирования разрабатываемых алгоритмов на реальных графах, которые, по всей видимости, не допускают точного представления с помощью какой бы то ни было вероятностной модели.

Значение программы 17.15 велико еще потому, что она подтвердила наше предполо­жение, которое мы допускали во всех разрабатываемых нами программах и которое зак­лючается в том, что имена вершин являются целочисленными значениями в диапазоне от О до V— 1. Если в нашем распоряжении имеется граф с другим множеством имен вер­шин, то первым шагом в построении представления графа является выполнение програм­мы 17.15, отображающей имена вершин на целые числа в диапазоне от 0 до V— 1.

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

Глава 17. Свойства и типы графов

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

Граф со степенями разделения. Рассмотрим некоторую совокупность подмножеств из V элементов. Мы определя­ем граф таким образом: его вершина соответствует каждо­му элементу объединения подмножеств, а ребро между дву­мя вершинами проводится в том случае, если обе вершины встречаются в каком-то одном поднаборе (см. рис. 17.15). При желании этот граф может быть преобразован в муль­тиграф, в котором метки ребер именуют соответствующие подмножества. Говорят, что все элементы, инцидентные данному элементу v, отделены от вершины v одной степе­нью разделения {degree of separation). В противном случае все элементы, инцидентные какому-либо элементу, который отделен i степенями разделения от вершины v, (о которых еще не известно, сколькими степенями разделения они от­делены от вершины v, / степенями или меньшим числом степеней разделения), обладают i + 1 степенями разделения с вершиной v. Такая конструкция служила развлечением для многих людей, от математиков (числа Эрдеша (Erdos)) до деятелей киноискусства (отделение от Кевина Бэкона (Kevin Bacon)).

Интервальный граф. Рассмотрим совокупность V ин­тервалов на действительной оси (пары вещественных чи­сел). Мы определяем граф следующим образом: каждому интервалу ставится в соответствие вершина, ребра между вершинами проводятся в том случае, когда соответствую­щие интервалы пересекаются (имеют любое число общих точек).

РИСУНОК 17.15. ГРАФ СО СТЕПЕНЯМИ РАЗДЕЛЕНИЯ

Граф в нижней части рисунка определяется группами, показанными в верхней части рисунка, при этом каждому имени соответствует вершина, а ребра соединяют вершины с именами, попадающими в одну и ту же группу. Кратчайшие длины пути в рассматриваемом графе соответствуют степеням разделения. Например, Франк отдален на три степени разделения от Алисы и Боба.

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

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

На базе нескольких примеров, рассмотренных в данном разделе, мы приходим к заключению, что графы представля­ют собой сложные комбинаторные объекты, которые намно­го сложнее тех, что служат основой других алгоритмов, об­суждавшихся в главах 1-4. Во многих случаях графам, с которыми приходится иметь дело в приложениях, трудно или даже невозможно дать более-менее точную характеристику. Алгоритмы, которые хорошо показывают себя на случайных графах, часто не находят широкого применения ввиду того, что зачастую трудно убедиться в том, что случайные графы обладают теми же структурными характеристиками, что и графы, возникающие в приложениях. Обычный способ пре­одолеть это возражение предусматривает разработку алгорит­мов, которые хорошо работают в наихудших случаях. И если этот подход приносит успех в одних случаях, он не оправды­вает ожиданий в других (в силу своей консервативности).

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