'%2СЖй 5
Алгоритмы
на графах
17
Свойства и типы графов
18
Поиск на графах
19
Орграфы и ориентированные
ациклические графы
20
Минимальные остовные леревья
21
Кратчайшие пути
22
Потоки в сетях

Свойства и типы
графов
Многие вычислительные приложения естественным
образом используют не только набор элементов
(items), но также и набор соединений (connections) между па¬
рами таких элементов. Отношения, которые вытекают из
этих соединений, немедленно вызывают множество есте¬
ственных вопросов. Существует ли путь от одного такого
элемента к другому, вдоль этих соединений? В какие дру¬
гие элементы можно перейти из заданного элемента? Ка¬
кой путь от одного элемента к другому считается наилуч¬
шим?
Чтобы смоделировать подобную ситуацию, мы пользу¬
емся объектами, которые называются графами (graphs). В
этой главе мы подвергнем подробному анализу основные
свойства графов, тем самым подготавливая базу для изуче¬
ния всевозможных алгоритмов, которые помогут ответить
на вопросы, подобные сформулированным выше. Эти ал¬
горитмы эффективно используют различные вычислитель¬
ные средства, которые рассматривались в частях 1—4. Они
также служат той базой, без которой невозможно подсту¬
питься к проблемам, возникающим в важных приложени¬
ях, и решение которых нельзя представить без привлече¬
ния солидной алгоритмической технологии.
Теория графов, будучи крупной ветвью комбинаторной
математики, интенсивно изучалась в течение не одной сот¬
ни лет. Было выявлено много важных и полезных свойств
графов, однако многие задачи еще ждут своего решения.
В этой книге, признавая, что еще многое предстоит изу¬
чить, мы извлекаем из всего массива обширных знаний о
графах только то, что нам необходимо понять, и исполь¬
зуем из всего разнообразия фундаментальных алгоритмов
лишь те из них, которые представляют несомненную прак¬
тическую ценность.

Глава 17. Свойства и типы графов
Как и множество других предметных областей, которые приходилось изучать, алго¬
ритмическое исследование графов возникло сравнительно недавно. И хотя некоторые
фундаментальные алгоритмы открыты давно, все же большая часть интереснейших ал¬
горитмов получена в течение нескольких последних десятилетий. Даже простейшие ал¬
горитмы на графах позволяют получить полезные компьютерные программы, а изучае¬
мые нами нетривиальные алгоритмы относятся к числу наиболее элегантных и
интересных из известных алгоритмов.
Чтобы продемонстрировать все разнообразие приложений, использующих графы
для обработки данных, начнем исследования алгоритмов в этой благодатной области с
рассмотрения нескольких примеров.
Географические карты. Путешественник, прежде чем отправиться в путь, желает
получить ответ на вопросы типа: "Какой маршрут из Принстона в Сан-Хосе потребует
наименьших расходов?" Пассажир, для которого время дороже денег, хотел бы получить
ответ на такой вопрос: "Каким путем быстрее всего добраться из Принстона в Сан-
Хосе?" Чтобы ответить на вопросы подобного рода, мы выполняем обработку инфор¬
мации, характеризующей соединения (пути следования) между элементами (городами и
населенными пунктами).
Гипертекст. Когда мы просматриваем Web-каталоги, мы сталкиваемся с документа¬
ми, содержащими различные ссылки (соединения) на другие документы, и переходим
от документа к документу, щелкая мышью на этих ссылках. Сама по себе "всемирная
паутина" представляет собой граф, в котором в качестве элементов выступают доку¬
менты, а соединения суть связи. Алгоритмы обработки графов являются важными ком¬
понентами поисковых механизмов, которые помогают определить местоположение ин¬
формации в Web.
Микросхемы. Микросхемы содержат такие элементы, как транзисторы, резисторы,
конденсаторы, которые связаны между собой сложнейшим образом. Для управления
машинами, изготавливающими микросхемы, и для проверки, выполняют ли эти цепи
заданные функции, используются компьютеры. Мы хотим получить ответы на простые
вопросы наподобие "Имеются ли в цепи условия для короткого замыкания?" и на бо¬
лее сложные вопросы, такие как "Можно ли скомпоновать микросхему на кристалле
таким образом, чтобы шины не пересекались?". В данном случае, ответ на первый
вопрос зависит только от свойств соединений (шин), в то время как для ответа на
второй вопрос потребуется подробная информация о шинах, элементах, которые эти
шины соединяют, и физических ограничениях, накладываемых кристаллом.
Составление расписаний. Производственный процесс требует решения различных
задач под воздействием некоторого множества ограничений, по условиям которых ре¬
шение одной задачи не может быть начато до тех пор, пока не будет завершено реше¬
ние другой задачи. Мы представляем эти ограничения в виде соединений между этими
задачами (элементами), при этом перед нами возникает задача составления расписаний
(,scheduling) в ее классическом виде: как построить временной график решения задач
таким образом, чтобы удовлетворить заданным ограничениям и завершить данный
процесс за минимально возможное время?

