Виды графов и их свойства

Глоссарий

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

Определение 17.1. Граф (graph) -это некоторое множество вершин (vertex) и некоторое множество ребер (edge), соединяющих пары различных вершин (одну пару вершин может соединять максимум одно ребро).

Если граф состоит из V вершин, то мы будем помечать их числами от 0 до V-1. Основная причина выбора этой системы обозначений заключается в том, что она обеспечивает быстрый доступ к информации, соответствующей каждой вершине, путем индексирования векторов. В разделе 17.6 будет рассмотрена программа, которая использует таблицу символов для установления взаимно-однозначного соответствия V произвольных имен вершин с V целыми числами от 0 до V-1. Пользуясь этой программой, мы можем (для удобства обозначений) употреблять без потери общности индексы как имена вершин. Иногда мы будем предполагать, что множество вершин определено неявно, с помощью множества ребер, учитывая только те вершины, которые упомянуты хотя бы в одном ребре. Во избежание громоздких выражений наподобие " граф из 10 вершин со следующим набором ребер " , мы часто не будем указывать явно количество вершин, если оно понятно из контекста. Далее будем придерживаться соглашения: количество вершин в заданном графе всегда обозначается буквой V, а количество ребер -буквой E.

Мы примем определение 17.1 в качестве стандартного определения графа (мы уже сталкивались с ним в ), но учтите, что в нем использованы два технических упрощения. Во-первых, в нем запрещены одинаковые ребра (математики иногда называют такие ребра параллельными, а граф, который может содержать такие ребра -мультиграфом (multigraph)). Во-вторых, в нем запрещены ребра, соединяющие вершины с собой; такие ребра называются петлями (self-loop). Графы, в которых нет параллельных ребер или петель, иногда называют простыми графами (simple graph).

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

Лемма 17.1. Граф, состоящий из Vвершин, содержит не более V(V- 1)/2 ребер.

Доказательство. Общее количество возможных пар вершин равно V², из них V петель, а ребра между различными вершинами учитываются дважды, следовательно, максимальное количество ребер не превосходит значения (V2 -V)/2 = V(V-1)/2 . $$$\blacksquare$$$

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

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

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

Математики употребляют термины вершина (vertex) и узел (node) как эквивалентные, но мы будем обычно использовать термин вершина при изучении графов и термин узел при обсуждении представлений графов -например, структур данных в C++. Как правило, мы полагаем, что вершина может иметь имя и другую связанную с ней информацию. Аналогично, для соединений двух вершин математиками широко используются слова дуга (arc), ребро (edge) и связь (link), однако мы всегда будем употреблять термин ребро при изучении графов и термин ссылка при обсуждении структур данных в C++.

Если имеется ребро, соединяющее две вершины, будем говорить, что обе эти вершины смежны (adjacent) друг с другом, а ребро инцидентно (incident) этим вершинам. Степень (degree) вершины -это количество ребер, инцидентных этой вершине. Ребро, соединяющее вершины v и w, мы будем обозначать v-w, либо эквивалентной записью w-v.

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

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

(рис 17.1) Три различных представления одного и того же графа

Граф определяется его вершинами и ребрами, но не способом его графического изображения. Оба приведенных чертежа, а также список ребер (внизу) изображают один и тот же граф -при наличии информации, что рассматриваемый граф содержит 13 вершин, помеченных номерами от 0 до 12.

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

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

Если сосредоточиться только на связях, то метки вершин можно считать просто удобными обозначениями, а два графа считать одинаковыми, если они отличаются друг от друга только метками вершин. Два графа называются изоморфными (isomorphic), если можно поменять метки вершин в одном из них так, чтобы множество ребер этого графа стало эквивалентным множеству ребер другого графа. Определение изоморфизма двух графов представляет собой сложную вычислительную задачу (см. рис 17.2 и упражнение 17.5). Ее сложность объясняется тем, что существует V! способов обозначения вершин -слишком много, чтобы перепробовать все возможности.

(рис 17.2) Примеры изоморфизма графов

Два верхних графа изоморфны, поскольку можно переобозначить вершины таким образом, что оба множества ребер станут идентичными (чтобы сделать граф в центре таким же, как и верхний граф, нужно поменять 10 на 4, 7 на 3, 2 на 5, 3 на 1, 12 на 0, 5 на 2, 9 на 11, 0 на 12, 11 на 9, 1 на 7 и 4 на 10). Нижний граф не изоморфен двум другим, поскольку не существует такого способа переименования его вершин, чтобы множество его ребер стало идентично множествам ребер двух первых графов.

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

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

Определение 17.2. Путь (path) в графе -это последовательность вершин, в которой каждая следующая вершина (после первой), является смежной с предыдущей вершиной на этом пути. Простой путь (simple path) -это путь, все вершины и ребра, составляющие, различны. Циклом (cycle) называется путь, у которого первая и последняя вершина одна и та же.

Иногда используется термин циклический путь (cyclic path) -для обозначения пути, у которого совпадают первая и последняя вершина (но который в других отношениях не обязательно является простым); а термин контур (tour) употребляется для циклического пути, который включает каждую вершину. Путь можно определить и как последовательность ребер, которая соединяет соседние вершины. Мы подчеркиваем это в наших обозначениях, соединяя имена вершин в пути так же, как и в обозначениях ребер. Например, на рис 17.1 имеются простые пути 3-4-6-0-2 и 9-11-12 и циклы 0-6-4-3-5-0 и 5-4-3-5. Длина (length) пути или цикла определяется как количество составляющих их ребер.

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

Два простых пути называются непересекающимися (disjoint), если они не содержат общих вершин, кроме, возможно, концевых. Это условие несколько слабее, чем требование полного отсутствия в обоих путях общих вершин, и оно более полезно, поскольку в этом случае мы можем соединить простые непересекающиеся пути из s в t и из t в u и получить простой непересекающийся путь из s в u, если вершины s и u различны (и получить цикл, если s и u совпадают). Иногда используется термин непересекающиеся по вершинам (vertex disjoint), чтобы отличить эту ситуацию от более сильного условия непе-ресекающихся по ребрам (edge disjoint) путей, когда пути не должны иметь общих ребер.

Определение 17.3. Граф называется связным графом (connected graph), если существует путь из каждой вершины в любую другую вершину графа. Не связный граф состоит из некоторого множества связных компонентов, которые представляют собой максимальные связные подграфы.

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

). (Ациклическим называется граф, в котором отсутствуют циклы -прим. перев.) Множество деревьев называется лесом (forest) или бором. Остовное дерево (spanning tree) связного графа -это подграф, который содержит все вершины этого графа и представляет собой единое дерево. Остовный лес (spanning forest) графа -это лес, который содержит все вершины этого графа.

Например, граф на рис 17.1 с тремя связными компонентами может иметь остовный лес эти и некоторые другие свойства показаны на большем графе.

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

G содержит V-1 ребро и ни одного цикла.

G содержит V-1 ребро и является связным.

Каждую пару вершин в G соединяет в точности один простой путь.

G является связным, а при удалении любого из ребер перестает быть связным.

Любое из указанных выше условий необходимо и достаточно для доказательства остальных трех, и из них можно вывести другие свойства деревьев (см. упражнение 17.1). Формально следовало бы выбрать одно из этих условий в качестве определения; но неформально они могут служить определениями все вместе и свободно заменять, например, слова " ациклический связный граф " в определении 17.4.

Графы, у которых присутствуют все ребра (т.е. между каждыми двумя вершинами -прим. перев.), называются полными графами (complete graph) -см. рис 17.4. Дополнение (complement) графа G определяется так: берется полный граф с тем же множеством вершин, что и исходный графа G, и из него удаляются все ребра графа G.

(рис 17.3) Терминология, употребляемая в теории графов

Этот граф содержит 55 вершин, 70 ребер и 3 связных компонента. Один из связных компонентов представляет собой дерево (справа). В графе имеется множество циклов, один из них выделен как крупный связный компонент (слева). На диаграмме также показано остовное дерево небольшого связного компонента (в центре). Весь граф не может иметь остовного дерева, поскольку он не является связным.

(рис 17.4) Полные графы

Здесь показаны полные графы, в которых каждая вершина соединена с любой другой вершиной. Они содержат, соответственно, 10, 15, 21, 28 и 36 ребер (снизу вверх). Каждый граф, содержащий от 5 до 9 вершин (существует более 68 миллиардов таких графов), является подграфом одного из этих графов.

Объединением (union) двух графов является граф, порожденный объединением множеств ребер этих графов. Объединение графа и его дополнения дает полный граф. Все графы, имеющие V вершин, являются подграфами полного графа с V вершинами. Общее количество различных графов с V вершинами равно 2<sup>V(V- 1)/2</sup> (количество различных подмножеств из V( V-1)/2 возможных ребер). Полный подграф называется кликой (clique).

Большинство встречающихся на практике графов содержат лишь небольшую часть всех возможных ребер. Для численного выражения этой концепции определим насыщенность (density) графа равной среднему значению степеней его вершин, т.е. 2E/V. Граф называется насыщенным (dense graph), если средняя степень его вершин близка к V; разреженный граф (sparse graph) есть граф, дополнение которого насыщенно. Другими словами, мы считаем граф насыщенным, если количество его ребер E имеет порядок V², и разреженным в противном случае. Такое " асимптотическое " определение не очень точно характеризует графы, однако различие очевидно: можно с уверенностью утверждать, что граф, состоящий из миллионов вершин и десятков миллионов ребер, является разреженным, а граф, состоящий из нескольких тысяч вершин и миллионов ребер, является насыщенным. Можно браться за обработку разреженного графа с миллиардами вершин, но насыщенный граф с миллиардами вершин содержит несметное количество ребер.

Информация о том, с каким графом мы имеем дело -с насыщенным или разреженным -обычно является главным фактором выбора эффективного алгоритма обработки графа. Например, для решения какой-то задачи мы можем разработать два алгоритма, и первому из них для ее решения понадобится V² шагов, а другому -E lgE шагов. Эти формулы показывают, что второй алгоритм лучше подходит для разреженных алгоритмов, а первый алгоритм следует применять для насыщенных графов. Например, насыщенный граф с миллионами ребер может иметь всего лишь несколько тысяч вершин: в этом случае величины V² и E имеют один порядок, а быстродействие алгоритма сложности V² в 20 раз выше, чем быстродействие алгоритма сложности ElgE. С другой стороны, разреженный граф с миллионами ребер будет иметь и миллионы вершин, следовательно, алгоритм сложности E lgE будет в миллионы раз быстрее алгоритма со сложностью V². Подробное изучение этих формул может привести к различным вариантам, но для практических целей обычно вполне достаточно терминов разреженный и насыщенный, чтобы можно было получить представление об основных характеристиках производительности.

При анализе алгоритмов обработки графов мы полагаем, что значение V/E ограничено сверху небольшой константой, и поэтому такие выражения, как V(V+E), можно упростить до VE. Это предположение нарушается только если количество ребер гораздо меньше количества вершин, что бывает крайне редко. Как правило, количество ребер намного превосходит количество вершин (V/E намного меньше 1).

Двудольный граф (bipartite graph) -это граф, множество вершин которого можно разбить на два таких подмножества, что любое ребро соединяет вершину из одного подмножества с вершиной из другого подмножества. Пример двудольного графа приведен на рис 17.5. Двудольные графы естественным образом возникают во многих ситуациях, таких как задачи поиска сопоставлений, описанные в начале этой главы. Любой подграф двудольного графа сохраняет это свойство.

(рис 17.5) Двудольный граф

Все ребра данного графа соединяют вершины с нечетными номерами с вершинами с четными номерами -т.е. это двудольный граф. Дву-дольность наглядно видна на нижней диаграмме.

Графы, которые мы рассматривали до сих пор, носят название неориентированных (undirected) графов. В ориентированных (directed) графах, известных еще как орграфы (digraph), ребра имеют направления: пара вершин, определяющая любое ребро, рассматривается как упорядоченная пара, которая определяет направленную смежность -в том смысле, что можно перейти из первой вершины во вторую, но не из второй вершины в первую. Многие приложения (например, графы, представляющие всемирную компьютерную сеть, или расписания действий, или телефонные звонки) естественным образом описываются как раз орграфами.

Ребра в орграфах называются ориентированными ребрами (directed edge), хотя обычно это свойство понятно из контекста (некоторые авторы называют ориентированные ребра дугами -arc). Первая вершина ориентированного ребра называется началом (source), а вторая вершина концом (destination). (Некоторые авторы употребляют, соответственно, термины хвост (tail) и голова (head), чтобы подчеркнуть, что это вершины ориентированного графа, однако мы будем избегать таких обозначений, поскольку употребляем эти же термины в реализациях структур данных.) На диаграммах ориентированные ребра изображаются в виде стрелок, направленных из начала в конец, и часто говорим, что ребро указывает (point) на конечную вершину. Обозначение w-v в орграфе означает, что это ребро, которое указывает из w на v, и оно отличается от ребра v-w, которое указывает из v на w. Мы также говорим о степени выхода (outdegree) и степени захода (indegree) вершины -это, соответственно, количество ребер, для которых она служит началом, и количество ребер, для которых она служит концом.

