Графы и алгоритмы. Структуры данных. Модели вычислений

Графы и алгоритмы

2-е издание, исправленное

Алексеев В.Е.
Таланов В.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 519.17+510.58+681.142
ББК 3
А47
Графы и алгоритмы. Структуры данных. Модели вычислений / Алексеев В.Е., Таланов В.А. - M.:
Национальный Открытый Университет “ИНТУИТ”, 2016 (Основы информационных технологий)
ISBN 5-9556-0066-3

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

(c) ООО “ИНТУИТ.РУ”, 2006-2016
(c) Алексеев В.Е., Таланов В.А., 2006-2016

3

Начальные понятия теории графов

Начальные понятия теории графов. Определение графа. Графы и бинарные отношения.
Откуда берутся графы. Число графов. Смежность, инцидентность, степени. Некоторые
специальные графы. Графы и матрицы. Взвешенные графы. Изоморфизм. Инварианты.
Операции над графами. Локальные операции. Подграфы. Алгебраические операции.

Начальные понятия теории графов

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

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

Определение графа

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

Рис. 1.1. 

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

4

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

, 
, 
. Таким образом, когда мы отвлекаемся от всех несущественных

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

Термин “граф” неоднозначен, это легко заметить, сравнивая приводимые в разных
книгах определения. Однако во всех этих определениях есть кое-что общее. В любом
случае граф состоит из двух множеств - множества вершин и множества ребер, причем
для каждого ребра указана пара вершин, которые это ребро соединяет. Вершины и
ребра называются элементами графа. Здесь будут рассматриваться только конечные
графы, то есть такие, у которых оба множества конечны. Чтобы получить законченное
определение графа того или иного типа, необходимо уточнить еще три момента.

1. Ориентированный или неориентированный?

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

Если да, то говорят, что рассматриваются упорядоченные пары (порядок
элементов в паре важен), если нет - неупорядоченные. Если ребро  соединяет
вершину  с вершиной  и пара 
 считается упорядоченной, то это ребро

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

2. Кратные ребра.

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

3. Петли.

Ребро, которому поставлена в соответствие пара вида 
, то есть ребро,

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

5

Рис. 1.2. 

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

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

множество, 
 - множество неупорядоченных пар различных элементов из .

Элементы множества  называются вершинами графа, элементы множества 
 - его

ребрами.

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

В дальнейшем термин “граф” мы будем употреблять в смысле “обыкновенный граф“, а
рассматривая другие типы графов, будем специально это оговаривать.

Множество вершин графа 
 будем обозначать через 
, множество ребер - 
,

число вершин - 
, число ребер - 
.

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

граф 
 с 
, 
. Если граф не слишком велик, то более наглядно

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

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

Рис. 1.3. 

6

Графы и бинарные отношения

Напомним, что бинарным отношением на множестве 
 называется любое

подмножество 
 множества 
, состоящего из всевозможных упорядоченных пар

элементов множества 
. Каждому такому отношению можно поставить в соответствие

граф отношения 
. Сравнивая с тем, что говорилось выше об определениях

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

для любого 
 пара 
 принадлежит 
, и антирефлексивным, если ни одна

такая пара не принадлежит 
. Отношение называется симметричным, если из 

 следует, что 
. В графе антирефлексивного и симметричного

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

Откуда берутся графы

Легко найти примеры графов в самых разных областях науки и практики. Сеть дорог,
трубопроводов, электрическая цепь, структурная формула химического соединения,
блок-схема программы - в этих случаях графы возникают естественно и видны
“невооруженным глазом”. При желании графы можно обнаружить практически где
угодно. Это наглядно показано в книге Д.Кнута [D.E.Knuth, “The Stanford GraphBase”] -
графы извлекаются из романа “Анна Каренина”, из картины Леонардо да Винчи, из
материалов Бюро Экономического Анализа США и из других источников.

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

Рис. 1.4. 

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

7

любого семейства множеств 
 можно построить граф пересечений с

множеством вершин 
, в котором ребро 
 имеется тогда и только тогда,

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

пересечений некоторого семейства множеств.

Рис. 1.5. 

Число графов

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

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

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

Теорема 1. 
.

Смежность, инцидентность, степени

Если в графе имеется ребро 
, то говорят, что вершины  и  смежны в этом

графе, ребро  инцидентно каждой из вершин , , а каждая из них инцидентна этому
ребру.

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

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

быстрого просмотра окрестности вершины.

Число вершин, смежных с вершиной , называется степенью вершины  и
обозначается через 
.

8

Если сложить степени всех вершин некоторого графа, то каждое ребро внесет в эту
сумму вклад, равный 2, поэтому справедливо следующее утверждение:

Теорема 2. 
.

Это равенство известно как “лемма о рукопожатиях”. Из него следует, что число
вершин нечетной степени в любом графе четно.

Вершину степени  называют изолированной.

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

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

Некоторые специальные графы

Рассмотрим некоторые особенно часто встречающиеся графы.

Пустой граф - граф, не содержащий ни одного ребра. Пустой граф с множеством
вершин 
 обозначается через 
.

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

Граф 
, в частности, имеет одну вершину и ни одного ребра. Очевидно, 
.

Будем считать также, что существует граф 
, у которого 
.

Цепь ( путь ) 
 - граф с множеством вершин 
 и множеством ребер 

.

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

Все эти графы при 
 показаны на рис. 1.6

Рис. 1.6. 

Графы и матрицы

Пусть 
 - граф с  вершинами, причем 
. Построим квадратную

матрицу 
 порядка , в которой элемент 
, стоящий на пересечении строки с

9

номером  и столбца с номером , определяется следующим образом:

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

Другая матрица, ассоциированная с графом - это матрица инцидентности. Для ее
построения занумеруем вершины графа числами от 1 до , а ребра - числами от 1 до 

. Матрица инцидентности  имеет  строк и 
 столбцов, а ее элемент 
 равен 1,

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

Рис. 1.7. 

Для ориентированного графа матрица инцидентности определяется несколько иначе:
ее элемент 
 равен 1, если вершина  является началом ребра , и равен 
, если она

является концом этого ребра, и он равен , если эта вершина и это ребро не
инцидентны друг другу.

Взвешенные графы

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

10