Часть 5. Алгоритмы на графах
Транзакции. Телефонная компания поддерживает базу данных телефонного трафи¬
ка. В этом случае соединения представляют телефонные вызовы. Мы заинтересованы
в том, чтобы знать все, что касается характера структуры соединений, ибо хотим
проложить провода и установить коммутаторы так, чтобы эффективно справляться с
телефонным трафиком. Еще одним примером может служить то, как финансовое уч¬
реждение отслеживает операции купли/продажи на рынке. Соединение в рассматрива¬
емом случае представляет собой передачу денег продавцом покупателю. Знание
свойств структуры соединений в данном случае помогает лучше понять особенности
рынка.
Задачи поиска сочетаний. Студенты обращаются с заявлениями на замещение долж¬
ностей в таких общественных организациях, как общественные клубы, университеты
или высшие медицинские учебные заведения. Элементы соответствуют студентам и ин¬
ститутам, тогда как связи соответствуют приложениям. Мы хотим найти методы, уста¬
навливающие соответствие между вакантными должностями и заинтересованными в их
получении студентами.
Сети. Сеть вычислительных машин состоит из взаимосвязанных узлов, которые по¬
сылают, передают дальше и получают сообщения различных видов. Мы заинтересова¬
ны не только в обеспечении возможности получать сообщения из любого другого
узла, но и в том, чтобы эта возможность сохранялась для всех пар узлов и в случае
изменения конфигурации сети. Например, возможно, потребуется проверить работу
конкретной сети, чтобы убедиться в отсутствии некоторого небольшого подмножества
узлов или соединений, настолько критичных для работы всей сети, что их утрата мо¬
жет привести к разъединению остальных пар узлов.
Структура программы. Компилятор строит графы для представления структуры вы¬
зовов крупной системы программного обеспечения. Элементами в этом случае являют¬
ся различные функции или программные модули, составляющие систему; соединения
отождествляются либо с возможностью того, что одна функция может вызвать другую
функцию (статический анализ), или с фактическим вызовом, когда система находится
в рабочем состоянии (динамический анализ). Нам нужно выполнить анализ графа,
чтобы определить, как достичь максимальной эффективности при выделении систем¬
ных ресурсов для конкретной программы.
Эти примеры демонстрируют, насколько широк диапазон приложений, для кото¬
рых граф служит подходящей абстракцией, и, соответственно, диапазон вычислитель¬
ных задач, с которыми доведется столкнуться при работе с графами. Эти задачи явля¬
ются главной темой настоящей книги. Во многих подобного рода приложениях, с
которыми приходится иметь дело на практике, объем обрабатываемых данных поисти-
не огромен, так что именно эффективность алгоритма решает, будет ли вообще рабо¬
тать соответствующее приложение.
Нам уже приходилось сталкиваться с графами в части 1. В самом деле, первые ал¬
горитмы, которые мы изучали самым подробным образом, т.е. алгоритмы объедине¬
ния-поиска, описанные в главе 1, представляют собой простейшие алгоритмы на гра¬
фах. Мы также использовали графы в главе 3 в качестве иллюстрации приложения
двухмерных массивов и связных списков, в главе 5 графы послужили иллюстрацией