Иногда неориентированный граф удобнее рассматривать как орграф, у которого вместо каждого неориентированного ребра имеются два ориентированных ребра (по одному в каждом направлении); в других случаях неориентированный граф бывает лучше рассматривать просто как совокупность связей. Как правило, и для ориентированных, и для неориентированных графов мы используем одно и то же представление (см. рис 17.6), о чем подробно пойдет речь в разделе 17.4. То есть обычно для неориентированных графов мы поддерживаем два представления каждого ребра -по одному для каждого направления -чтобы иметь возможность сразу же ответить на вопросы типа " Какие вершины связаны с вершиной v? "

Изучению структурных свойств орграфов посвящена ; обычно они более сложны, чем соответствующие свойства неориентированных графов. Направленный цикл (directed cycle) в орграфе -это цикл, в котором пары смежных вершин появляются в порядке, указываемом ребрами графа. DAG-граф (Directed Acyclic Graph -ориентированный ациклический граф) представляет собой орграф, который не содержит направленных циклов. DAG-граф (ациклический орграф) не эквивалентен дереву (ациклическому неориентированному графу). Иногда мы рассматриваем базовый неориентированный граф (underlying undirected graph) орграфа, то есть неориентированный граф, определяемый тем же множеством ребер, только эти ребра не рассматриваются как ориентированные.

Главы 20—22 посвящены в основном анализу алгоритмов решения различных вычислительных задач, связанных с использованием графов, в вершинах и ребрах которых хранится дополнительная информация. В случае взвешенного графа (weighted graph) с каждым ребром связано число (weight -вес), которое обычно интерпретируется как расстояние либо стоимость. Можно также присвоить вес каждой вершине, либо несколько весов каждой вершине и каждому ребру. В мы будем изучать взвешенные неориентированные графы, а в и -взвешенные орграфы, которые называют сетями (network). Алгоритмы, рассматриваемые в , решают классические задачи, которые возникают при особой интерпретации сетей, известной как сетевые потоки (flow network).

(рис 17.6) Два орграфа

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

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

Упражнения

17.1. Докажите, что любой ациклический связный граф с V вершинами имеет V-1 ребро.

17.2. Приведите все связные подграфы графа 0-1 0-2 0-3 1-3 2-3.

17.3. Составьте список неизоморфных циклов графа, представленного на рис 17.1. Например, если в списке содержится цикл 3-4-5-3, то в нем не могут находиться циклы 3-5-4-3 , 4-5-3-4 , 4-3-5-4 , 5-3-4-5 или 5-4-3-5 .

17.4. Пусть дан граф 4-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4

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

17.5.

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

0-10-20-31-31-42-52-93-64-74-85-85-96-76-97-8

0-10-20-30-31-42-52-93-64-74-85-85-96-76-97-8

0-11-21-30-30-42-52-93-64-74-85-85-96-76-97-8

4-17-96-27-35-00-20-81-63-96-32-81-59-84-54-7

Какие из этих графов изоморфны друг другу? Какие из них планарны?

17.6. Какой процент из более чем 68 миллиардов графов, о которых говорится в подписи к рис 17.4, состоит из менее чем девяти вершин?

17.7. Сколько различных подграфов имеется в заданном графе с V вершинами и E ребрами?

17.8. Приведите максимально точные верхние и нижние границы количества связных компонентов графа с V вершинами и E ребрами.

17.9. Сколько существует неориентированных графов, содержащих V вершин и E ребер?

17.10. Сколько существует различных графов, содержащих V вершин и E ребер, если считать графы различными, только когда они не изоморфны?

17.11. Сколько графов, содержащих V вершин, являются двудольными?

АТД графа

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

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

Программа 17.1. Интерфейс АТД графа

Этот интерфейс -отправная точка для реализации и тестирования алгоритмов на графах. Он определяет два типа данных: тривиальный тип Edge (ребро) с функцией конструктора, которая создает ребро из двух заданных вершин, и тип GRAPH, определенный в соответствии со стандартной методологией независимости интерфейса АТД от представления (см. ).

Конструктор GRAPH принимает два аргумента: целое число, задающее количество вершин, и логическое значение, указывающее, является ли граф ориентированным или неориентированным (орграф) -по умолчанию граф неориентированный.

Базовые операции, необходимые для обработки графов и орграфов -функции АТД для их создания и уничтожения, подсчета количества вершин и ребер, а также добавления и удаления ребер. Класс итератора adjlterator позволяет клиентам выполнить обработку всех вершин, смежных с заданной. Его использование демонстрируется в программах 17.2 и 17.3.

    struct Edge
      { int v, w;
        Edge(int v = -1, int w = -1) : v(v), w(w) { }
      };
    class GRAPH
      { private:
        // Код, зависящий от реализации
      public:
          GRAPH(int, bool);
        ~GRAPH();
        int V() const;
        int E() const;
        bool directed() const;
        int insert(Edge);
        int remove(Edge);
        bool edge(int, int);
        class adjIterator
          { public:
            adjIterator(const GRAPH , int);
            int beg();
            int nxt();
            bool end();
          };
        };
      

АТД в программе 17.1 -это просто средство, которое позволяет разрабатывать и тестировать алгоритмы, но не универсальный интерфейс. Как обычно, мы работаем с простейшим интерфейсом, поддерживающим базовые операции обработки графов, которые нам могут понадобиться. Определение такого интерфейса для использования в практических приложениях требует тщательно продуманного компромисса между простотой, эффективностью и универсальностью. Ниже мы рассмотрим несколько таких компромиссов; а далее в этой книге будут рассмотрены и многие другие, которые мы будем анализировать в контексте конкретных реализаций и приложений.

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

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

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

Программа 17.2 содержит функцию, которая демонстрирует применение класса итератора из АТД графа. Эта функция извлекает из заданного графа множество его ребер и возвращает их в переменной типа vector из библиотеки STL (Standard Template Library -стандартная библиотека шаблонов) C++. По сути граф есть просто множество ребер, и довольно часто требуется получить граф именно в таком виде, независимо от его внутреннего представления.

Программа 17.2. Пример клиентской функции обработки графов

Данная функция демонстрирует один из способов использования АТД графа для реализации базовой операции обработки графов, не зависимой от представления. Она возвращает все ребра графа в виде вектора.

Эта реализация служит иллюстрацией основного способа работы большинства программ, которые мы будем рассматривать: для перебора всех ребер графа перебираются все вершины, смежные с каждой вершиной этого графа. Функции beg, end и nxt обычно не вызываются никаким другим способом, кроме продемонстрированного в этой программе -это позволяет лучше оценить характеристики производительности наших реализаций (см. раздел 17.5).

  template <class Graph>
  vector <Edge> edges(Graph G)
    { int E = 0;
      vector <Edge> a(G.E());
      for (int v = 0; v < G.V(); v++)
        { typename Graph::adjIterator A(G, v);
          for (int w = A.beg(); !A.end(); w = A.nxt())
            if (G.directed() || v < w)
              a[E++] = Edge(v, w);
        }
      return a;
    }
      

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

Программа 17.3 -другой пример использования класса итератора из АТД графа, она предназначена для вывода таблицы вершин, смежных с каждой вершиной (см. рис. 17.7 рис 17.7). Коды этих двух примеров довольно похожи, как похожи и многие другие программные реализации многочисленных алгоритмов обработки графов. Даже удивительно, что все алгоритмы, изучаемые в данной книге, можно построить, как и приведенные функции, на этой базовой абстракции обработки всех вершин, смежных с каждой вершиной (что эквивалентно обработке всех ребер в графе).

Как сказано в разделе 17.5, мы часто оформляем логически взаимосвязанные функции в отдельный класс. Программа 17.4 представляет собой интерфейс такого класса. В ней содержится определение функции show из программы 17.3, а также двух других функций, которые вставляют в граф ребра, считанные из стандартного ввода (реализации этих функций см. в упражнении 17.12 и программе 17.14).

Задачи обработки графов, рассматриваемые в этой книге, обычно принадлежат к одной из трех обширных категорий:

Вычисления значения какой-то меры графа.

Выбор некоторого подмножества ребер графа.

Ответы на вопросы о каких-то свойствах графа.

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

(рис 17.7) Формат списка смежности

Эта таблица служит еще одним способом представления графа, приведенного на рис 17.1; с каждой вершиной связывается множество смежных с ней вершин (которые соединены с ней одним ребром). Каждое ребро принадлежит двум множествам: для каждого ребра u-v графа вершина u содержится в множестве, связанном с вершиной v, а вершина v содержится в множестве, связанном с вершиной u.

Программа 17.3. Клиентская функция вывода графа

Данная реализация функции show для класса IO из программы 17.4 использует АТД графа для вывода таблицы вершин, смежных с каждой вершиной графа. Порядок перечисления вершин в таблице зависит от представления графа и реализации АТД (см. рис 17.7).

  template <class Graph>
  void IO<Graph>::show(const Graph G)
    { for (int s = 0; s < G.V(); s++)
        { cout.width(2); cout << s << ":";
          typename Graph::adjIterator A(G, s);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            { cout.width(2); cout << t << " "; }
          cout << endl;
        }
    }
      

Программа 17.4. Интерфейс ввода/вывода для обработки графов

Этот класс демонстрирует оформление схожих функций в единый класс. Он определяет функции, выполняющие вывод графа (см. программу 17.3), вставку ребер, определяемых парами целых чисел из стандартного ввода (см. упражнение 17.12) и вставку ребер, определяемых парами символов из стандартного ввода (см. программу 17.14).

  template <class Graph>
  class IO
    { public:
      static void show(const Graph );
      static void scanEZ(Graph );
      static void scan(Graph );
    };
      

Для решения таких задач мы будем строить абстрактные типы данных, которые являются клиентами базового АТД из программы 17.1, и которые, в свою очередь, позволяет отделить клиентские программы, требуемые для решения реальных задач, от их реализаций. Например, программа 17.5 представляет собой интерфейс для АТД связности графа. Мы можем написать клиентские программы, использующие этот АТД для создания объектов, которые вычисляют количество связных компонентов в графе и которые могут проверить, находятся ли любые две вершины в одном и том же связном компоненте. Описание реализаций такого АТД и характеристики их производительности будут даны в . Подобные АТД мы будем разрабатывать на протяжении всей книги. Как правило, такие АТД содержат общедоступную функцию-член, выполняющую предобработку (обычно это конструктор), приватные члены данных, которые содержат информацию, полученную во время предобработки, и общедоступные функции-члены обслуживания запросов, которые используют эту информацию для предоставления клиентам информации о графе.

В этой книге мы будем работать главным образом со статическими (static) графами, которые содержат фиксированное количество вершин V и ребер E.

Программа 17.5. Интерфейс связности

Данный интерфейс АТД демонстрирует типичную парадигму, которую мы используем для реализации алгоритмов обработки графов. Он позволяет клиентам создавать объекты, которые выполняют обработку графа для определения ответов на запросы, касающиеся связности этого графа. Функция-член count возвращает количество связных компонентов графа, а функция-член connect проверяет, связаны ли две заданные вершины. Реализация этого интерфейса приведена в программе 18.4.

  template <class Graph>
  class CC
    { private:
      // Код, зависящий от реализации 
      public:
        CC(const Graph );
        int count();
        bool connect(int, int);
    };
      

Обычно мы строим графы с помощью E вызовов функции insert, а затем обрабатываем их -либо вызвав соответствующую функцию АТД, которая принимает граф в качестве аргумента и возвращает некоторую информацию о графе, либо используя объекты наподобие вышеуказанных для предварительной обработки графа, которые позволяют затем эффективно отвечать на запросы, касающиеся графа. В любом случае, после изменения графа функциями insert и remove необходима повторная обработка графа. Динамические задачи, где обработка графов может чередоваться с добавлением или удалением вершин и ребер графа, принадлежат к онлайновым алгоритмам (on-line algorithm), известных также как динамические алгоритмы (dynamic algorithm), с которыми связаны другие сложные задачи. Например, задача связности, которую мы решали с помощью алгоритма объединения-поиска в , представляет собой пример интерактивного алгоритма, поскольку мы можем получать информацию о связности графа в процессе включения ребер в этот граф. АТД из программы 17.1 поддерживает операции вставить ребро и удалить ребро, и клиенты могут использовать их для внесения изменений в графы. Однако некоторые последовательности операций могут снизить производительность. Например, алгоритмы объединения-поиска могут потребовать повторной обработки всего графа, если клиент удалил из него ребро. В большинстве задач обработки графов, которые мы будем рассматривать, добавление или удаление нескольких ребер может кардинально изменить вид графа, а, значит, понадобится его повторная обработка.

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

Пример клиентской программы обработки графов приведен в программе 17.6. Она использует базовый АТД из программы 17.1, класс ввода/вывода из программы 17.4 для считывания графа из стандартного ввода и его вывода на стандартное устройство вывода, а также класс связности из программы 17.5 для определения количества его связных компонентов. Аналогичные, хотя и более сложные, клиентские программы мы будем использовать для построения других видов графов, тестирования алгоритмов, изучения других свойств графов и использования графов для решения других задач. Эту базовую схему можно применять в любых приложениях обработки графов.

