Глоссарий и правила игры

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

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

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

Определение 19.2. Ориентированный путь (directed path) в орграфе есть список вершин, в котором имеет­ся (ориентированное) ребро орграфа, соединяющее каждую вершину списка со следующим элементом это­го списка. Мы говорим, что вершина t достижима (reachable) из вершины s, если существует ориентиро­ванный путь из s в t.

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

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

В то время как подобные примеры подчеркивают различия, важно иметь в виду, что то, что человек счи­тает трудной задачей, может совпадать, а может и не совпадать с тем, что трудной задачей считает програм-

РИСУНОК 19.3. СЕТЧАТЫЙ ОРГРАФ

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

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

В этих представлениях не существует различий меж­ду неориентированными графами и ориентированными графами с петлей в каждой вершине и двумя ориенти­рованными ребрами для каждого ребра, соединяющего разные вершины неориентированного графа (по одно­му в каждом направлении). Следовательно, можно ис­пользовать алгоритмы, которые мы разрабатываем в этой главе для орграфов, для обработки неориентирован­ных графов, естественно, при соответствующей интер­претации результатов. Наряду с этим, мы используем программы, которые рассматривали в главе 17, в каче­стве основы для программ обработки орграфов: програм­мы 17.7-17.9, реализующие классы DenseGRAPH и SparseMultiGRAPH, строят орграфы, когда конструктор во втором аргументе получает значение true.

Полустепень захода (indegree) вершины орграфа есть число ориентированных ребер, которые ведут в эту вер­шину. Полустепень исхода (outdegree) вершины орграфа есть число ориентированных ребер, которые исходят из этой вершины. Ни одна из вершин орграфа не достижи­ма из вершины с полустепенью исхода 0, эта вершина получила название сток (sink); вершина с полустепенью захода 0 получила название исток (source), она не дости­жима ни из одной другой вершины орграфа. Орграфы, в которых допускается существование петель и в кото­рых каждая вершина обладает полустепенью исхода, равной 1, называется картой (тар) (отображение само­го на себя множества целых чисел в диапазоне от 0 до К- 1). Мы легко можем подсчитать полустепени захода и исхода для каждой вершины и найти стоки и исходы за линейное время и с использованием пространства па­мяти, пропорционального V; при это применяются век­торы, индексированные именами вершин.

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

РИСУНОК 19.4. ПРЕДСТАВЛЕНИЯ ОРГРАФА

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

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

В случае представления графа в виде матрицы смеж­ности мы могли бы вычислить его обращение, скопиро­вав матрицу и выполнив ее транспонирование (меняя местами строки и столбцы). Если мы знаем, что граф в дальнейшем не будет изменяться, мы фактически можем использовать его обращение без каких-либо дополни­тельных вычислении, путем простой перестановки вер­шин в ссылках (references) на соответствующие ребра, когда мы ссылаемся на обращение. Например, ребру s-t орграфа G соответствует значение 1 элемента adj[s][t]. Таким образом, если бы мы вычислили обращение R орграфа G, он содержал бы 1 в элементе adj[t][s]. Од­нако нет необходимости делать это, если мы построим свою реализацию на основе функции проверки ребра edge(s, t), поскольку для переключения на работу с об­ращением достаточно поменять такую ссылку на edge(t, s). Эта возможность может показаться очевидной, но ею часто пренебрегают. Что касается представления орграфа в виде списков смежных вершин, то это совер­шенно другая структура данных, и на ее построение, как показывает программа 19.1, тратится время, пропорци­ональное числу ребер орграфа.

Программа 19.1. Обращение орграфа_____________

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

template < class inGraph, class outGraph> void reverse(const inGraph & G,

outGraph & R) { for (int v = 0; v < G.V(); v++)

{typename inGraph:: adjIterator A(G, v); for (int w = A.beg();! A.end();

w = A.nxt()) R.insert(Edge(w, v)); } }

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

РИСУНОК 19.5. ОБРАЩЕНИЕ ОРГРАФА

Изменение направлений ребер орграфа на обратные соответ­ствует транспонированию матрицы смежности, однако оно требует переделки списков смежных вершин (см. рис. 19.1 и 19.4).

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