Глава 17. Свойства и типы графов
отношений между рекурсивными программами и фундаментальными структурами дан¬
ных. Любая связная структура данных может быть представлена в виде графа, а неко¬
торые известные алгоритмы обработки деревьев и других связных структур представ¬
ляют собой частные случаи алгоритмов на графах. Назначение данной главы
заключается в том, чтобы обеспечить контекст для изучения широкого набора алгорит¬
мов на графах, от простейших, описанных в части 1, до очень сложных, описываемых
в главах 18-22.
Как всегда, мы хотим знать, какой из возможных алгоритмов решения конкретной
задачи обладает максимальной эффективностью. Задача изучения рабочих характерис¬
тик алгоритмов на графах представляет собой достаточно сложную проблему, что
можно объяснить следующими причинами:
■	Стоимость алгоритма зависит не только от свойств множества элементов, но
также и от многочисленных свойств соединений (и глобальных свойств графа,
обусловленных свойствами соединений).
■	Разработка точных моделей типов графов, с которыми, возможно, придется
столкнуться, сопряжена с большими трудностями.
Мы часто исходим из предположения, что используемым алгоритмам на графах
придется функционировать в условиях, наиболее неблагоприятных для их рабочих ха¬
рактеристик, даже если во многих случаях на практике такие предположения пред¬
ставляют собой пессимистическую оценку. К счастью, как мы убедимся далее, многие
из этих алгоритмов оптимальны и не требуют больших непроизводительных затрат. В
отличие от них, существуют алгоритмы, которые затрачивают одинаковые ресурсы на
обработку всех графов заданного размера. Мы можем с достаточной степенью точнос¬
ти предсказать, как поведут себя такие алгоритмы в конкретных условиях. В тех слу¬
чаях, когда такие предсказания невозможны, нам придется уделить особое внимание
свойствам графов различных типов, которые, в соответствии с нашими ожиданиями,
проявятся в конкретных практических ситуациях, и оценить, как эти свойства могут
повлиять на производительность выбранных алгоритмов.
Мы начнем с изучения основных определений графов и свойств графов, а также с
освоения стандартной терминологии, которая используется для их описания. Затем мы
дадим определения интерфейсов АТД (ADT, abstract data type — Абстрактный тип дан¬
ных), которыми будем пользоваться при изучении алгоритмов на графах, двух наибо¬
лее важных структур данных, применяемых для представления графов — матрицы
смежности (adjacency-matrix) и списков смежных вершин (adjacency-lists), а также различ¬
ных подходов к реализации базовых функций над АТД (АТД-функций). Затем мы рас¬
смотрим клиентские программы, способные строить случайные графы, которые могут
использоваться для тестирования разработанных алгоритмов и для изучения свойств
графов. Весь этот материал служит фундаментом, позволяющим применять алгоритмы
обработки графов для решения трех классических задач, связанных с поиском путей в
графах, которые служат также иллюстрацией того, что по сложности задачи обработки
графов существенно отличаются друг от друга даже в тех случаях, когда различия
между ними далеко не очевидны. Эта глава завершается обзором наиболее важных за¬
дач обработки графов, которые будут рассматриваться в этой книге, в контексте
сложности их решения.

Часть 5. Алгоритмы на графах
17.1.	Глоссарий
С графами связана обширная терминология. Большинство употребляемых терминов
имеют прямое определение, и для удобства ссылок целесообразно рассматривать их в
каком-то одном месте, а именно - в данном разделе. Некоторые из понятий мы уже
употребляли в главе 1 при изучении базовых алгоритмов, другие останутся невостребо¬
ванными до тех пор, пока мы не перейдем к изучению соответствующих им новейших
алгоритмов в главах 18-22.
Определение 17.1. Граф есть некоторое множество вершин и некоторое множество
ребер, соединяющих пары различных вершин (любую пару вершин может соединять
максимум одно ребро).
Мы используем цифры от 0 до V-1 в качестве имен вершин графа, состоящего из
V	вершин. Основная причина выбора именно этой системы обозначений заключается в
том, что мы получаем быстрый доступ к информации, соответствующей каждой вер¬
шине, путем индексирования массивов. В разделе 17.6 будет рассмотрена программа,
которая применяет таблицу идентификаторов с тем, чтобы установить отображение
"один-к-одному" с целью связать V произвольных имен с вершин с V целыми числами
в диапазоне от 0 до V-1. Имея в своем распоряжении такую программу, мы можем
трактовать индексы как имена вершин (для удобства обозначений) без ущерба для
универсальности рассуждений. Иногда мы будем предполагать, что множество вершин
определено неявно, взяв за основу для определения графов множество ребер и учиты¬
вая только те вершины, которые закреплены, по меньшей мере, за одним ребром. Во
избежание громоздких выражений, как то "граф, состоящий из 10 вершин со следую¬
щим набором ребер”, мы часто явно не указываем числа вершин, если оно следует из
контекста. Далее будем придерживаться соглашения, в соответствии с которым число
вершин в заданном графе всегда обозначается через К а число ребер - через Е.
В качестве стандартного определения графа (с которым первый раз довелось стол¬
кнуться в главе 5) будет принято определение 17.1, но при этом заметим, что в нем
использованы два технических упрощения. Во-первых, оно не позволяет дублировать
ребра (математики иногда называют такие ребра параллельными (parallel), а граф, кото¬
рый может содержать такие ребра, мультиграфом (multigraph)). Во-вторых, оно не до¬
пускает ребер, замыкающихся на одну и ту же вершину; такое ребро называются пет¬
лей (self-loop). Графы, в которых нет параллельных ребер или петлей, иногда называют
простыми графами (simple graph).
Мы употребляем понятия простых графов в формальных определениях, поскольку
таким путем легче выразить их основные свойства, а также ввиду того, что параллель¬
ные ребра и петли во многих приложениях не нужны. Например, мы можем ограни¬
чить число ребер простого графа заданным числом вершин.
Свойство 17.1. Граф, состоящий из Vвершин, содержит не более V(V — \) / 2 ребер.
Доказательство. Всего существует V2 возможных пар вершин, но в это число вхо¬
дят V петель, при этом связи между различными вершинами учитываются дважды,
следовательно, максимальное число ребер равно (V — V) / 2 = V(V - \) / 2. ■