В разделах 17.3—17.5 мы рассмотрим основные классические представления графа и реализации функций АТД из программы 17.1. Эти реализации позволят расширить интерфейс, чтобы охватить задачи обработки графов, которыми мы будем заниматься на протяжении ряда последующих глав.

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

Программа 17.6. Пример клиентской программы обработки графов

Эта программа демонстрирует использование абстрактных типов данных, описанных в настоящем разделе и использующих соглашения об АТД, которые были сформулированы в . Она создает граф с V вершинами, вставляет в него ребра, получаемые из стандартного ввода, выводит его, если граф не слишком велик, и вычисляет (и выводит) количество связных компонентов. Предполагается, что программы 17.1, 17.4 и 17.5 (с реализациями) содержатся соответственно в файлах GRAPH.cc, IO.cc и CC.cc.

  #include <iostream.h>
  #include <stdlib.h>
  #include "GRAPH.cc"
  #include "IO.cc"
  #include "CC.cc"
  main(int argc, char *argv[])
    { int V = atoi(argv[1]);
      GRAPH G(V);
      IO<GRAPH>::scan(G);
      if (V < 20) IO<GRAPH>::show(G);
      cout << G.E() << " ребер ";
      CC<GRAPH> Gcc(G);
      cout << Gcc.count() << " компонентов" << endl;
    }
      

Например, в качестве базы для реализации АТД можно рассмотреть представление в виде вектора ребер (см. упражнение 17.16). Это прямое представление несложно реализовать, однако оно не позволяет эффективно выполнять базовые операции обработки графов, к изучению которых мы вскоре приступим. Как мы увидим, большинство приложений обработки графов могут неплохо работать с одним из двух элементарных классических представлений, которые ненамного сложнее представления вектором ребер -матрица смежности и списки смежности. Эти представления графов, которые мы подробно изучим в разделах 17.3 и 17.4, основаны на элементарных структурах данных (и мы их рассматривали в и 5 в качестве примеров применения последовательного и связного распределения). Выбор одного из этих представлений зависит главным образом от того, является ли граф насыщенным или разреженным, хотя, как обычно, важную роль при принятии решения играет также характер выполняемых операций.

Упражнения

17.12. Разработайте реализацию функции scanEZ из программы 17.4: напишите функцию, которая строит граф, считывая ребра (пары целых чисел в диапазоне от 0 до V-1) из стандартного ввода.

17.13. Напишите клиентскую программу для АТД графа, которая добавляет ребра из заданного вектора в заданный граф.

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

17.15. Разработайте реализацию для АТД связности из программы 17.5, используя алгоритм объединения-поиска (см. )

17.8. Приведите реализацию функций из программы 17.1, которая использует для представления графа вектор ребер. Используйте примитивную реализацию функции, которая для удаления ребра v-w просматривает вектор, находит в нем ребро v-w или w-v и затем меняет местами найденное ребро с последним ребром вектора. Используйте аналогичный просмотр для реализации итератора. Примечание: предварительное чтение раздела 17.3 упростит вашу задачу.

Представление графа в виде матрицы смежности

Представление графа в виде матрицы смежности (adjacency matrix) -это матрица булевских значений размером Vх V, элемент которой, стоящий на пересечении v-ой строки и w-го столбца, равен 1, если в графе имеется ребро, соединяющее вершину v с вершиной w, и 0 в противном случае. Пример матрицы смежности приведен на рис 17.8.

(рис 17.8) Представление графа матрицей смежности

Данная булева матрица является еще одним представлением графа с рис. 17.1 рис 17.1. На пересечении строки v и столбца w этой матрицы находится 1 (true), если в графе имеется ребро, соединяющее вершину v с вершиной w, и 0 (false), если такого ребра нет. Эта матрица симметрична относительно главной диагонали. Например, шестая строка (и шестой столбец) показывает, что вершина 6 соединена с вершинами 0 и 4. В некоторых случаях мы считаем, что каждая вершина соединена сама с собой, и ставим единицы на главной диагонали. Большие нулевые области в верхнем правом и нижнем левом углах матрицы обусловлены выбранной нумерацией вершин для данного примера, но не свойствами рассматриваемого графа (за исключением того, что они указывают на разреженность графа).

Программа 17.7 является реализацией интерфейса АТД графа, в которой используется непосредственное представление этой матрицы в виде вектора векторов (см. рис 17.9). Это двумерная таблица существования, элемент adj[v][w] которой равен true, если в графе существует ребро, соединяющее вершину v с вершиной w, и false в противном случае. В случае неориентированного графа каждое ребро должно быть представлено двумя элементами: ребро v-w представлено значением true как в adj[v][w], так и в adj[w][v], что соответствует ребру w-v.

Имя DenseGRAPH в программе 17.7 подчеркивает, что эта реализация больше подходит для насыщенных, чем для разреженных графов, и отличает ее от других реализаций. Клиентская программа может воспользоваться определением типа typedef, чтобы сделать этот тип эквивалентным типу GRAPH или же явно воспользоваться именем DenseGRAPH.

В матрице смежности, которая представляет граф G, строка v есть вектор, представляющий собой таблицу существования, i-й элемент которого равно true, если вершина i смежна с v (в графе G имеется ребро v-i). Значит, чтобы дать клиентам возможность обрабатывать вершины, смежные с v, нужен код просмотра этого вектора, который находит значения true, как в программе 17.8. Понятно, что такая реализация обработки всех вершин, смежных с заданной вершиной, требует (по меньшей мере) времени, пропорционального количеству вершин V графа, независимо от количества смежных вершин.

(рис 17.9) Структура данных для матрицы смежности

На этом рисунке изображено представление графа с рис 17.1 в виде вектора векторов языка C++.

Программа 17.7. Реализация АТД графа (матрицей смежности)

Данный класс представляет собой непосредственную реализацию интерфейса из программы 17.1, основанную на представлении графа в виде вектора булевых векторов (см. рис 17.9). Вставка и удаление ребер выполняется за постоянное время. Запросы на вставку уже существующих ребер (функция insert) молча игнорируются, хотя клиенты могут проверить наличие какого-либо ребра с помощью функции edge. Для построения графа требуется время, пропорциональное V².

  class DenseGRAPH
    { int Vcnt, Ecnt; bool digraph;
      vector <vector <bool> > adj;
    public:
      DenseGRAPH(int V, bool digraph = false) :
        adj(V), Vcnt(V), Ecnt(0), digraph(digraph)
          { for (int i = 0; i < V; i++)
            adj[i].assign(V, false);
          }
      int V() const { return Vcnt; }
      int E() const { return Ecnt; }
      bool directed() const { return digraph; }
      void insert(Edge e)
        { int v = e.v, w = e.w;
          if (adj[v][w] == false) Ecnt++;
          adj[v][w] = true;
          if (!digraph) adj[w][v] = true;
        }
      void remove(Edge e)
        { int v = e.v, w = e.w;
          if (adj[v][w] == true) Ecnt—;
          adj[v][w] = false;
          if (!digraph) adj[w][v] = false;
        }
      bool edge(int v, int w) const
        { return adj[v][w]; }
      class adjlterator;
      friend class adjlterator;
    } ;
      

Программа 17.8. Итератор для представления матрицей смежности

Данная реализация итератора для программы 17.7 использует индекс i для пропуска элементов, равных false, в строке v матрицы смежности (adj[v]). Чтобы получить последовательность вершин, смежных с вершиной v графа G в порядке возрастания индексов вершин, необходим вызов функции beg(), а за ним последовательность вызовов функций xt() (с проверкой на false значения end() перед каждым таким вызовом).

  class DenseGRAPH::adjIterator
    { const DenseGRAPH G;
      int i, v;
    public:
      adjIterator(const DenseGRAPH G, int v) :
        G(G), v(v), i(-1) { }
      int beg()
        { i = -1; return nxt(); }
      int nxt()
        { for (i++; i < G.V(); i++)
          if (G.adj[v][i] == true) return i;
          return -1;
        }
      bool end()
        { return i >= G.V(); }
    };
      

Как было сказано в разделе 17.2, наш интерфейс требует, чтобы в момент инициализации графа клиенту было известно количество вершин. При необходимости можно разрешить вставку и удаление вершин (см. упражнение 17.21). Главное в конструкторе в программе 17.7 -это то, что при инициализации графа он заносит во все элементы матрицы значения false. Следует иметь в виду, что эта операция требует для своего выполнения время, пропорциональное V², независимо от количества ребер в графе. Для краткости в программу 17.7 не включены проверки на нехватку памяти -перед использованием программы нужно добавить такие проверки (см. упражнение 17.24).

Чтобы добавить в граф ребро, в указанный элемент матрицы заносится значение true (одно для орграфов, два для неориентированных графов). Такое представление не допускает параллельных ребер: если в граф нужно вставить ребро, для которого соответствующий элемент матрицы уже равен 1, то программа ничего не изменяет. В некоторых вариантах АТД может потребоваться информировать клиент о попытке включить параллельное ребро (возможно, с помощью кода возврата функции insert). Однако петли в данном представлении возможны: ребро v-v представляется ненулевым значением элемента a[v][v].

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

При обработке больших графов, или большого количества маленьких графов, или в других случаях, когда ощущается нехватка памяти, существует несколько способов экономии памяти. Например, матрицы смежности, представляющие неориентированные графы, симметричны: a[v][w] всегда равно a[w][v]. Значит, можно сэкономить память, храня только половину симметричной матрицы (см. упражнение 17.22). Другой способ экономии значительного объема памяти заключается в использовании битовой матрицы (если этого не делает функция vector<bool>). Тогда, например, мы можем хранить представление графа, состоящего примерно из 64000 вершин в примерно 64 миллионах 64-битовых слов (см. упражнение 17.23). Эти реализации связаны с небольшим усложнением проверки существования ребра (см. упражнение 17.20). (В наших реализациях такая операция не используется, поскольку проверка, существует ли ребро v-w, сводится к проверке значения a[v][w].) Подобные методы экономии памяти эффективны, но связаны с дополнительными расходами, которые могут утяжелить внутренний цикл приложения, для которого критично время выполнения.

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

Использование матриц смежности зависит от назначения в качестве имен вершин целых чисел в диапазоне от 0 до V-1. Такое назначение можно выполнить множеством различных способов; например, в разделе 17.6 будет рассмотрена программа, которая выполняет эту процедуру. Поэтому конкретная матрица значений 0-1, которую мы представили в виде вектора векторов языка C++, не является единственно возможным представлением матрицы смежности любого заданного графа, т.к. другая программа может присвоить другие имена вершин индексам, которые мы используем для указания строк и столбцов. Две совершенно различные на первый взгляд матрицы на самом деле могут представлять один и тот же граф (см. упражнение 17.17). Это наблюдение -просто другая формулировка задачи изоморфизма графов: несмотря на необходимость определения, являются ли две различные матрицы представлением одного и того же графа, еще никто не изобрел алгоритм, который всегда мог бы эффективно решать данную задачу. Эта трудность носит фундаментальный характер. Например, наши возможности найти эффективное решение различных важных задач обработки графов полностью зависят от способа нумерации вершин (см., например, упражнение 17.26).

Программа 17.3 из раздела 17.2 выводит таблицу вершин, смежных с каждой вершиной графа. Когда она используется совместно с реализацией в программе 17.7, она выводит список вершин в порядке возрастания индексов их вершин, как на рис 17.7. Однако учтите, что требование перебора вершин в порядке возрастания их индексов не входит в определение класса adjlterator, поэтому разработка клиента АТД, который выводит матрицу смежности, представляющую граф -нетривиальная задача (см. упражнение 17.18). Выходные данные, выводимые этими программами, сами являются представлениями графа, которые наглядно демонстрируют основные компромиссы относительно производительности алгоритма. Для вывода матрицы на странице нужно место, достаточное для размещения всех V 2 элементов; для вывода списков нужно место, достаточное для размещения V + E чисел. В случае разреженных графов, когда V² гораздо больше, чем V + E, предпочтительнее списки, а в случае насыщенных графов, когда E и V² сравнимы, удобнее матрица. Вскоре мы увидим необходимость такого же выбора, когда будем сравнивать представление графа матрицей смежности и его основной альтернативой -явным представлением списками смежности.

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

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

Упражнения

17.17. Приведите представления трех графов, изображенных на рис 17.2, в виде матриц смежности.

17.18. Приведите реализацию функции show для независимого от представления графа пакета io из программы 17.4, которая выводит двумерную матрицу нулей и единиц, наподобие приведенной на рис 17.8. Примечание', вы не должны зависеть от итератора, который перебирает вершины в порядке возрастания их индексов.

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

17.20. Добавьте в АТД графа функцию edge, которая позволит клиентам проверять, существует ли ребро, соединяющие две заданные вершины, и напишите реализацию для представления графа матрицей смежности.

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

17.22. Измените программу 17.7, расширенную как описано в упражнении 17.20, чтобы массив не содержал элементы a[v][w], у которых w больше, чем v -это должно снизить ее требования к памяти примерно наполовину.

17.23. Измените программу 17.7, расширенную как описано в упражнении 17.20, чтобы на компьютере со словами из B битов граф с V вершинами был представлен примерно V2/B (а не V²) словами. Эмпирически определите влияние упаковки битов в слова на время выполнения операций АТД.

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