мы будем представлять ребро s-t узлом t в списке смежных вершин вершины s (установ­лено такое значение разряда направления, которое указывает, что движение вдоль реб­ра в направлении от s в t является обратным обходом ребра) и узлом s в списке смеж­ных вершин вершины t (установлено такое значение разряда направления, которое указывает, что движение вдоль ребра в направлении от t в s представляет собой прямой обход ребра). Подобное представление поддерживает алгоритмы, которые выполняют обходы ребра орграфа в обоих направлениях. Вообще говоря, в подобных случаях удоб­но включать указатели, соединяющие оба представления каждого узла. Мы отложим под­робное исследование такого представления до главы 22, в которой оно играет существен­ную роль.

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

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

Определение 19.3. Ориентированный ациклический граф (directed acyclic graph), или граф DAG, — это орграф, не содержащий направленных циклов.

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

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

Определение 19.4. Орграф называется сильно связ­ным (strongly connected), если каждая его вершина достижима из любой другой вершины.

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

Прилагательное сильно указывает на то, что каждая пара вершин связана более сильным отношением, чем достижимость. Мы говорим, что пара вершин s и t

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

любого графа сильно связана {strongly connected) или что эти вершины являются взаимно достижимыми {mutually reachable), если существует ориентированный путь из s в t и ориентированный путь из t в s. (Из того факта, что в соответствии с нашим соглашением каждая вершина достижима из самой себя, следует, что каждая вершина сильно связана сама с собой.) Орграф сильно связан тогда и только тогда, когда все пары вершин сильно связаны. Определяющей характеристикой сильно связ­ных орграфов является свойство, которое в случае связ­ных неориентированных графов мы воспринимаем как само собой разумеющееся: если существует путь из s в t, то существует путь из t в s. В случае неориентирован­ных графов нам этот факт известен, поскольку один и тот же путь, пройденный в обратном направлении, от­вечает всем требованиям определения; в случае орграфа это уже будет другой путь.

По-другому о том факте, что пара вершин сильно связана, можно сказать следующим образом: они лежат на некотором ориентированном циклическом пути. На­помним, что мы используем термин циклический путь (cyclic path) вместо термина цикл (cycle), дабы показать, что путь не обязательно должен быть простым. Напри­мер, на рис. 19.1 вершины 5 и 6 сильно связаны, по­скольку вершина 6 достижима из вершины 5 через пря­мой путь 5-4-2-0-6, а 5 достижима из 6 по ориентированному пути 6-4-3-5. Из существования этих путей следует, что вершины 5 и 6 лежат на ориентиро­ванном циклическом пути 5-4-2-0-6-4-3-5, но они не лежат в каком-то (простом) ориентированном цикле.

РИСУНОК 19.7. ТЕРМИНОЛОГИЯ ОРГРАФОВ

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

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

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

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

РИСУНОК 19.8. СИЛЬНЫЕ КОМПОНЕНТЫ И ЯДРО DAG

Рассматриваемый орграф (вверху) состоит из четырех сильных компо­нент, как это следует из массива id (в центре), индексированного именами вершин (в качестве индексов взяты произвольные целые числа). Компонен­та 0 содержит вершины 9, 10, 11 и 12; компонента 1 состоит из един­ственной вершины 1; компонента 2 содержит вершины 0, 2, 3, 4, 5 и 6, а компонента 3 состоит из вершин 7 и 8. Если мы начертим граф, определяе­мый ребрами, соединяющими различ­ные компоненты, то получим DAG (внизу).

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

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

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

Достижимость. Мы говорим, что вершина t орграфа достижима из вершины s, если существует ориентированный путь из s в t Как правило, мы избегаем употреблять тер­мин достижимый (reachable), когда имеем дело с неориентированными графами, хотя мо­жем считать его эквивалентным понятию connected (связный), поскольку идея достижимо­сти одной вершины из другой имеет определенный практический смысл в некоторых неориентированных графах (в частности, в графах, служащих представлением лабирин­тов).

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

Мы хотим обеспечить поддержку операции АТД орграфа, которые принимают в ка­честве аргументов две вершины s и t и позволяют нам проверить:

■ достижима ли t из s;

■ существует ли сильная связность вершин s и t (взаимная достижимость).

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

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