Глава 17. Свойства и типы графов
Эти ограничения не имеют места в условиях существования параллельных ребер:
граф, не принадлежащий к категории простейших, может содержать всего лишь две
вершины и миллиарды ребер, соединяющие их (или даже одну вершину и миллиарды
петель).
В некоторых приложениях удаление параллельных ребер и петель можно рассмат¬
ривать как задачу обработки данных, которую должны решать сами приложения. В
других приложениях, возможно, вообще не имеет смысла проверять, представляет ли
заданный набор ребер простой граф. На протяжении данной книги, там, где удобно
проводить анализ конкретного приложения или разрабатывать алгоритм с применени¬
ем расширенного определения графа, использующего понятия параллельных ребер
или петель, мы будем это делать. Например, петли играют важнейшую роль в класси¬
ческом алгоритме, который будем изучаться в разделе 17.4; параллельные ребра широ¬
ко используются в приложениях, которые будут рассматриваться в главе 22. В общем
случае из контекста ясно, в каком смысле используется термин "граф*': "простой
граф”, "мультиграф" или "мультиграф с петлями”.
У математиков термины вершина (vertex) и узел (node) взаимозаменяемы, но мы бу¬
дем главным образом пользоваться термином вершина при обсуждении графов и тер¬
мином узел при обсуждении представлений графов, например, структур данных на
языке С. Обычно мы полагаем, что у вершины есть имя, и что она может нести дру¬
гую связанную с ней информацию. Аналогично, слова дуга (arc), ребро (edge) и связь
(link) также широко используются математиками для описания абстракций, предусмат¬
ривающих соединение двух вершин, однако мы последовательно будем употреблять
термин ребро при обсуждении графов и термин связь при обсуждении структур данных
на языке С.
Если имеется ребро, соединяющее две вершины, будем говорить, что обе эти вер¬
шины смежные (adjacent) по отношению друг к другу, а ребро инцидентно (incident on)
этим вершинам. Степень (degree) вершины есть число ребер, инцидентных этой верши¬
не. Мы употребляем обозначение v-w для обозначения ребра, соединяющего вершины v и
w; обозначение w-v представляет собой еще одно возможное обозначение того же ребра.
Подграф (subgraph) представляет собой подмножество ребер некоторого графа (и
связанных с ними вершин), которые сами образуют граф. По условиям многих вычис¬
лительных задач требуется определить на некотором графе подграфы различных типов.
Если выделить некоторое подмножество вершин графа и все ребра графа, соединяю¬
щие пары вершин этого подмножества, то такое подмножество называется индуциро¬
ванным подграфом (induced subgraph), ассоциированным с этими вершинами.
Мы можем начертить граф, обозная точками его вершины и соединяя эти точки
линиями, которые будут служить ребрами. Чертеж дает нам некоторое представление
о структуре графа; но это представление может оказаться обманчивым, ибо определе¬
ние графа дается вне зависимости от его представления. Например, два чертежа и
список ребер, которые приводятся на рис. 17.1, представляют один и тот же граф,
поскольку этот граф - всего лишь (неупорядоченное) множество его вершин и (не¬
упорядоченное) множество его ребер (пар вершин), и ничего более. Достаточно рас¬
сматривать граф просто как некоторое множество ребер, однако мы будем изучать и
другие представления, которые лучше других подходят для использования в качестве
базы для структур данных типа граф, рассматриваемых в разделе 17.4.