17.25. Разработайте версию программы 17.7, которая использует единственный вектор, содержащий V² элементов.

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

Представление графа в виде списков смежности

Стандартное представление графа, которое обычно выбирают для ненасыщенных графов, называется представлением списками смежности (adjacency lists).

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

Программа 17.9 представляет собой реализацию интерфейса АТД из программы 17.1, основанную на данном подходе, а на рис 17.10 приведен соответствующий пример. Чтобы добавить в это представление графа ребро, соединяющее вершины v и w, мы добавляем w в список смежности вершины v, а v -в список смежности вершины w. Таким образом, добавление новых ребер выполняется за постоянное время, однако общий объем занимаемой при этом памяти пропорционален сумме количества вершин и количества ребер (в отличие от пропорциональности квадрату количества вершин для представления графа матрицей смежности). Ребра неориентированных графов опять фигурируют в двух различных местах, т.к. ребро, соединяющее вершину v с w, представлено узлами в обоих списках смежности. Оба включения обязательны, иначе мы не сможем эффективно отвечать на простые вопросы вроде " Какие вершины смежны с вершиной v? " Программа 17.10 реализует итератор, который дает ответ клиентам, задающим такие вопросы, за время, пропорциональное количеству таких вершин.

(рис 17.10) Структура данных списков смежности

Здесь показано представление графа с рис 17.1 в виде массива связных списков. Объем используемой памяти пропорционален сумме количества вершин и количества ребер. Чтобы найти индексы вершин, связанных с заданной вершиной v, мы выбираем v-ю позицию этого массива, которая содержит указатель на связный список, содержащий по одному узлу для каждой вершины, связанной с v. Порядок, в котором узлы расположены в списках, зависит от метода, которым были построены эти списки.

Реализации в программах 17.9 и 17.10 являются низкоуровневыми. В качестве альтернативы можно реализовать каждый связный список с помощью контейнера list из библиотеки STL (см. упражнение 17.30). Недостаток такого подхода заключается в том, что реализациям list из STL приходится поддерживать гораздо большее количество операций, чем нужно нам, а это обычно означает излишние затраты, которые могут ухудшить производительность всех разрабатываемых нами алгоритмов (см. упражнение 17.31). Вообще-то все наши алгоритмы обработки графов используют интерфейс АТД Graph, так что эта реализация -вполне подходящее место для инкапсуляции всех низкоуровневых операций. Так мы достигнем нужной эффективности, не затрагивая другие программы. Другое преимущество представления графа связными списками заключается в том, что оно обеспечивает базу для оценки производительности наших приложений. Однако учтите, что реализация связных списков в программах 17.9 и 17.10 неполна, в ней нет деструктора и конструктора копирования. Во многих случаях это может привести к неожиданным результатам или серьезному снижению производительности. Эти функции являются прямыми расширениями функций из реализации очереди первого класса в программе 4.22 (см. упражнение 17.29).

Программа 17.9. Реализация АТД графа (списками смежности)

Данная реализация интерфейса из программы 17.1 использует вектор связных списков, каждый из которых соответствует одной вершине. Она эквивалентна представлению в программе 3.15, где ребро v-w представлено узлом вершины w в списке вершины v и узлом вершины v в списке вершины w.

Реализации функций remove и edge, а также конструктора копирования и деструктора оставлены в качестве самостоятельных упражнений. Код функции insert обеспечивает постоянное время вставки ребра за счет отказа от проверки параллельности ребер. Общий объем используемой памяти пропорционален V + E, т.е. это представление больше подходит для разреженных мультиграфов.

Клиентские программы могут воспользоваться конструкцией typedef, чтобы сделать этот тип эквивалентным типу GRAPH, или явно использовать класс SparceMultiGRAPH.

  class SparseMultiGRAPH
    { int Vcnt, Ecnt; bool digraph;
      struct node
        { int v; node* next;
          node(int x, node* t) { v = x; next = t; }
        } ;
      typedef node* link;
      vector <link> adj;
    public:
      SparseMultiGRAPH(int V, bool digraph = false) :
        adj(V), Vcnt(V), Ecnt(0), digraph(digraph)
        { adj.assign(V, 0); }
      int V() const { return Vcnt; }
      int E() const { return Ecnt; }
      bool directed() const { return digraph; }
      void insert(Edge e)
        { int v = e.v, w = e.w;
          adj[v] = new node(w, adj[v]);
          if (!digraph) adj[w] = new node(v, adj[w]);
          Ecnt++;
        }
      void remove(Edge e);
      bool edge(int v, int w) const;
      class adjlterator;
      friend class adjlterator;
      } ;
      

В данной книге мы полагаем, что объекты SparceMultiGRAPH содержат их. В этом смысле STL-контейнер list гораздо удобнее низкоуровневых однонаправленных списков, он снимает необходимость в дополнительном кодировании, поскольку соответствующий деструктор и конструктор копирования определены автоматически. Например, объекты DenseGRAPH, построенные в программе 17.7, правильно уничтожаются и копируются клиентскими программами, так как они построены из объектов библиотеки STL.

В отличие от программы 17.7, программа 17.9 строит мультиграфы, т.к. она не удаляет параллельные ребра. Для выявления повторяющихся ребер в структуре списков смежности необходим просмотр списков со временем, пропорциональным V. Кроме того, в программе 17.9 отсутствует реализация операции удалить ребро и проверить наличие ребра. Добавление реализаций этих функций не представляет труда (см. упражнение 17.28), но каждая такая операция может потребовать время, пропорциональное V, на поиск в списках узлов, представляющих ребра. Из-за этих затрат представление списками смежности может оказаться неприемлемым для приложений, выполняющих обработку очень больших графов, в которых недопустимы параллельные ребра, или для приложений, в которых интенсивно используются операции удалить ребро или проверить наличие ребра. В разделе 17.5 будут рассмотрены реализации списками смежности, которые обеспечивают выполнение операций удалить ребро и проверить наличие ребра за постоянное время.

Если в качестве имен вершин графа используются обозначения, отличные от целых чисел, то (как и в случае матриц смежности) две разные программы могут связать имена вершин с целыми числами в диапазоне от 0 до V-1 двумя различными способами, а это приведет к образованию двух различных структур списков смежности (см., например, программу 17.15). Из-за сложности задачи изоморфизма графов трудно рассчитывать на то, что мы сумеем определить, представляют ли различные структуры один и тот же граф.

Программа 17.10. Итератор для представления списками смежности

Данная реализация итератора для программы 17.9 использует ссылку t для обхода связного списка, присоединенного к вершине v. Чтобы получить последовательность вершин, смежных с вершиной v графа G, необходим вызов функции beg() , а за ним последовательность вызовов функций nxt() (с проверкой на false значения end() перед каждым таким вызовом).

  class SparseMultiGRAPH::adjIterator
    { const SparseMultiGRAPH G;
      int v;
      link t;
    public:
      adjIterator(const SparseMultiGRAPH G, int v) :
        G(G), v(v) { t = 0; }
      int beg()
        { t = G.adj[v]; return t ? t->v : -1; }
      int nxt()
        { if (t) t = t->next; return t ? t->v : -1; }
      bool end()
        { return t == 0; }
    };
      

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

Основное преимущество представления списками смежности по сравнению с представлением матрицей смежности заключается в том, что оно всегда требует объем памяти, пропорциональный V + E, а не V². А основной недостаток состоит в том, что проверка наличия конкретных ребер может потребовать время, пропорциональное V -в отличие от постоянного времени для матрицы смежности. Эти различия, по сути, возникают из-за различия в использовании связных списков и векторов для представления множеств вершин, инцидентных каждой вершине.

Итак, мы снова приходим к тому, что понимание базовых свойств связных структур данных и векторов критично для построения эффективных реализаций АТД графа. Интерес к такому различию в производительности естественен, т.к. мы хотим избежать слишком неэффективных реализаций, когда от АТД требуется выполнение множества разнообразных операций. В разделе 17.5 будут рассмотрены вопросы применения базовых структур данных для использования возможных достоинств обеих рассматриваемых структур на практике. И все-таки простая реализация, приведенная в программе 17.9, обладает всеми свойствами, которые необходимы для изучения эффективных алгоритмов обработки разреженных графов.

Упражнения

17.27. В стиле рисунка 17.10 приведите структуру списков смежности, полученную при вставке программой 17.9 ребер

3-71-47-80-55-23-82-90-64-92-66-4(вуказанно мпо рядке)вперво начально пусто йграф.

17.28. Напишите реализации функций remove и edge для класса графов, представленных списками смежности (программа 17.9). Примечание', в случае параллельных ребер достаточно удалить любое ребро, соединяющее заданные вершины.

17.29. Добавьте конструктор копирования и деструктор в класс графов, представленных списками смежности (программа 17.9). Совет, см. программу 4.22.

17.30. Измените реализацию класса SparceMultiGRAPH в программах 17.9 и 17.10, используя вместо связного списка STL-контейнер list для представления каждого списка смежности.

17.31. Эмпирически сравните реализацию класса SparceMultiGRAPH из упражнения 17.30 с реализацией, приведенной в тексте. На примере специально подобранного множества значений V сравните значения времени работы клиентской программы, которая строит полные графы с V вершинами, после чего перебирает их ребра с помощью программы 17.2.

17.32. Приведите простой пример представления графа списками смежности, которое невозможно построить многократной вставкой ребер с помощью программы 17.9.

17.33. Сколько различных представлений графа в виде списков смежности представляют один и тот же граф, показанный на рис. 17.10 рис 17.10?

17.34. Добавьте в АТД графа (программа 17.1) объявление общедоступной функции-члена, которая удаляет петли и параллельные ребра. Напишите тривиальную реализацию этой функции для класса на базе матрицы смежности (программа 17.7) и для класса на базе списков смежности (программа 17.9), которая использует время, пропорциональное E, и объем памяти, пропорциональный V.

17.35. Напишите версию программы 17.9, которая блокирует добавление параллельных ребер (просматривая список смежности при каждой вставке ребра) и петель. Сравните полученную реализацию с реализацией из упражнения 17.34. Какая из них лучше подходит для работы со статическими графами? Примечание, оптимальную реализацию см. в упражнении 17.49.

17.36. Напишите клиентскую программу АТД графа, которая возвращает результат удаления петель, параллельных ребер и вершин степени 0 (изолированных вершин) из заданного графа. Примечание, Время выполнения вашей программы должно линейно зависеть от размера представления графа.

17.37. Напишите клиентскую программу АТД графа, которая возвращает результат удаления из заданного графа петель и сворачиваемых путей, т.е. состоящих исключительно из вершин степени 2. А именно, каждая вершина степени 2 в графе без параллельных ребер принадлежит некоторому пути u-...-w, где вершины u и w могут иметь степени, не равные 2. Замените каждый такой путь ребром u-w, а затем удалите все промежуточные вершины степени 2 как в упражнении 17.37. Примечание, Эта операция может привести к появлению петель и параллельных ребер, но она сохраняет степени вершин, которые не были удалены.

17.38. Приведите (мульти)граф, полученный преобразованием из упражнения 17.37 графа, показанного нарис 17.1.

Вариации, расширения и затраты

В этом разделе мы рассмотрим несколько способов совершенствования представлений графов, которые были описаны в разделах 17.3 и 17.4. Все рассматриваемые вопросы можно разделить на три категории. Во-первых, базовые механизмы матрицы смежности и списков смежности легко расширяются для представления других видов графов. В последующих лекциях будут рассмотрены и такие расширения, и соответствующие примеры; а здесь мы дадим лишь краткий обзор. Во-вторых, мы рассмотрим структуры АТД графа с большим набором свойств, чем структура, выбранная нами в качестве базовой, и использование более развитых структур данных для построения их эффективных реализаций. В-третьих, мы подробнее изучим наш общий подход к решению задач обработки графов, разрабатывая на основе базового АТД графа классы, нацеленные на некоторые конкретные задачи.

Реализации, приведенные в программах 17.7 и 17.9, могут строить орграфы, если при вызове конструктора указать второй аргумент, равный true. Как показано на рис 17.11, каждое ребро входит в представление графа только один раз.

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

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

(рис 17.11) Представления орграфа

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

Часто возникает необходимость привязывать к вершинам или ребрам графа еще больше информации, чтобы графы могли моделировать более сложные объекты. Эту дополнительную информацию можно связать с каждым ребром, расширив тип Edge из программы 17.1, а затем используя экземпляры этого типа в матрицах смежности или в узлах списков смежности. Или, поскольку именами вершин являются целые числа в диапазоне от 0 до V—1, можно воспользоваться векторами, индексированными этими именами, чтобы привязать к вершинам дополнительную информацию -возможно, с помощью соответствующих АТД. Мы рассмотрим такие АТД в лекциях 20—22 . А можно воспользоваться отдельным АТД таблицы символов для привязки дополнительной информации к каждой вершине и к каждому ребру (см. упражнение 17.48 и программу 17.15).

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

