![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 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, Свойства и типы графов
Более подробно мы исследуем деревья в главе 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 вершинами равно 2V{V- 1)/2 (число различных способов выбора подмножеств из V(V— l)/2 возможных ребер). Полный подграф называется кликой (clique). Большинство графов, с какими нам приходится сталкиваться на практике, содержат лишь небольшую часть всех возможных ребер. Чтобы представить это понятие в числовом выражении, положим насыщенность (density) графа равной среднему значению степеней его вершин, т.е. 2E/V. Насыщенный граф есть граф, средняя степень вершин которого про- РИСУНОК 17.4. ПОЛНЫЕ ГРАФЫ Представленные на диаграмме полные графы, в которых каждая вершина соединена с любой другой вершиной, содержат, соответственно, 10, 15, 21, 28 и 36 ребер (снизу вверх). Каждый граф, содержащий от 5 до 9 вершин (существует более чем 68 миллиардов таких графов) есть подграф одного из этих графов. Часть 5. Алгоритмы на графах
Информация о том, с каким графом мы имеем дело, с плотным или разреженным, в общем случае является ключевым фактором выбора эффективного алгоритма обработки графа. Например, для решения той или иной задачи мы можем разработать два алгоритма, причем первому из них для ее решения понадобится V2 действий, а другому - Е lgE действий. Эти формулы показывают, что второй алгоритм лучше подходит для разреженных алгоритмов, в то время как первому алгоритму следует отдавать предпочтение при обработке плотного графа. Например, плотный граф с многими миллионами ребер может иметь всего лишь несколько тысяч вершин: в данном случае V2 и E суть величины одного порядка, при этом быстродействие алгоритма V2 в 20 раз выше, чем быстродействие алгоритма Е lgE. С другой стороны, разреженный граф с миллионами ребер обладает миллионами вершин, следовательно, алгоритм E lgE будет в миллионы раз быстрее алгоритма V2. Мы можем прийти к различным компромиссам на основании более подробного изучения этих формул, но в общем случае для практических целей вполне достаточно терминов разреженный (sparse) и насыщенный (dense), чтобы можно было получить представление об основных рабочих характеристиках требуемых алгоритмов. При анализе алгоритмов обработки графов мы полагаем, что значения V/E ограниче-
ны сверху небольшой константой, благодаря чему мы можем упростить такие выражения как V(V+E) до VE. Это предположение подтверждается только в тех случаях, когда число ребер невелико по сравнению с числом вершин, что представляет собой редкую ситуацию. Как правило, число ребер намного превосходит число вершин (V/E намного меньше 1).
Двухдольный граф (bipartite graph) есть граф, множество вершин которого можно разделить на такие два подмножества, что любое ребро соединяют вершину одного подмножества только с вершиной другого подмножества. На рис. 17.5 приводится пример двухдольного графа. Двухдольные графы естественным образом возникают во многих ситуациях, таких как задачи поиска соответствий, описанные в начале этой главы. Любой подграф двухдольного графа сохраняет это свойство. Графы, которые мы рассматривали до сих пор, носят название неориентированных графов (undirected graphs). В ориентированных графах (directed graphs), из-
|