История комбинаторики и машинное представление графов

б)

        

Рис. 2.1: а) ориентированный граф и его матрица инциденций; б) неориентированный граф и его матрица инциденций.

ствующий  ребру , содержит 1 в строках, соответствующих и , и нули

в остальных  строках. Это проиллюстрировано  на рис. 2.1. С алгоритмической точки  зрения матрица инциденций является, вероятно, самым худшим способом представления графа, который только можно себе представить. Во-первых, он требует ячеек памяти, причем большинство этих ячеек вообще занято нулями. Неудобен также доступ к информации. Ответ на элементарные вопросы типа «существует ли дуга ?», «к каким вершинам ведут ребра из ?» требует в худшем случае перебора всех столбцов матрицы, а следовательно, m шагов.

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

Рис. 2.2: Матрицы смежности для графов на рис. 2.1. 

мы подразумеваем, что ребро неориентированного графа идет как от

к , так и от к , так что матрица смежности такого графа всегда является симметричной. Это проиллюстрировано на рис. 2.2.

   Основным  преимуществом матрицы смежности  является тот факт, что за один шаг  можно получить ответ на вопрос «существует  ли ребро из в ?». Недостатком же является тот факт, что независимо от числа ребер объем занятой памяти составляет . На практике это неудобство можно иногда уменьшить, храня целую строку (столбец) матрицы в одном машинном слове — это возможно для малых .

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

ладает или  не обладает нашим свойством). Предположим, что свойство удовлетворяет следующим трем условиям:

• (а) , если графы изоморфны;
• (б) для произвольного пустого графа для произвольного полного графа с достаточно большим числом вершин;
• (в) добавление ребра не нарушает свойства , т.е. для произвольных графов , таких что

   Примером  такого свойства является существование цикла (в графе, имеющем по крайней мере три вершины).

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

      Рис. 2.3: Списки рёбер, соответствующие графам на рис. 2.1. 

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

    • (г) для произвольных ориентированных графов ,

    Более экономным в отношении памяти (особенно в случае неплотных графов, когда гораздо меньше ) является метод представления графа с помощью списка пар, соответствующих его ребрам. Пара соответствует дуге , если граф ориентированный, и ребру в случае неориентированного графа (рис. 2.3). Очевидно, что объем памяти в этом случае составляет Неудобством является большое число шагов — порядка в худшем случае, — необходимое для получения множества вершин, к которым ведут ребра из данной вершины.

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

таких что (или в случае неориентированного графа). Точнее, каж

дый элемент  такого списка является записью , содержащей вершину и указатель на следующую запись в списке ( для последней

записи  в списке). Начало каждого списка хранится в таблице , точ

нее, является указателем на начало списка, содержащего вершины

из множества для неориентированного графа). Весь

такой список обычно неформально будем  обозначать , а цикл, вы

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

    

       

      Рис. 2.4: Списки инцидентности

, , соответствующие графам на рис. 2.1.

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

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

5. Поиск в глубину в графе

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

• (а) он позволяет алгоритму решения интересующей нас задачи легко «погрузиться» в этот метод и
• (б) каждое ребро графа анализируется не более одного раза (или, что существенно не меняет ситуации, число раз, ограниченное константой). Опишем теперь такой метод поиска в неориентированном графе, который стал одной из основных методик проектирования графовых алгоритмов. Этот метод называется поиском в глубину (англ. depth first search [66]) по причинам, которые, как мы надеемся, вскоре станут ясными.

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

и, начиная  с нее, продолжаем поиск. Если же не существует ни одной новой вершины, смежной с , то мы говорим, что вершина использована, возвращаемся в вершину, из которой мы попали в , и продолжаем процесс (если , то

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

 

   Поиск в глубину в произвольном, необязательно  связном графе проводится согласно следующему алгоритму:

     
 
 
 

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

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

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

   Отметим, что алгоритм поиска в глубину в произвольном графе можно легко модифицировать так, чтобы он вычислял связные компоненты этого графа. Зафиксируем этот факт:

   Следствие 2.2. Связные компоненты произвольного графа, представленного списками инцидентности, можно вычислить за время

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

 
 

 
 
 

Рис. 2.5: Нумерация вершин графа (в скобках), соответствующая очередности, в  которой они просматриваются  в процессае поиска в глубину.

 

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

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

6. Поиск в ширину в графе

     Теперь  рассмотрим несколько иной метод  поиска в графе, называемый поиском в ширину (англ.: breadth first search). Прежде чем описать его, отметим, что при поиске в глубину чем позднее будет посещена вершина, тем раньше она будет использована — точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины скапливаются в стеке. Поиск в ширину, грубо говоря, основывается на замене стека очередью. После такой модификации чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще непросмотренных соседей этой вершины. Вся процедура представлена ниже