В качестве примера предположим, что нужно узнать, является ли вершина v графа изолированной. Равна ли степень вершины v нулю? При представлении графа списками смежности эту информацию можно получить немедленно, просто проверив, на равенство нулю значение adj[v]. Однако в случае представления матрицей смежности придется проверить все элементы в строке или столбце v, чтобы убедиться, что вершина не соединена ни с какой другой вершиной. А в случае представления графа вектором ребер остается только просмотреть все E ребер, чтобы проверить, содержат ли какие-либо ребра вершину v. Необходимо оградить клиенты от подобных длительных вычислений. Как было сказано в разделе 17.2, один из способов заключается в том, чтобы определить клиентский АТД для задачи, как это сделано в программе 17.11. Эта реализация после предварительной обработки графа за время, пропорциональное размеру его представления, позволит клиентам определить степень любой вершины за постоянное время. Такой способ не дает никакого выигрыша, если клиенту нужно узнать степень только одной вершины, но обеспечивает существенную экономию ресурсов тем клиентам, которые хотят определять значения степеней многих вершин. Существенное различие в производительности алгоритмов решения достаточно простой задачи характерно для обработки графов.

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

Программа 17.11. Реализация класса для определения степеней вершин

Этот класс предоставляет способ определения степени любой заданной вершины объекта GRAPH за постоянное время после предварительной обработки в конструкторе за линейное время. Реализация основана на использовании вектора степеней вершин, индексированного именами вершин, в качестве приватного члена и перегрузки операции [] как общедоступной функции-члена. Вначале все элементы обнуляются, а затем выполняется просмотр всех ребер графа с увеличением на единицу соответствующих элементов для каждого ребра.

Подобные классы используются в данной книге при разработке объектно-ориентированных реализаций функций обработки графов как клиентов класса GRAPH.

  template <class Graph>
  class DEGREE
    { const Graph G;
      vector <int> degree;
    public:
      DEGREE(const Graph G) : G(G), degree(G.V(), 0)
        { for (int v = 0; v < G.V(); v++)
          { typename Graph::adjIterator A(G, v);
            for (int w = A.beg(); !A.end(); w = A.nxt())
              degree[v]++;
          }
        }
      int operator[](int v) const
        { return degree[v]; }
    };
     

Существует много других способов разработки на основе интерфейсов в C++. Одно из направлений дальнейших действий состоит в простом добавлении общедоступных функций-членов (и любых других приватных данных и функций-членов, которые могут потребоваться) в определение базового АТД GRAPH. Такой подход обладает всеми достоинствами, расхваленными в , но ему свойственны и серьезные недостатки, поскольку сфера обработки графов намного шире, чем виды базовых структур данных, которые были рассмотрены в . Вот основные из этих недостатков,

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

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

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

Такие интерфейсы называются " толстыми " (fat). В книге, посвященной алгоритмам обработки графов, подобные интерфейсы и в самом деле выглядят " толстыми " .

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

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

Производительность основных операций АТД, осуществляющих обработку графов, существенно различается в зависимости от выбора представления графа, даже если рассматривать только простейшие операции. Здесь приведены затраты на выполнение операций в худших случаях (с точностью до постоянного множителя для больших значений V и E). Приведенные стоимости получены для простых реализаций, которые были описаны в предыдущих разделах. А различные модификации, которые могут повлиять на затраты, описываются в данном разделе.

Затраты на выполнение операций обработки графов в худшем случае

	Массив ребер	Матрица смежности	Списки смежности
Память	E	V2	V+E
Инициализация пустого объекта	1	V2	V
Копирование	E	V2	E
Уничтожение	1	V	E
Вставка ребра	1	1	1
Поиск/удаление ребра	E	1	V
Вершина v изолирована?	E	V	1
Существует ли путь от u к v?	E lg*V	V2	V+E

Иногда удается модифицировать представление графа, чтобы повысить эффективность простых операций, но при этом нужно следить, чтобы не увеличить стоимость других простых операций. Например, значение в таблице, соответствующее строке " Уничтожение " и столбцу " Матрица смежности " , следует из выбранного нами представления двухмерной матрицы в виде вектора векторов (см. ). Эти затраты нетрудно снизить до постоянной величины (см. упражнение 17.25). Но если ребра графа представляют собой достаточно сложные структуры, для которых требуется хранение указателей в элементах матрицы, то операция уничтожить для матрицы смежности потребует затрат, пропорциональных V².

Операции найти ребро и удалить ребро часто используются в обычных приложениях, и поэтому мы их рассматриваем более подробно. В частности, операция найти ребро нужна для удаления или блокировки добавления параллельных ребер. Как было показано в , эти операции тривиальны, если использовать представление матрицей смежности -достаточно просто проверить или изменить значение элемента матрицы, который допускает прямую индексацию. Но как обеспечить эффективную реализацию этих операций для представления списками смежности? В языке C++ можно воспользоваться библиотекой STL; здесь мы опишем базовые механизмы, чтобы получить представление о проблемах обеспечения эффективности. Один из подходов описан ниже, а другой -в упражнении 17.50. Оба подхода основаны на использовании реализаций таблицы символов. Например, если мы используем реализации динамической хеш-таблицы (см. ), то оба подхода потребуют объем памяти, пропорциональный E, и позволяют выполнять обе операции за постоянное время (в среднем, амортизированный подсчет).

В частности, для реализации операции найти ребро при использовании списков смежности можно воспользоваться вспомогательной таблицей символов для ребер. Каждому ребру v-w можно назначить целочисленный ключ v*V+w и воспользоваться контейнером map из библиотеки STL или любой реализацией таблицы символов из части IV (Для неориентированных графов ребрам v-w и w-v можно присваивать одни и те же ключи.) Каждое ребро можно заносить в таблицу символов после предварительной проверки, было ли оно занесено раньше. Можно выбрать как блокировку включения параллельных ребер (см. упражнение 17.49), так и сохранение повторяющихся записей для параллельных ребер в таблице символов (см. упражнение 17.50). Сейчас эта техника интересует нас в основном тем, что она делает возможной реализацию операции найти ребро с постоянным временем выполнения для представления списками смежности.

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

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

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

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

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

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

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

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

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

Значение в нижней строке левого столбца таблицы 17.1 получено для алгоритмов объединения-поиска, описанных в (см. упражнение 17.15). Этот метод привлекателен тем, что необходимый для него объем памяти пропорционален лишь V, однако он не способен находить пути. Этот элемент таблицы 17.1 подчеркивает важность полного и точного описания задач обработки графов.

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

Упражнения

17.39. Разработайте представление матрицей смежности для насыщенных мультиграфов и напишите реализацию АТД для использующей его программы 17.1.

17.40. Почему не стоит использовать прямое представление графов (структура данных, которая точно моделирует граф с объектами-вершинами, содержащими списки смежности со ссылками на эти вершины)?

17.41. Почему программа 17.11 не увеличивает на единицу оба значения deg[v] и deg[w], когда она обнаруживает, что вершина v смежна с w?

17.42. Добавьте в класс графа на основе матрицы смежности (программа 17.7) вектор, индексированный именами вершин, который содержит степени каждой вершины. Добавьте общедоступную функцию-член degree, которая возвращает степень заданной вершины.

17.43. Выполните упражнение 17.43 для представления списками смежности.

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

17.45. Добавьте в таблицу 17.1 строку для задачи определения, содержит ли заданный орграф вершину со степенью захода V и степенью выхода 0. Дополните ответ реализациями функций для каждого из трех представлений. Примечание, значение для представления матрицей смежности должно быть равно V.

17.46. Воспользуйтесь двусвязными списками смежности с перекрестными ссылками (см. текст) для реализации функции remove, выполняющей операцию удалить ребро за постоянное время для реализации АТД графа, в которой используются списки смежности (программа 17.9).

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

17.48. Измените решение упражнения 17.16, чтобы в нем использовалась динамическая хеш-таблица (см. описание в тексте), и операции вставить ребро и удалить ребро выполнялись за постоянное (в среднем) время.

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

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

17.51. Разработайте АТД графа, ориентированный на статические графы, в котором конструктор принимает в качестве аргумента вектор ребер и использует для построения графов базовый АТД графа. (Такая реализация может оказаться полезной для сравнения производительности с реализациями из упражнений 17.52—17.55.)

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

  struct node { int cnt; vector <int> edges; };
  struct graph { int V; int E; vector <node> adj; };
      

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

17.53. Добавьте в решение упражнения 17.52 функцию для удаления петель и параллельных ребер, как в упражнении 17.34.

17.54. Разработайте реализацию АТД статического графа, описанного в упражнении 17.51, которая использует для представления графа только два вектора, один -вектор E вершин, второй -вектор V индексов или указателей на элементы первого вектора. Реализуйте функцию io::show для этого представления.

17.55. Добавьте в решение упражнения 17.54 функцию для удаления петель и параллельных ребер, как в упражнении 17.34.

17.56. Разработайте интерфейс АТД графа, который связывает с каждой вершиной координаты (x, y), что позволит работать с чертежами графов. Включите в интерфейс функции drawV и drawE для вычерчивания, соответственно, вершин и ребер.

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

17.58. Разработайте реализацию интерфейса из упражнения 17.56, генерирующую PostScript-программу для вычерчивания графов (см. ).

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

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

Генераторы графов

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

Для конкретизации примеров мы представим их в виде клиентских функций программы 17.1 -тогда мы сможем непосредственно применять их для тестирования рассматриваемых реализаций алгоритмов на графах. Кроме того, мы рассмотрим реализацию функции io::scan из программы 17.4, которая считывает последовательность пар произвольных имен из стандартного ввода и строит граф с вершинами, соответствующими именам, и ребрами, соответствующими парам.

Реализации, которые будут рассмотрены в этом разделе, основаны на интерфейсе из программы 17.1, так что теоретически они должны правильно работать для любого представления графа. Хотя на практике, как мы увидим, некоторые сочетания интерфейса и представлений не могут обеспечить приемлемой производительности.

(рис 17.12) Два случайных графа

Оба приведенных здесь графа содержат по 50 вершин. Разреженный граф в верхней части рисунка содержит 50 ребер, а насыщенный граф в нижней части рисунка -500ребер. Разреженный граф не является связным, поскольку каждая его вершина соединена только с небольшим количеством других вершин; насыщенный граф, несомненно, является связным, т.к. каждая его вершина связана в среднем с 20 другими вершинами. Эти диаграммы демонстрируют сложность разработки алгоритмов вычерчивания произвольных графов (на рисунке вершины размещены в случайно выбранных местах).

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

Случайные ребра. Реализация этой модели довольно проста -см. генератор, представленный в программе 17.12. Для заданного количества вершин V генерируются произвольные ребра, т.е. пары случайных чисел от 0 до ); поэтому данный метод обычно используется для разреженных графов.

Случайный граф. Классическая математическая модель случайных графов -включение в граф каждого возможного ребра с одинаковой вероятностью p. Если нужно, чтобы ожидаемое количество ребер графа было равно E, следует выбрать p = 2E/V(V-1). Функция в программе 17.13 использует эту модель для генерации случайных графов.

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

Данная функция добавляет в граф случайные ребра. Для этого она генерирует E случайных пар целых чисел, интерпретируя числа как метки вершин, а пары меток вершин как ребра. Решение о том, как поступать с параллельными ребрами и петлями, возлагается на функцию-член insert класса Graph. Обычно этот метод не годится для генерации очень больших и насыщенных графов из-за большого количества параллельных ребер.

    static void randE(Graph G, int E)
      { for (int i = 0; i < E; i++)
        { int v = int(G.V()*rand()/(1.0+RAND MAX));
          int w = int(G.V()*rand()/(1.0+RAND MAX));
          G.insert(Edge(v,w));
        }
      }
      

Параллельные ребра не допускаются, а количество ребер в графе равно E только в среднем. Эта реализация удобна для генерации насыщенных, а не разреженных графов, поскольку за время, пропорциональное V(V-1)/2, она генерирует E = pV(V-1)/2 ребер. То есть для разреженных графов время работы программы 17.13 квадратично зависит от размера графа (см. упражнение 17.68).

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

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

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

  static void randG(Graph G, int E)
    { double p = 2.0*E/G.V()/(G.V()-1);
      for (int i = 0; i < G.V(); i++)
        for (int j = 0; j < i; j++)
          if (rand() < p*RAND MAX)
            G.insert(Edge(i, j));
    }
      

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

(рис 17.13) Случайные графы с соседними связями

Здесь приведены примеры двух моделей разреженных графов. Граф с соседними связями в верхней части рисунка содержит 33 вершины и 99ребер, и каждое ребро может соединять одну вершину с другой, если их индексы отличаются не более чем на 10 (по модулю V). Евклидов граф с соседними связями в нижней части рисунка моделирует графы, которые встречаются в приложениях, где вершины привязаны к конкретным геометрическим точкам. Для вершин выбраны случайные точки на плоскости, а ребра соединяют любую пару вершин, расстояние между которыми не превышает d.

Этот граф относится к категории разреженных (177вершин и 1001 ребро). Изменяя значения d, можно построить граф любой степени насыщенности.

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

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

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

(рис 17.14) Граф транзакций

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

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

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

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