Часть 5. Алгоритмы на графах
Перенесение вершин заданного графа на плоскость
и вычерчивание этих вершин и соединяющих их ребер
позволяет получить чертеж графа (graph drawing). Воз¬
можно множество вариантов размещения вершин, сти¬
лей изображения ребер, поскольку эстетические требо¬
вания, предъявляемые к изображению, практически
бесконечны. Алгоритмы построения чертежей, соблю¬
дающие различные естественные ограничения, подверг¬
лись интенсивному изучению, в результате которых
были получены многие удачные приложения (см. раздел
ссылок). Например, одно из простейших ограничений
есть требование, согласно которому ребра не должны
пересекаться. Планарный граф (planar graph) принадле¬
жит к числу тех, которые можно построить на плоско¬
сти без пересечения ребер. В зависимости от того, яв¬
ляется ли граф планарным (плоским) или нет,
возникает заманчивая задача, которой мы коротко
коснемся в разделе 17.8. Возможность построения чер¬
тежа графа представляет собой благодатное поле для
исследований, в то же время на практике построить
хороший чертеж графа не так-то просто. Многие гра¬
фы с очень большим числом вершин и ребер, являются
абстрактными объектами, чертеж которых неосуще¬
ствим.
В некоторых приложениях, например, выполняю¬
щих анализ географических карт или электрических
схем, для построения чертежа графа требуется обшир¬
ная информационная база, поскольку их вершины со¬
ответствуют точкам на плоскости, а расстояния между
ними должны быть выдержаны в определенном масш¬
табе; во множестве других приложений, имеющих дело
с графами, представляющими отношения или времен-
РИСУНОК 17.1. ТРИ РАЗЛИЧНЫХ
ПРЕДСТАВЛЕНИЯ ОДНОГО
ИТОГО ЖЕ ГРАФА
Граф определяется его вершина¬
ми и его ребрами, но не способом
его изображения на чертеже.
Оба чертежа изображают один
и тот же граф, этот же граф
представлен списком ребер
(внизу), при этом учитывается
то обстоятельство, что рас¬
сматриваемый граф содержит
13 вершин, помеченных номерами
от 0 до 12.
ные графики, они просто служат носителями информа¬
ции о связности, при этом даже не предъявляются какие-либо требования к геометри¬
ческому расположению вершин. Мы рассмотрим примеры алгоритмов, которые
используют геометрическую информацию, в главах 20 и 21, но сначала поработаем с
алгоритмами, которые вообще не используют геометрическую информацию. И все же
стоит еще раз подчеркнуть важность различения графа как абстрактного представле¬
ния множеством связей и любым конкретным представлением графа в виде чертежа
или на экране компьютера.
Если целиком сосредоточиться на исследовании свойств соединений, то мы, воз¬
можно, предпочтем рассматривать метки вершин как предназначенные только для
удобства обозначения, а два графа считать одинаковыми, если они отличаются друг от
друга только метками вершин. Два графа называются изоморфными (isomorphic), если
можно поменять метки вершин на одном из них таким образом, чтобы набор ребер

