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

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

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

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

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

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

Мы можем начертить граф, обозная точками его вершины и соединяя эти точки ли­ниями, которые будут служить ребрами. Чертеж дает нам некоторое представление о структуре графа; но это представление может оказаться обманчивым, ибо определение графа дается вне зависимости от его представления. Например, два чертежа и список ре­бер, которые приводятся на рис. 17.1, представляют один и тот же граф, поскольку этот граф - всего лишь (неупорядоченное) множество его вершин и (неупорядоченное) мно­жество его ребер (пар вершин), и ничего более. Достаточно рассматривать граф просто как некоторое множество ребер, однако мы будем изучать и другие представления, ко­торые лучше других подходят для использования в качестве базы для структур данных типа граф, рассматриваемых в разделе 17.4.

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

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

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

РИСУНОК 17.1. ТРИ РАЗЛИЧНЫХ ПРЕДСТАВЛЕНИЯ ОДНОГО ИТОГО ЖЕ ГРАФА

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

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

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

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

Определение 17.2. Путь (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 (путь из некоторой вершины в ту же вершину, не содержащий ребер, отлич­ных от петель). Помимо этого соглашения, в графе, не содержащем параллельных ребер и петель, в котором кон­кретная пара вершин однозначно определяет некоторое ребро, пути должны состоять, по меньшей мере, из двух различных вершин, а циклы должны содержать, по мень­шей мере, три различных ребра и три различных верши­ны.

РИСУНОК 17.2. ПРИМЕРЫ ИЗОМОРФИЗМА ГРАФОВ

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

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

РИСУНОК 17.3. ТЕРМИНОЛОГИЯ, УПОТРЕБЛЯЕМАЯ В ТЕОРИИ ГРАФОВ

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

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

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

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

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

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

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

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

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

■ G содержит V— 1 ребро и представляет собой связный
граф.

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

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

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

Графы, у которых присутствуют все ребра, называются полными графами (complete graph) (см. рис. 17.4). Мы опреде­ляем дополнение (complement) графа G методом построения, взяв для начала полный граф, имеющий то же число вершин, что и исходный графа G, и удалив из него все ребра графа G. Объединением (union) двух графов является граф, порожденный объединением множеств ребер этих графов. Объединение гра­фа и его дополнения есть полный граф. Все графы, имеющие V вершин суть подграфы полного графа с V вершинами. Об­щее число различных графов с V вершинами равно 2^{V{V- 1)/2} (число различных способов выбора подмножеств из V(V— l)/2 возможных ребер). Полный подграф называется кликой (clique).

Большинство графов, с какими нам приходится сталки­ваться на практике, содержат лишь небольшую часть всех возможных ребер. Чтобы представить это понятие в числовом выражении, положим насыщенность (density) графа равной среднему значению степеней его вершин, т.е. 2E/V. Насыщен­ный граф есть граф, средняя степень вершин которого про-

РИСУНОК 17.4. ПОЛНЫЕ ГРАФЫ

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

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

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

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

При анализе алгоритмов обработки графов мы полагаем, что значения V/E ограниче-

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

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

Графы, которые мы рассматривали до сих пор, но­сят название неориентированных графов (undirected graphs). В ориентированных графах (directed graphs), из-