В некоторых приведенных выше примерах вершины представляют собой естественные имена объектов, а ребра -пары именованных объектов. Например, граф транзакций может быть построен из последовательности пар телефонных номеров, а евклидов граф -из последовательности пар населенных пунктов. Программа 17.14 представляет собой реализацию функции scan из программы 17.4, которой можно воспользоваться для построения графов в общих ситуациях. Для удобства клиентских программ она использует в качестве определения графа множество ребер и определяет множество имен вершин графа на основании их присутствия в ребрах. А именно, программа считывает последовательность пар символов из стандартного ввода, использует таблицу символов для связывания этих символов с номерами вершин от 0 до ). Эти программы упрощают тестирование алгоритмов на реальных графах, которые невозможно точно описать какой бы то ни было вероятностной моделью.

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

Данная реализация функции scan из программы 17.4 использует таблицу символов для построения графа на основе пар символов, считываемых из стандартного ввода. Функция index АТД таблицы символов ставит в соответствие каждому символу целое число: если поиск в таблице размера N заканчивается неудачно, она добавляет в таблицу символ с привязанным к нему целым числом N+1; а если поиск завершается успешно, она просто возвращает целое число, которое ранее было связано с этим символом. Годится любой метод работы с таблицами символов из рассмотренных в части IV -например, программа 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)));
    }
      

Программа 17.15 важна еще и потому, что она обосновывает наше допущение, которое было сделано во всех разрабатываемых нами алгоритмах: что имена вершин являются целочисленными значениями от 0 до V-1. Если у какого-то графа имеется другое множество имен вершин, то перед построением представления графа нужно выполнить программу 17.15, чтобы переобозначить имена вершин целыми числами из диапазона от 0 до V-1.

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

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

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

  #include <string>
  class ST
    { int N, val;
      struct node
        { int v, d; node* l, *m, *r;
          node(int d) : v(-1), d(d), l(0), m(0), r(0) {}
        } ;
      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; }
    } ;
      

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

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

(рис 17.15) Граф со степенями разделения

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

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

Граф де Брюйна. Предположим, что V равно степени 2. Мы определяем орграф следующим образом: каждому неотрицательному целому числу, меньшему V, соответствует одна вершина графа, а ребра соединяют каждую вершину i с вершинами изображены графы де Брюйна (de Bruijn) с 8, 16, 32 и 64 вершинами.

(рис 17.16) Графы де Брюйна

Орграф де Брюйна порядка n содержит 2ⁿ вершин и ребра, соединяющие вершины i с вершинами 2i mod 2n и (2i + 1) mod 2n для всех i . Здесь показаны неориентированные графы, соответствующие орграфам де Брюйна порядка 6, 5, 4 и 3 (сверху вниз).

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

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

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

Упражнения

17.61. Какую часть генерируемых ребер составляют петли, если для построения случайных графов с насыщенностью aV используется программа 17.12?

17.62. Вычислите ожидаемое количество полученных параллельных ребер, если для генерации случайных графов с V вершинами и насыщенностью а используется программа 17.12. Воспользуйтесь полученным результатом для построения графиков зависимости доли параллельных ребер от a при V= 10, 100 и 1000.

17.63. Воспользуйтесь контейнером map из библиотеки STL для разработки альтернативной реализации класса ST из программы 17.15.

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

17.65. Напишите программу, которая генерирует разреженные случайные графы для специально подобранных наборов значений V и E и выводит объем памяти, необходимый для представления графа, и время на его построение. Протестируйте программу с помощью класса разреженного графа (программа 17.9) и генератора случайных графов (программа 17.12), чтобы иметь возможность выполнять обоснованные эмпирические исследования графов, построенных на базе этой модели.

17.66. Напишите программу, которая генерирует насыщенные случайные графы для специально подобранных наборов значений V и E и выводит объем памяти, необходимый для представления графа, и время на его построение. Протестируйте программу с помощью класса насыщенного графа (программа 17.7) и генератора случайных графов (программа 17.13), чтобы иметь возможность выполнять обоснованные эмпирические исследования графов, построенных на базе этой модели.

17.67. Приведите среднеквадратичное отклонение количества ребер, генерируемых программой 17.13.

17.68. Напишите программу, которая строит каждый возможный граф с точно такой же вероятностью, что и программа 17.13, но затрачивает время и объем памяти, пропорциональные V+E, а не V². Протестируйте программу, как описано в упражнении 17.65.

17.69. Напишите программу, которая строит каждый возможный граф с точно такой же вероятностью, что и программа 17.12, но затрачивает время и объем памяти, пропорциональные E, даже для насыщенности, близкой к 1. Протестируйте программу, как описано в упражнении 17.66.

17.70. Напишите программу, которая генерирует с равной вероятностью каждый возможный граф с Vвершинами и E ребрами (см. упражнение 17.9). Протестируйте программу, как описано в упражнении 17.65 (для ненасыщенных графов) и в упражнении 17.66 (для насыщенных).

17.71. Напишите программу, которая генерирует случайные графы, соединяя вершины, которые упорядочены на сетке размером $$$\sqrt{V}\times \sqrt{V}$$$, с соседними вершинами (см. рис 1.2), при этом каждая вершина соединяется к дополнительными ребрами со случайно концевой вершиной (выбор любой концевой вершины равновероятен). Определите, каким должно быть к, чтобы ожидаемое количество ребер было равно E. Протестируйте программу, как описано в упражнении 17.65.

17.72. Напишите программу, которая генерирует случайные орграфы, соединяя вершины, которые упорядочены на сетке размером $$$\sqrt{V}\times \sqrt{V}$$$, с соседними вершинами, при этом каждое возможное ребро появляется с вероятностью p (см. рис 1.2). Определите, каким должно быть p, чтобы ожидаемое количество ребер было равно E. Протестируйте программу, как описано в упражнении 17.65.

17.73. Внесите в программу из упражнения 17.72 возможность добавления R дополнительных случайных ребер, вычисленных как в программе 17.12. Для больших R сожмите решетку настолько, чтобы общее количество ребер оставалось примерно равным V.

17.74. Напишите программу, которая генерирует V случайных точек на плоскости, а потом строит граф из ребер, соединяющих все пары точек, удаленных друг от друга на расстояние, не превышающее d (см. рис. 17.13 рис 17.13 и программу 3.20). Определите, какое значение d следует выбрать, чтобы ожидаемое количество ребер было равно E. Протестируйте программу, как описано в упражнении 17.65 (для ненасыщенных графов) и в упражнении 17.66 (для насыщенных).

17.75. Напишите программу, которая генерирует в единичном интервале V случайные интервалы длиной d, а затем строит соответствующий интервальный граф. Определите, какое значение d следует выбрать, чтобы ожидаемое количество ребер было равно E. Протестируйте программу, как описано в упражнении 17.65 (для ненасыщенных графов) и в упражнении 17.66 (для насыщенных). Указание. Воспользуйтесь BST-деревом.

17.76. Напишите программу, которая случайным образом выбирает V вершин и E ребер из реального графа, найденного в упражнении 17.64. Протестируйте программу, как описано в упражнении 17.65 (для ненасыщенных графов) и в упражнении 17.66 (для насыщенных).

17.77. Один из способов определения транспортной системы -с помощью множества последовательностей вершин, причем каждая такая последовательность определяет путь, соединяющий вершины. Например, последовательность 0-9-3-2 определяет ребра 0-9, 9-3 и 3-2. Напишите программу, которая строит граф по данным из входного файла, содержащего в каждой строке одну последовательность символьных имен. Подготовьте входные данные, которые позволят использовать эту программу для построения графа, соответствующего схеме московского метро.

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

17.79. Примените преобразования, описанные в упражнениях 17.34—17.37, к различным графам (см. упражнения 17.63—17.76) и сведите в таблицу количество вершин и ребер, удаленных при каждом таком преобразовании.

17.80. Реализуйте конструктор для программы 17.1, который позволит клиентам строить граф разделения без необходимости вызова функции для каждого неявного ребра. То есть количество вызовов функции, необходимых клиенту для построения графа, должно быть пропорционально сумме размеров групп. Разработайте эффективную реализацию этого измененного АТД (на основе структур данных с использованием групп, но без неявных ребер).

17.81. Приведите строгую верхнюю границу количества ребер любого графа разделения для N различных групп с к человек в каждой группе.

17.82. Начертите графы в стиле рис 17.16, которые содержат V вершин, пронумерованных от 0 до V—1, и ребра, соединяющие вершину i с вершиной $$$\lfloor i/2\rfloor$$$, для V= 8, 16 и 32.

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

17.84. Добавьте в интерфейс АТД из упражнения 17.83 функцию, которая поддерживает операцию объединить (графы), и напишите реализации для представлений матрицей смежности и списками смежности. Примечание: В результирующем графе должны присутствовать все вершины и ребра каждого исходного графа, но вершины, имеющиеся в обоих графах, должны присутствовать только один раз. Кроме того, нужно удалять параллельные ребра.

Простые, эйлеровы и гамильтоновы пути

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

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

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

Программа 17.16 представляет собой непосредственное решение этой задачи. В ее основу положен поиск в глубину (depth-first search) -фундаментальный принцип обработки графов, на котором мы кратко останавливались в и 5, и который будет подробно рассмотрен в .

Программа 17.16. Поиск простого пути

Этот класс использует рекурсивную функцию поиска в глубину searchR, которая находит простой путь, соединяющий две заданные вершины графа, и предоставляет функцию-член exists, позволяющую клиенту проверить, существует ли путь между вершинами. Для двух заданных вершин v и w функция searchR проверяет каждое ребро v-t, смежное с v, может ли оно быть первым ребром на пути к w. Вектор visited, индексированный именами вершин, предотвращает повторное использование любой вершины, то есть находятся только простые пути.

  template <class Graph>
  class sPATH
    { const Graph G;
      vector <bool> visited;
      bool found;
      bool searchR(int v, int w)
        { if ( v == w) return true;
          visited[v] = true;
          typename Graph::adjIterator A(G, v);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (!visited[t])
              if (searchR(t, w)) return true;
          return false;
        }
    public:
      sPATH(const Graph G, int v, int w) :
        G(G), visited(G.V(), false)
        { found = searchR(v, w); }
      bool exists() const
        { return found; }
   };
      

Этот алгоритм основан на приватной функции-члене, которая определяет, существует ли простой путь из вершины v в вершину w, проверяя для каждого ребра v-t, инцидентного v, существует ли простой путь из t в w, который не проходит через v. В нем используется вектор, индексированный именами вершин, который позволяет отметить v, чтобы ни при каком рекурсивном вызове не проверялся путь, проходящий через v.

Программа 17.16 просто проверяет, существует ли путь. Как можно добавить в нее возможность вывода ребер, составляющих путь? Рекурсивный подход предлагает простое решение:

Добавить оператор вывода ребра v-t сразу же после того, как рекурсивный вызов в функции searchR находит путь из t в w.

В вызове функции searchR в конструкторе поменять местами v и w.

Одно лишь первое изменение приводит к тому, что путь из v в w будет выведен в обратном порядке: если вызов searchR(t, w) находит путь из t в w (и выводит составляющие его ребра в обратном порядке), то для вывода пути из v в w остается вывести путь t-v. Второе изменение меняет порядок: чтобы вывести ребра, составляющие путь из v в w, нужно вывести путь из w в v в обратном порядке. (Этот прием годится только для неориентированных графов.) Такую стратегию можно применить и для реализации функции АТД, которая вызывает клиентскую функцию для каждого ребра пути (см. упражнение 17.88).

На рис 17.17 приведен пример динамики рекурсии. Как и в случае любой другой рекурсивной программы (вообще-то любой программы с вызовами функций), получить подобную трассировку нетрудно. Чтобы внести такую возможность в программу 17.16, можно добавить переменную depth для отслеживания глубины рекурсии (ее значение увеличивается на 1 при входе и уменьшается на 1 при выходе), а затем вставить в начало рекурсивной функции код вывода depth пробелов перед нужной информацией (см. упражнения 17.86 и 17.87).

(рис 17.17) Трассировка поиска простого пути

Данная трассировка показывает, как работает рекурсивная функция из программы 17.16при вызове searchR(G, 2.6) для поиска простого пути из вершины 2 в вершину 6 на графе, который показан в верхней части рисунка. Для каждого рассматриваемого ребра выводится отдельная строка с отступом на один уровень больше для каждого рекурсивного вызова. Для проверки ребра 2-0 нужен вызов searchR(G,0,6). Для его завершения необходимо проверить ребра 0-1, 0-2 и 0-5. Для проверки ребра 0-1 нужен вызов searchR(G, 1.6) -для его завершения необходимо проверить ребра 1-0 и 1-2, которые не приводят к рекурсивным вызовам, поскольку вершины 0 и 2 уже помечены. В этом примере функция находит путь 2-0-5-4-6.

Лемма 17.2. Путь, соединяющий две заданных вершины графа, можно найти за линейное время.

Рекурсивная функция поиска в глубину из программы 17.16 представляет собой доказательство по индукции, что функция АТД определяет, существует ли искомый путь. Это доказательство легко расширить, чтобы установить, что в худшем случае программа 17.16 проверяет все элементы матрицы смежности в точности один раз. Аналогично можно показать, что подобная программа для списков смежности проверяет в худшем случае все ребра графа в точности два раза (по разу в каждом направлении). $$$\blacksquare$$$