Глава 17. Свойства и типы графов 681
этого графа стал идентичным набору ребер другого гра¬
фа. Обнаружение изоморфизма двух графов представля¬
ет собой сложную вычислительную задачу (см. рис. 17.2
и упражнение 17.5). Ее сложность объясняется тем об¬
стоятельством, что существует V! способов обозначения
вершин, т.е. их слишком много, чтобы перепробовать
каждый из них. Поэтому, несмотря на потенциальную
привлекательность уменьшения числа различных струк¬
тур графа, которое становиться возможным, если рас¬
сматривать изоморфные графы как идентичные структу¬
ры, это делается довольно-таки редко.
Как и в случае деревьев, которые мы изучали в гла¬
ве 5, нас очень часто интересуют базовые структурные
свойства, которые мы можем определить, рассматривая
характерные последовательности ребер в графе.
Определение 17.2. Путь (path) в графе есть последо¬
вательность вершин, в которой каждая следующая вер¬
шина (после первой), является смежной с предыдущей
вершиной на этом пути. Все вершины и ребра, состав¬
ляющие простой путь (symple 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 (путь из некоторой
©-CD
РИСУНОК 17.2. ПРИМЕРЫ
ИЗОМОРФИЗМА ГРАФОВ
Два верхних графа изоморфны,
поскольку мы можем переобоз-
начить вершины таким
образом, что оба набора ребер
становятся идентичными
(чтобы сделать граф в середине
таким же, как и верхний граф,
поменяйте 10 на 4, 7 на 3,2 на
5, 3 на 1, 12 на 0, 5 на 2, 9 на
11, О на 12, 11 на 9, 1 на 7 и 4
на 10). Нижний граф не
изоморфен двум другим, по¬
скольку не существует такого
способа переименования его
вершин, чтобы множество его
ребер стало идентично анало¬
гичным множествам двух
первых графов.
вершины в ту же вершину, не содержащий ребер, от¬
личных от петель). Помимо этого соглашения, в графе, не содержащем параллельных
ребер и петель, в котором конкретная пара вершин однозначно определяет некоторое
ребро, пути должны состоять, по меньшей мере, из двух различных вершин, а циклы дол¬
жны содержать, по меньшей мере, три различных ребра и три различных вершины.

Часть 5. Алгоритмы на графах
Мы называем два простых пути непересекающимися (disjoint), если они не содержат
общих вершин, кроме, разве что, их конечных точек. Это условие несколько слабее,
нежели требование отсутствия в обоих путях каких-либо общих вершин, и более по¬
лезное, поскольку в этом случае мы можем соединять простые непересекающиеся
пути из 5 в г и из / в и и получать простой непересекающийся путь из s в w, если вер¬
шины s и и различны. Иногда используется термин непересекающиеся по вершинам (vertex
disjoint), чтобы отличить эту ситуацию от более сильного условия непересекающиеся по
ребрам (edge disjoint), когда мы требуем, чтобы пути не имели общих ребер.
Определение 17.3. Граф называется связным графом (connected graph), если суще¬
ствует путь из каждой вершины в любую другую вершину графа. Несвязный граф со¬
стоит из некоторого множества связных компонент (connected components), кото¬
рые представляют собой максимальные связные подграфы.
Термин максимальный связный подграф (maximal connected subgraph) означает, что не
существует пути из вершины такого подграфа в любую другую вершину графа, кото¬
рый не содержался бы в подграфе. Интуитивно, если бы вершины были физическими
объектами, такими как, скажем, узлы или бусинки, а ребра были бы физическими со¬
единениями, такими как, например, нити или провода, то в случае связного графа,
находясь в какой-либо его вершине, можно было бы смотать нить в один клубок, в то
время как несвязный граф распался бы на два или большее число таких клубков.
Определение 17.4. Ациклический связный граф называется деревом (tree) (см. главу
5). Множество деревьев называется лесом (forest). Остовное дерево (spanning tree)
связного графа есть подграф, который содержит все вершины этого графа и пред¬
ставляет собой единое дерево. Остовный лес (spanning forest) графа есть подграф,
который содержит все вершины этого графа и при этом является лесом.
Например, граф, изображенный на рис. 17.1, имеет три связных компоненты и ох¬
ватывается лесом 7-8 9-10 9-11 9-12 0-1 0-2 0-5 5-3 5-4 4-6 (существует
множество других остовных лесов). На рис. 17.3 эти и некоторые другие свойства
отображены на большем из графов.
РИСУНОК 17.3. ТЕРМИНОЛОГИЯ, УПОТРЕБЛЯЕМАЯ В ТЕОРИИ ГРАФОВ
Изображенный на рисунке граф содержит 55 вершин, 70 ребер и 3 связных компоненты. Одна из
связных компонент представляет собой дерево (справа). В графе имеется много циклов, один из этих
циклов выделен как крупная связная компонента (слева). На рисунке также показано остовное
дерево, содержащееся в связной компоненте небольшого размера (в центре). Как единое целое,
рассматриваемый граф не содержит остовных деревьев, поскольку он не является связным.

Глава 17. Свойства и типы графов
:1s
щ
т
ш
кем
Более подробно мы исследуем деревья в главе 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У(У~1)/2 (число различных
способов выбора подмножеств из V(V— 1) / 2 возможных
ребер). Полный подграф называется кликой (clique).
Большинство графов, с какими нам приходится сталки¬
ваться на практике, содержат лишь небольшую часть всех
возможных ребер. Чтобы представить это понятие в число¬
вом выражении, положим насыщенность (density) графа рав¬
ной среднему значению степеней его вершин, т.е. 2E/V.
Насыщенный граф (dense graph) есть граф, средняя степень
вершин которого пропорциональна К; разреженный граф
(sparse graph) есть граф, дополнение которого является на¬
сыщенным. Другими словами, мы считаем граф насыщенным, если число его ребер Е
пропорционально V2, и разреженным в противном случае. Такое "асимптотическое"
определение недостаточно точно характеризует тот или иной граф, однако общая кар¬
РИСУНОК 17.4. ПОЛНЫЕ ГРАФЫ
Представленные на рисунке
полные графы, в которых
каждая вершина, соединен¬
ная с любой другой верши¬
ной, содержат, соответ¬
ственно, 10, 15, 21, 28 и 36
ребер (снизу вверх). Каждый
граф, содержащий от 5 до 9
вершин (существует более
нем 68 миллиардов таких
графов) есть подграф одного
из этих графов.

Часть 5. Алгоритмы на графах
тина ясна: можно с уверенностью утверждать, что граф, который состоит из миллиона
вершин и десятков миллионов ребер есть разреженный граф, в то время как граф,
который состоит из нескольких тысяч вершин и миллионов ребер, есть плотный граф.
Мы еще можем рассчитывать на то, что нам удастся успешно выполнить обработку
разреженного графа, однако плотный граф с миллиардами вершин содержит несмет¬
ное количество ребер.
Информация о том, с каким графом мы имеем дело, с плотным или разреженным,
в общем случае является ключевым фактором выбора эффективного алгоритма обра¬
ботки графа. Например, для решения той или иной задачи мы можем разработать два
алгоритма, причем первому из них для ее решения понадобится V2 действий, а друго¬
му — Е lgЕ действий. Эти формулы показывают, что второй алгоритм лучше подходит
для разреженных графов, в то время как первому алгоритму следует отдавать пред¬
почтение при обработке плотных графов. Мы можем прийти к различным компромис¬
сам на основании более подробного изучения этих формул, но в общем случае для
практических целей вполне достаточно терминов разреженный (sparse) и насыщенный
(dense), чтобы можно было получить представление об основных рабочих характерис¬
тиках требуемых алгоритмов. Например, плотный граф со многими миллионами ребер
может иметь всего лишь несколько тысяч вершин: в данном случае V2 и Е суть вели¬
чины одного порядка, при этом быстродействие алгоритма V2 в 20 раз выше, чем бы¬
стродействие алгоритма Е lgЕ. С другой стороны, разреженный граф с миллионами
ребер обладает миллионами вершин, следовательно, алгоритм Е \gE будет в миллионы
раз быстрее алгоритма V2.
При анализе алгоритмов обработки графов мы полагаем, что значения V/Е ограни¬
чены сверху небольшой константой, благодаря чему мы можем упростить такие выра¬
жения, как V(V+ Е)у до VE. Это предположение подтверждается только в тех случаях,
когда число ребер невелико по сравнению с числом
вершин, что представляет собой редкую ситуацию.
Как правило, число ребер намного превосходит чис¬
ло вершин (V/Е намного меньше 1).
Двухдольный граф (bipartite graph) есть граф, мно¬
жество вершин которого можно разделить на такие
два подмножества, что любое ребро соединяют вер¬
шину одного подмножества только с вершиной дру¬
гого подмножества. На рис. 17.5 приводится пример
двухдольного графа. Двухдольные графы естествен¬
ным образом возникают во многих ситуациях, таких
как задачи поиска соответствий, описанные в нача¬
ле этой главы. Любой подграф двухдольного графа
сохраняет это свойство.
Графы, которые мы рассматривали до сих пор,
носят название неориентированных графов (undirected
graphs). В ориентированных графах (directed graphs),
известных еще как орграфы (digraph), ребра одно¬
направленные: мы рассматриваем пару вершин, оп¬
ределяющую конкретное ребро, как упорядоченную
РИСУНОК 17.5. ДВУХДОЛЬНЫЙ ГРАФ
Все ребра этого графа соединяют
вершины с нечетными номерами с
вершинами с четными номерами, то
есть, это двухдольный граф.
Нижняя диаграмма делает это
свойство очевидным.

Глава 17. Свойства и типы графов
(ordered) пару, которая определяет однонаправленную
смежность в том смысле, что возможность перехода из
первой вершины во вторую отнюдь не означает воз¬
можность перехода из второй вершины в первую. Мно¬
гие применения (например, графы, представляющие
Web, графы, используемые при составлении расписа¬
ний, или графы, применяемые для обработки телефон¬
ных звонков) естественным образом описываются в
виде орграфов.
Ребра в орграфах мы называем ориентированными
ребрами (directed edges), хотя в общем случае это разли¬
чие понятно из контекста (следует отметить, что неко¬
торые авторы для обозначения ориентированных ребер
применяют термин дуга (arc)). Первая вершина ориен¬
тированного ребра называется началом (source); вторая
вершина называется концом (destination). (Некоторые ав¬
торы используют, соответственно, термины голова
(head) и хвост (tail), чтобы отличить вершины ориенти¬
рованного графа, однако мы будем избегать таких обо¬
значений, поскольку мы употребляем эти же термины
при реализации структур данных.) На диаграммах мы
изображаем ориентированные ребра в виде стрелок,
направленных из начала в конец, и часто говорим, что
ребро указывает (points) на ту или иную вершину. Когда
мы используем обозначение w-v по отношению к орг¬
рафу, мы делаем это с целью показать, что ребро, ко¬
торое исходит из w и заходит в v, отличается от ребра
v-w, которое исходит из v и заходит в w. Мы также го¬
ворим о полустепени исхода (outdegree) и полустепени за¬
хода (indegree) некоторой вершины (соответственно,
число ребер, для которых она служит началом, и число
ребер, для которых она служит концом).
Иногда целесообразно рассматривать неориенти¬
рованный граф как орграф, у которого имеются два
ориентированных ребра (по одному в каждом направ-
РИСУНОК 17.6. ДВА ОРГРАФА
Чертеж вверху есть представ¬
ление графа, приведенного в
качестве примера на рис. 17.1,
интерпретируемое как ориенти¬
рованный граф, при этом мы
рассматриваем ребра как
упорядоченные пары и изобража¬
ем их в виде стрелок, ведущих из
первой вершины во вторую.
Этот граф является DAG-
графом. Чертеж в нижней
части рисунка есть представле¬
ние неориентированного графа,
показанного на рис. 17.1,
который может служить
иллюстрацией способа, обычно
выбираемого нами для представ¬
ления неориентированных
графов: в виде орграфа, в
котором каждому соединению
соответствуют два ребра (по
одному в каждом направлении).
лении); в других случаях полезно рассматривать неори
ентированный граф просто как некоторую совокупность соединений. Обычно для
ориентированных и неориентированных графов мы используем одно и то же пред¬
ставление (рис. 17.6), о чем подробно пойдет речь в разделе 17.4. Иначе говоря, в об¬
щем случае мы поддерживаем два представления каждого ребра неориентированных
графов, каждое из них указывает в одном из направлений, так что мы имеем возмож¬
ность сразу же ответить на вопросы типа "Какие вершины соединены с вершиной v?"
Глава 19 посвящена изучению структурных свойств орграфов; в общем случае они
более сложные, чем соответствующие свойства неориентированных графов. Направлен¬
ный цикл (directed cycle) в орграфе - это цикл, в котором пары смежных вершин появ-

Часть 5. Алгоритмы на графах
ляются в порядке, устанавливаемом ребрами графа. Граф DAG (Directed Acyclic Graph -
ориентированный ациклический граф) есть орграф, который не содержит направленных
циклов. DAG-граф (ациклический орграф) и дерево (ациклический неориентирован¬
ный граф) - это отнюдь не тождественные понятия. Иногда мы обращаемся к базово¬
му неориентированному графу (underlying undirected graph), лежащему в основе орграфа,
подразумевая под ним неориентированный граф, определяемый тем же множеством
ребер, при этом, однако, эти ребра не рассматриваются как ориентированные.
В главах 20-22 содержится, главным образом, анализ алгоритмов решения различ¬
ных вычислительных задач, связанных с использованием графов, в которых в виде
вершин и ребер представлена другая информация. В случае взвешенного графа (weighted
graph) с каждым ребром мы связываем числа (weights - веса), которые в общем случае
представляют собой расстояние либо стоимость. Мы также можем присвоить вес каж¬
дой вершине либо несколько весов каждой вершине и каждому ребру. Ориентирован¬
ные взвешенные графы будем называть сетями (networks). В главе 22 исследуются клас¬
сические задачи на сетях и алгоритмы, решающие эти задачи.
Уже из главы 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.	Исследуйте граф
3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
Определите число связных компонент, постройте остовный лес, составьте список
простых путей, содержащих, по меньшей мере, три вершины, а также список всех
неизоморфных циклов (см. упражнение 17.1).
о 17.5. Исследуйте граф, заданный следующими четырьмя наборами ребер:
0-1
0-2
0-3
1-3
1-4
2-5
2-9
3-6
4-7
4-8
5-8
5-9
6-7
6-9
7-8
0-1
0-2
0-3
0-3
1-4
2-5
2-9
3-6
4-7
4-8
5-8
5-9
6-7
6-9
7-8
0-1
1-2
1-3
0-3
0-4
2-5
2-9
3-6
4-7
4-8
5-8
5-9
6-7
6-9
7-8
4-1
7-9
6-2
7-3
5-0
0-2
0-8
1-6
3-9
6-3
2-8
1-5
9-8
4-5
4-7
Какие из этих графов изоморфны друг другу? Какие из них планарны?