Когда в контексте алгоритмов на графах мы используем термин линейное (linear), это означает, что количественное значение не превосходит величины V+E (размер графа), умноженной на некоторый постоянный коэффициент. Как было сказано в конце раздела 17.5, такое значение также обычно не превосходит размера представления графа, умноженного на некоторый постоянный коэффициент. Формулировка свойства 17.2 позволяет, как обычно, использовать представление списками смежности для разреженных графов и представление матрицей смежности для насыщенных графов. Термин " линейный " нельзя применять для описания алгоритма, который использует матрицу смежности и выполняется за время, пропорциональное V² (даже если он линеен по отношению к размеру представления графа) -кроме случаев, когда граф является насыщенным. Вообще-то при представлении разреженного графа матрицей смежности линейный по времени алгоритм невозможен для любой задачи обработки графов, в которой нужно перебрать все ребра.

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

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

(рис 17.18) Гамильтонов цикл

В графе, приведенном вверху, имеется гамильтонов цикл 0-6-4-2-1-3-5-0, который проходит через каждую вершину точно один раз и возвращается в первоначальную вершину. В нижнем графе такого цикла нет.

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

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

Лемма 17.3. Рекурсивный поиск гамильтонова цикла может потребовать экспоненциального времени.

Доказательство. Рассмотрим граф, у которого ). Следовательно, общее количество рекурсивных вызовов равно V! или примерно (V/e)V , что больше любой константы в степени V. $$$\blacksquare$$$

(рис 17.19) Трассировка поиска гамильтонова цикла

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

Полученные нами реализации -программа 17.16 для поиска простых путей, и программа 17.17 для поиска гамильтоновых путей -очень похожи друг на друга. При отсутствии путей выполнение обеих программ прекращается, когда все элементы вектора visited становятся равными true. Но почему времена выполнения этих программ так разительно отличаются? Программа 17.16 гарантированно выполняется за короткое время, поскольку она заносит true по крайней мере в один элемент вектора visited при каждом вызове searchR. А программа 17.17 может снова сбрасывать элементы вектора visited, поэтому гарантировать ее быстрое выполнение невозможно.

При поиске простых путей программой 17.16 мы знаем, что если существует путь из v в w, то его можно найти, выбрав одно из ребер v-t, исходящих из v; то же самое верно и в отношении гамильтоновых путей. Но на этом сходство заканчивается.

Программа 17.17. Гамильтонов путь

Данная рекурсивная функция отличается от функции из программы 17.16 всего лишь двумя моментами, во-первых, она принимает длину искомого пути в качестве третьего аргумента и завершается успешно, только если находит путь длины V; во-вторых, при неудачном завершении она сбрасывает маркер visited.

Если заменить этой функцией рекурсивную функцию в программе 17.16 и добавить третий аргумент G.V()-1 в вызов функции searchR, то будет найден гамильтонов путь. Однако не рассчитывайте, что поиск завершится для любых графов, кроме самых маленьких (см. текст).

  bool searchR(int v, int w, int d)
    { if (v == w) return (d == 0) ;
      visited[v] = true;
      typename Graph::adjIterator A(G, v);
      for (int t = A.beg(); !A.end(); t = A.nxt())
        if (!visited[t])
          if (searchR(t, w, d-1)) return true;
      visited[v] = false;
      return false;
    }
      

Если невозможно найти простой путь из t в w, то это значит, что простого пути из v в w, проходящего через t, не существует; но в процессе поиска гамильтонова пути ситуация иная. Может случиться так, что в графе нет гамильтонова пути в вершину w, который начинается с ребра v-t, но есть путь, который начинается с v-x-t для некоторой вершины x. И придется выполнить рекурсивные вызовы из t, соответствующие каждому пути, который ведет в нее из вершины v. Короче говоря, нам может понадобиться проверить каждый путь в графе.

Задумайтесь, насколько медленно работает алгоритм с факториальным временем выполнения. Если, к примеру, граф с 15 вершинами можно обработать за 1 секунду, то обработка графа с 19 вершинами будет длиться целые сутки, более года для 21 вершины и 6 столетий, если граф содержит 23 вершины. Увеличение быстродействия компьютера практически не помогает. Если повысить быстродействие компьютера в 200 000 раз, то для решения рассматриваемой задачи с 23 вершинами ему потребуется больше суток. Но затраты на обработку графа со 100 или 1000 неимоверно велики, не говоря уже о графах, с которыми нам приходится сталкиваться на практике. Потребуются многие миллионы страниц этой книги, чтобы только записать количество веков, необходимых для обработки графа, содержащего миллионы вершин.

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

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

(рис 17.20) Примеры эйлерового цикла и пути

Граф в верхней части рисунка содержит эйлеров цикл 0-1-2-0-6-4-3-2-4-5-0 , который использует все ребра в точности один раз. Граф в нижней части рисунка не содержит такого цикла, однако содержит эйлеров путь 1-2-0-1-3-4-2-3-5-4-6-0-5.

Эйлеров путь. Существует ли путь, соединяющий две заданных вершины, который проходит точно один раз через каждое ребро графа? Путь не обязательно должен быть простым, и вершины можно посещать многократно. Если путь начинается и заканчивается в одной и той же вершине, то это задача поиска эйлерова цикла (Euler tour). Существует ли циклический путь, который проходит через каждое ребро графа в точности один раз? В следствии из леммы 17.4 будет показано, что задача поиска такого пути эквивалентна задаче поиска цикла в графе, полученного добавлением в граф ребра, соединяющего две соответствующие вершины. Два небольших примера приведены на рис 17.20.

Первым эту классическую задачу исследовал Л.Эйлер (L. Euler) в 1736 г. Некоторые математики считают, что начало изучению графов и теории графов положила работа Эйлера по решению одного из случаев этой проблемы -задачи о Кенигсбергских мостах (см. рис 17.21). В немецком городе Кенигсберг (с 1946 г. -Калининград, входящий в состав России) берега реки и острова соединяли семь мостов, и жители этого города обнаружили, что они не могут пройти по всем семи мостам, не пройдя по одному из них дважды. Отсюда и берет начало задача поиска эйлерова цикла.

(рис 17.21) Кенигсбергские мосты

Широко известная задача, которую изучал Эйлер, связана с городом Кенигсберг, где на разветвлении реки Прегель находится остров, соединенный с берегами семью мостами (вверху). Существует ли способ пройти семь мостов во время непрерывной прогулки по городу, не проходя ни по одному из них дважды? Если обозначить остров цифрой 0, берега реки -цифрами 1 и 2, а промежуток между рукавами реки -цифрой 3 и определить ребра, соответствующие каждому мосту, то получится мультиграф, показанный внизу. Требуется найти такой путь, который использует каждое ребро точно один раз.

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

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

Лемма 17.4. Граф содержит эйлеров цикл тогда и только тогда, когда он связен и все его вершины имеют четную степень.

Доказательство. Для упрощения доказательства мы допустим существование петель и параллельных ребер, хотя доказательство нетрудно изменить так, чтобы показать, что эта лемма справедлива и для простых графов (см. упражнение 17.94).

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

Чтобы доказать достаточность, воспользуемся методом индукции по количеству ребер. Это утверждение заведомо выполняется для графов, у которых нет ребер. Рассмотрим любой связный граф с более чем одним ребром, в котором степени всех вершин четные. Предположим, что начиная с произвольной вершины, мы продвигаемся по любому ребру, после чего удаляем его. Мы продолжаем двигаться, пока не окажемся в вершине, у которой нет ребер. Этот процесс должен когда-нибудь завершиться, поскольку на каждом шаге удаляется одно ребро, но что получится в результате? Посмотрите на примеры на рис 17.22. Сразу ясно, что этот процесс должен закончиться на исходной вершине тогда и только тогда, когда она имеет нечетную степень в начале процесса.

Один из возможных вариантов состоит в том, что мы прошли весь цикл -тогда доказательство завершено. Иначе все вершины оставшегося графа имеют четные степени, но он может оказаться несвязным. Однако в соответствии с индуктивным предположением каждый его связный компонент содержит эйлеров цикл. Более того, только что удаленный циклический путь связывает эти циклы в эйлеров цикл исходного графа, и остается пройти по этому циклическому пути, отклоняясь на обходы эйлеровых циклов для каждого связного компонента. Каждое такое отклонение представляет собой эйлеров цикл, заканчивающийся в вершине, с которой он начинался. Учтите, что каждое такое отклонение может многократно касаться циклического пути (см. упражнение 17.98). В таком случае обход отклонения выполняется только один раз (например, когда мы впервые с ним сталкиваемся). $$$\blacksquare$$$

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

Доказательство. Эта формулировка эквивалентна формулировке леммы 17.4 для графа, построенного добавлением ребра между двумя вершинами нечетной степени (на концах пути). $$$\blacksquare$$$

(рис 17.22) Частичные циклы

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

Отсюда следует, например, что никто не может пройти через все мосты Кенигсберга так, чтобы не пройти по одному мосту дважды, поскольку все четыре вершины в соответствующем графе имеют нечетные степени (см. рис 17.21).

Как было установлено в разделе 17.5, все степени вершин можно найти за время, пропорциональное E для представления списками смежности или множеством ребер, либо за время, пропорциональное V² для представления графа матрицей смежности -или же в составе представления графа можно использовать вектор, индексированный именами вершин, который содержит степени вершин (см. упражнение 17.42). При наличии такого вектора можно проверить, выполняется ли лемма 17.4, за время, пропорциональное V. Программа 17.18 реализует эту стратегию и показывает, что проверка, имеется ли в заданном графе эйлеров цикл, представляет собой достаточно простую вычислительную задачу. Это важно, потому что интуитивно совсем непонятно, проще ли эта задача, чем определение, существует ли гамильтонов путь в заданном графе.

Программа 17.18. Существование эйлерова цикла

Этот класс позволяет клиентским программам проверить существование эйлерова цикла в графе. Вершины v и w рассматриваются как приватные члены данных, чтобы клиенты могли вывести путь с помощью функции-члена show (которая использует приватную функцию-член tour) (см. программу 17.19).

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

  template <class Graph>
  class ePATH {
    Graph G;
    int v, w;
    bool found;
    STACK <int> S;
    int tour(int v);
  public:
    ePATH(const Graph G, int v, int w) :
      G(G), v(v), w(w)
      { DEGREE<Graph> deg(G);
        int t = deg[v] + deg[w];
        if ((t % 2) != 0) { found = false; return; }
        for (t = 0; t < G.V(); t++)
          if ((t != v)  (t != w))
            if ((deg[t] % 2) != 0)
              { found = false; return; }
        found = true;
      }
    bool exists() const
      { return found; }
    void show();
  } ;
      

А теперь предположим, что требуется найти сам эйлеров цикл. Прямая рекурсивная реализация (поиск пути с помощью проверки ребра с последующим рекурсивным вызовом для поиска пути в остальной части графа) обеспечивает ту же факториальную производительность, что и программа 17.17. Но с такой производительностью мириться не хочется, ведь проверить существование такого пути довольно легко, и мы попробуем отыскать более приемлемый алгоритм. Можно избежать факториальной зависимости с помощью проверки за фиксированное время, можно ли использовать конкретное ребро (в отличие от неизвестных затрат при рекурсивных вызовах), но мы оставим этот подход на самостоятельную проработку (см. упражнения 17.96 и 17.97).

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

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

(рис 17.23) Поиск эйлерова цикла методом удаления циклов

Здесь на простом графе показано, как программа 17.19 находит эйлеров цикл с началом и концом в вершине 0. Жирные ребра -те, которые входят в цикл, содержимое стека показано под каждой диаграммой, а списки смежности для ребер, не попавших в цикл, показаны слева от диаграмм.

Сначала программа добавляет в искомый цикл ребро 0-1 и удаляет его из списков смежности (из двух мест) (верхняя левая диаграмма, списки слева). Затем она точно так же добавляет в цикл ребро 1-2 (вторая сверху левая диаграмма). Потом она поворачивает назад в 0, но продолжает строить цикл 0-5-4-6-0 и возвращается в вершину 0, у которой больше не осталось инцидентных ребер (вторая сверху правая диаграмма). Затем она выталкивает из стека изолированные вершины 0 и 6, так что вверху стека остается вершина 4, и начинает цикл с 4 (третья сверху правая диаграмма), проходит через вершины 3, 2 и возвращается в 4, после чего из стека выталкиваются все уже изолированные вершины 4 , 2 , 3 и т.д. Последовательность вытолкнутых из стека вершин определяет эйлеров цикл 0-6-4-2-3-4-5-0-2-1-0 для всего графа.

Лемма 17.5. Если в графе существует эйлеров цикл, то его можно найти за линейное время.

Полное доказательство этой леммы методом индукции мы оставляем на самостоятельную проработку (см. упражнение 17.100). По существу, после первого вызова функции path в стеке содержится путь от v до w, а оставшаяся часть графа (после удаления изолированных вершин) состоит из связных компонентов меньших размеров (имеющих по крайней мере одну общую вершину с найденным на текущий момент путем), которые также содержат эйлеровы циклы. Изолированные вершины выталкиваются из стека, и с помощью функции path продолжается аналогичный поиск эйлеровых циклов, которые содержат неизолированные вершины. Каждое ребро графа заталкивается в стек (и выталкивается из него) в точности один раз, поэтому общее время выполнения пропорционально E. $$$\blacksquare$$$

Программа 17.19. Поиск эйлерова пути с линейным временем выполнения

Данная реализация функции show для класса из программы 17.18 выводит эйлеров путь между двумя заданными вершинами, если он существует. В отличие от многих других наших реализаций, этот код основан на реализации АТД Graph с конструктором копирования, поскольку он создает копию графа, а потом уничтожает эту копию, удаляя ребра из графа при выводе пути. При наличии линейной по времени реализации функции remove (см. упражнение 17.46) функция show выполняется за линейное время. Приватная функция-член tour проходит по ребрам циклического пути, удаляет их и помещает вершины в стек, чтобы выявить наличие боковых циклов (см. текст). Главный цикл вызывает функцию tour до тех пор, пока существуют боковые циклы.

  template <class Graph>
  int ePATH<Graph>::tour(int v)
    { while (true)
        { typename Graph::adjIterator A(G, v);
          int w = A.beg();
          if (A.end()) break;
          S.push(v);
          G.remove(Edge(v, w));
          v = w;
        }
      return v;
   }
  template <class Graph>
  void ePATH<Graph>::show()
    { if (found) return;
      while (tour(v) == v  !S.empty())
        { v = S.pop(); cout << "-" << v; }
      cout << endl;
    }
      

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

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

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

Упражнения

17.85. Покажите в стиле упражнения 17.17 трассу рекурсивных вызовов (и пропущенные вершины) при поиске программой 17.16 пути из вершины 0 в вершину 5 в графе 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

17.86. Добавьте в рекурсивную функцию из программы 17.16 возможность вывода трассы, как на рис 17.17, используя для этого глобальную переменную, как описано в тексте.

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

17.88. Используя метод, описанный в тексте, напишите реализацию класса sPATH с общедоступной функцией-членом, которая вызывает клиентскую функцию для каждого ребра на пути из v в w, если такой путь существует.

17.89. Измените программу 17.16 так, чтобы она принимала третий аргумент d и проверяла существование пути, соединяющего вершины u и v, длина которого больше d. А именно, значение search(v, v, 2) должно быть ненулевым тогда и только тогда, когда v содержится в некотором цикле.

17.90. Эмпирически определите вероятность того, что программа 17.16 найдет путь между двумя наугад выбранными вершинами в различных графах (см. упражнения 17.63—17.76) и вычислите среднюю длину пути, найденного для различных видов графов.

17.91. Рассмотрим графы, заданные следующими четырьмя наборами ребер:

0-10-20-31-31-42-52-93-64-74-85-85-96-76-97-8

0-10-20-31-30-32-55-63-64-74-85-85-96-76-98-8

0-11-21-30-30-42-52-93-64-74-85-85-96-76-97-8

4-17-96-27-35-00-20-81-63-96-32-81-59-84-54-7

Какие из этих графов содержат эйлеровы циклы? Какие из них содержат гамильтоновы циклы?

17.92. Сформулируйте необходимые и достаточные условия существования в ориентированном графе (ориентированного) эйлерова цикла.

17.93. Докажите, что каждый связный неориентированный граф содержит двунаправленный эйлеров цикл.

17.94. Измените доказательство леммы 17.4, чтобы оно годилось и для графов с параллельными ребрами и петлями.

17.95. Покажите, что если добавить еще один мост, то задача о Кенигсбергских мостах будет иметь решение.

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

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

17.98. Приведите пример, когда граф, оставшийся после первого вызова функции path из программы 17.19, будет несвязным (в графе, содержащем эйлеров цикл).

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

17.100. Приведите полное доказательства методом индукции, что алгоритм поиска эйлерова пути, выполняемый за линейное время, который описан в тексте и реализован в программе 17.19, правильно находит эйлеров цикл.

17.101. Найдите количество содержащих эйлеров цикл графов с V вершинами для максимального числа V, для которого вы можете выполнять реальные вычисления.

17.102. Эмпирически определите для различных графов среднюю длину пути, найденного первым вызовом функции path в программе 17.19 (см. упражнения 17.63—17.76). Вычислите вероятность того, что этот путь является циклом.

17.103. Напишите программу, которая вычисляет последовательность из 2n + n -1 битов, в которой никакие две последовательности из n следующих подряд битов не совпадают. (Например, для n = 3 таким свойством обладает последовательность 0001110100.) Примечание: Найдите эйлеров цикл в орграфе де Брюйна.

17.104. Покажите в стиле рис 17.19 трассу рекурсивных вызовов (и пропущенные вершины) при поиске программой 17.16 гамильтонова цикла в графе

3-71-47-80-55-23-82-90-64-92-66-4.

17.105. Добавьте в программу 17.17 возможность вывода гамильтонова цикла, если он будет найден.

17.106. Найдите гамильтонов цикл в графе

1-22-54-22-60-83-01-33-61-01-44-04-66-52-6

6-99-03-14-39-24-96-97-95-09-77-34-50-57-8,

либо докажите, что он не существует.

17.107. Найдите количество содержащих гамильтонов цикл графов с V вершинами для максимального значения V, для которого вы можете выполнять реальные вычисления.

Задачи обработки графов

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

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

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

Легкие

Разрешимые

Трудноразрешимые

Решение неизвестно.

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

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

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

Легкая задача обработки графа -это задача, которую можно решить с помощью компактных, элегантных и эффективных программ, к виду которых мы уже успели привыкнуть в частях I—IV Время выполнения таких программ зачастую линейно в худшем случае или ограничено полиномами низких степеней от количества вершин и/или ребер. Обычно, как мы делали в других областях, можно установить, что проблема относится к категории легких, если можно разработать примитивное решение, которое, будучи слишком медленным для крупных графов, вполне приемлемо для графов небольших, а иногда и средних размеров. Затем, зная, что задача имеет легкое решение, мы ищем эффективные решения, которыми можно воспользоваться на практике, и пытаемся выбрать наилучшее из них. Ярким примером легких задач может служить задача поиска эйлерова цикла, рассмотренная в разделе 17.7, а в лекциях 18—22 мы познакомимся с множеством других таких задач. Ниже приведены наиболее яркие примеры таких задач.

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

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

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

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

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

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

Планарность. Можно ли начертить заданный граф так, чтобы никакие линии, представляющие ребра, не пересекались? Поскольку вершины можно помещать в любое место, эта задача разрешима для многих графов, но она все-таки неразрешима для многих других графов. Замечательный классический результат, известный как теорема Куратовского, позволяет легко проверить, является ли граф планарным (плоским). Эта теорема утверждает: единственный вид графов, который невозможно изобразить на чертеже без пересечения ребер -это графы, содержащие некоторый подграф, который после удаления из него вершин степени 2, становится изоморфным одному из графов, изображенных на . Алгоритм Тарьяна не обязательно позволяет получить реальную компоновку, он просто утверждает, что такой чертеж существует. Как было сказано в разделе 17.1, построение наглядного чертежа графа для приложений, в котором вершины графа не обязательно соответствуют реальным объектам внешнего мира, является сложной исследовательской задачей. (рис 17.24) Подграфы, запрещенные в планарных графах Ни один из изображенных здесь графов нельзя начертить на плоскости без пересечения его ребер; это невозможно и для всех графов, которые содержат любой из этих графов в качестве подграфа (после того удаления вершин степени 2). Однако для всех остальных графов подобное изображение возможно.

Сопоставление. Каким является наибольшее подмножество ребер графа, в котором никакие два ребра не связаны с одной и той же вершиной? Известно, что эта классическая задача имеет решение, при этом она решается за время, пропорциональное полиномиальной функции от V и E, однако исследователям никак не удается найти быстродействующий алгоритм для работы с крупными графами. Эту задачу проще решить при наличии различных ограничений. Например, задача распределения студентов по свободным позициям в различных общественных организациях есть задача двудольного сопоставления (bipartite matching): имеются два различных вида вершин (студенты и организации), и нас интересуют только те ребра, которые соединяют вершину одного вида с вершиной другого вида. Решение этой задачи приведено в

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

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

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

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

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

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

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

Трудноразрешимая (intractable) задача обработки графов -это задача, для которой не известен алгоритм, гарантирующий ее решение за приемлемый промежуток времени. Для многих таких задач характерно то, что для ее решения можно использовать примитивный метод, когда мы пытаемся вычислить решение, перебирая все варианты, а трудноразрешимыми они считаются потому, что таких вариантов слишком много. Этот очень широкий класс задач включает в себя многие важные задачи, решение которых хотелось бы знать. Для описания задач этого класса применяется термин NP-трудный (NP-hard). Многие специалисты уверены, что эффективных алгоритмов решения этих задач не существует. В части VIII мы более подробно рассмотрим, что послужило причиной для такой уверенности и этого термина. Хрестоматийным примером NP-трудной задачи обработки графов является задача поиска гамильтонова цикла, рассмотренная в разделе 17.7, а также задачи из приведенного ниже списка.

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

Задача раскраски. Существует ли такой способ закрашивания каждой вершины графа одним из к цветов, чтобы ни одно ребро не соединяло две вершины одинакового цвета? Эта классическая задача легко решается для ), но является NP-трудной при к = 3.

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

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

Эти задачи сформулированы как задачи существования -нужно определить, существует или не существует подграф конкретного типа. В некоторых задачах требуется определить размер наибольшего подграфа конкретного типа, а это можно сделать, сведя задачу существования к проверке существования подграфа размера к с нужным свойством с последующим бинарным поиском наибольшего из них. Однако на практике часто бывает нужно отыскать полное решение, которое в общем случае найти гораздо труднее. Например, известная теорема четырех красок (four color theorem) утверждает, что можно воспользоваться четырьмя цветами для раскраски всех вершин планарного графа таким образом, что ни одно ребро не будет соединять две вершины одного и того же цвета. Однако эта теорема ничего не говорит о том, как это сделать для конкретного плоского графа: знание о том, что такая раскраска существует, ничем не может помочь в поиске полного решения задачи. Другой известный пример -задача коммивояжера (traveling salesperson problem), в которой требуется определить путь обхода вершин взвешенного графа минимальной длины. Эта задача относится к тому же классу задач, что и задача поиска гамильтонова цикла, и нисколько не легче ее: если мы не можем найти эффективное решение задачи поиска гамильтонова пути, то не можем рассчитывать и на то, что найдем решение задачи коммивояжера. Как правило, сталкиваясь с трудными задачами, мы работаем с простейшими вариантами, которые в состоянии решить. Задачи существования в принципе соответствуют этому правилу, но, как мы увидим в части VIII, они играют важную роль в теории.

Перечисленные выше задачи -лишь небольшая часть из тысяч известных NP-трудных задач. Как мы увидим в части VIII, они возникают во всех видах вычислительных приложений. Особенно много таких задач возникает при обработке графов, так что мы будем учитывать их существование на протяжении всей книги.

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

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

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

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

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

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

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

Трудность классификации задач обработки графов

	Л	Р	Т	?
Неориентированные графы
Связность	v
Общая связность		v
Эйлеров цикл	v
Гамильтонов цикл			v
Двудольное сопоставление	v
Максимальное сопоставление		v
Планарность		v
Максимальная клика			v
Раскраска 2 цветами	v
Раскраска 3 цветами			v
Кратчайшие пути	v
Самые длинные пути			v
Вершинное покрытие			v
Изоморфизм				v
Орграфы
Транзитивное замыкание	v
Сильная связность	v
Цикл нечетной длины	v
Цикл четной длины		v
Взвешенные графы
Минимальное остовое дерево	v
Задача коммивояжера			v
Сети
Кратчайшие пути (неотрицательные веса)	v
Кратчайшие пути (отрицательные веса)			v
Максимальный поток	v
Распределение		v
Поток минимальной стоимости		v

Обозначения:
Л	Легкая -известен эффективный классический алгоритм решения
Р	Разрешимая -решение существует (трудно получить реализацию)
Т	Трудноразрешимая -эффективное решение неизвестно (NP-трудная задача)
?	Неизвестно, существует ли решение

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

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

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

Упражнения

17.108. Докажите, что ни один из графов, изображенных на рис 17.24, не может быть планарным.

17.109. Напишите клиентскую функцию АТД графа, которая выясняет, содержит ли заданный граф один из графов, показанных на рис 17.24. Для этой цели воспользуйтесь примитивным алгоритмом, который проверяет все возможные подмножества из пяти вершин для клики и все возможные подмножества из шести вершин для полного двудольного графа. Примечание: Этой проверки недостаточно для доказательства планарности графа, поскольку она игнорирует условие, что удаление вершин степени 2 в некоторых подграфах может дать один из двух запрещенных подграфов.

17.110. Начертите граф

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6,

в котором нет пересекающихся ребер, либо докажите, что такой чертеж невозможен.

17.111. Найдите такой способ назначить один из трех цветов каждой вершине графа

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6,

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

17.112. Решите задачу независимого множества для графа

3-71-47-80-55-23-02-90-64-92-6

6-41-58-29-08-34-52-31-63-57-6.

17.113. Каков размер максимальной клики в графе де Брюйна порядка п?