Экстремальные задачи теории графов и Интернет

А.М. РАЙГОРОДСКИЙ

ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ  
ТЕОРИИ ГРАФОВ  
И ИНТЕРНЕТ

А.М. Райгородский
Экстремальные задачи теории графов и Интернет: Учебное
пособие / А.М. Райгородский – Долгопрудный: Издательский Дом «Интеллект», 2012. – 104 с.

ISBN 9785915591270

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

Книга рассчитана на всех, кто интересуется современными приложениями математики в области анализа данных. Она будет полезна студентам и
аспирантам технических ВУЗов, а также исследователям и разработчикам
больших сетей – Интернета, биологических и социальных сетей.

ISBN 9785915591270
© 2012, А.М. Райгородский
© 2012, ООО Издательский Дом
«Интеллект», оригиналмакет,
оформление

ОГЛАВЛЕНИЕ

Л е к ц ия 1. Основные объекты теории графов . . . . . . . . . . .
6

1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2. Основные объекты теории графов . . . . . . . . . . . . . . . . . . . . . .
7
1.2.1. Графы, орграфы и пр. . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2.2. Маршруты в графах . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.2.3. Связность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.2.4. Независимые множества и клики . . . . . . . . . . . . . . . . . .
11
1.3. Двудольные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.3.1. Определение и мотививировка . . . . . . . . . . . . . . . . . . . .
13
1.3.2. Связь с задачей о покрытии . . . . . . . . . . . . . . . . . . . . . .
14

Л е к ц и я 2. Несколько базовых алгоритмов на графах . . . . . . . .
16

2.1. Алгоритм Хопкрофта–Карпа . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2. Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.3. Алгоритм Беллмана–Форда . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.4. Реализация последовательностей чисел степенями вершин графа .
21

Задачи к лекциям 1 и 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25

Л е к ц и я 3. Системы общих представителей . . . . . . . . . . . . . . . .
29

3.1. Определение системы общих представителей . . . . . . . . . . . . . .
29
3.2. Верхняя оценка для размера минимальной с.о.п. . . . . . . . . . . . .
29
3.3. Доказательство теоремы 3.2.1. . . . . . . . . . . . . . . . . . . . . . . . .
31
3.4. Нижняя оценка для размера минимальной с.о.п. . . . . . . . . . . . .
33
3.5. Доказательство теоремы 3.4.1 . . . . . . . . . . . . . . . . . . . . . . . .
33
3.6. Уточнения теоремы 3.4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35

Л е к ц и я 4. Размерность Вапника–Червоненкиса . . . . . . . . . . . .
36

4.1. Размерность Вапника–Червоненкиса: определение и примеры . . .
36

Оглавление

4.2. Постановка задачи об ε-сетях . . . . . . . . . . . . . . . . . . . . . . . .
38
4.3. Формулировки результатов . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.4. Идея доказательства теоремы 4.3.1 и комментарии . . . . . . . . . .
40
4.5. О покрытии графов более простыми графами . . . . . . . . . . . . . .
41

Задачи к лекциям 3 и 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43

Л е к ц и я 5. Числа Рамсея . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46

5.1. Числа Рамсея: определения и формулировки результатов . . . . . .
46
5.2. Доказательство теоремы 5.1.2. . . . . . . . . . . . . . . . . . . . . . . . .
48
5.3. Доказательство следствия 5.1.2 . . . . . . . . . . . . . . . . . . . . . . .
49
5.4. Конструктивные оценки чисел Рамсея . . . . . . . . . . . . . . . . . . .
49
5.5. Доказательство теоремы 5.4.1 . . . . . . . . . . . . . . . . . . . . . . . .
51
5.6. Доказательство следствия 5.4.1 . . . . . . . . . . . . . . . . . . . . . . .
52
5.7. Двудольные числа Рамсея . . . . . . . . . . . . . . . . . . . . . . . . . . .
53

Л е к ц и я 6. Случайные графы . . . . . . . . . . . . . . . . . . . . . . . . . .
54

6.1. Случайные графы: определение . . . . . . . . . . . . . . . . . . . . . . .
54
6.2. Случайные графы: простейшие свойства . . . . . . . . . . . . . . . . .
55
6.3. Связность случайного графа . . . . . . . . . . . . . . . . . . . . . . . . .
56
6.4. Хроматическое число случайного графа . . . . . . . . . . . . . . . . . .
58
6.5. Законы нуля и единицы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59

Задачи к лекциям 5 и 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60

Л е к ц и я 7. Алгоритмы в некоторых «трудных» задачах теории
графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62

7.1. О задачах отыскания хроматического числа, числа независимости
и кликового числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
7.2. Алгоритм Кривелевича–Ву: формулировки результатов . . . . . . . .
63
7.3. Доказательство теоремы 7.2.1. . . . . . . . . . . . . . . . . . . . . . . . .
65
7.3.1. Вспомогательные определения и факты . . . . . . . . . . . . . .
65
7.3.2. Построение алгоритма . . . . . . . . . . . . . . . . . . . . . . . . .
65
7.3.3. Пояснения к работе алгоритма . . . . . . . . . . . . . . . . . . . .
66

Л е к ц и я 8. Рамсеевские алгоритмы . . . . . . . . . . . . . . . . . . . . . .
68

8.1. Еще об отыскании клик . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
8.2. Несколько слов о Рамсеевском алгоритме . . . . . . . . . . . . . . . .
69
8.3. Уточнение Рамсеевского алгоритма . . . . . . . . . . . . . . . . . . . . .
71

Задачи к лекциям 7 и 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73

Оглавление
5

Л е к ц и я 9. Обходы графов и их приложения . . . . . . . . . . . . . . .
74

9.1. Эйлеровы графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
9.2. Эйлеровы графы и последовательности де Брёйна . . . . . . . . . . .
76
9.3. Гамильтоновы графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
9.3.1. Определение гамильтоновости и связь с эйлеровостью . . . .
78
9.3.2. Необходимые и достаточные условия гамильтоновости . . . .
79
9.3.3. Алгоритмы поиска гамильтоновых циклов . . . . . . . . . . . .
80
9.3.4. Гамильтоновы циклы в турнирах . . . . . . . . . . . . . . . . . .
81
9.3.5. Гамильтоновы циклы в случайных графах . . . . . . . . . . . .
81

Л е к ц и я 10. Задачи о пересечениях и проблема изоморфизма . . .
83

10.1. Графы пересечений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
10.1.1. Постановка задачи и формулировки результатов . . . . . . .
83
10.1.2. Доказательство теоремы Эрдеша–Ко–Радо . . . . . . . . . . .
84
10.1.3. Доказательство гипотезы Кнезера . . . . . . . . . . . . . . . . .
85
10.2. Проблема изоморфизма графов . . . . . . . . . . . . . . . . . . . . . . . .
86
10.2.1. Определение изоморфизма и несколько слов об истории
вопроса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
10.2.2. Проблема изоморфизма «почти наверное»: формулировка
результата . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
10.2.3. Проблема изоморфизма «почти наверное»: вспомогательное
утверждение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
10.2.4. Доказательство теоремы 10.2.2.1 . . . . . . . . . . . . . . . . . .
90

Задачи к лекциям 9 и 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92

Л е к ц и я 11. Моделирование Интернета . . . . . . . . . . . . . . . . . . .
94

Курсовые проекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
100

Л Е К Ц И Я
1

ОСНОВНЫЕ ОБЪЕКТЫ ТЕОРИИ ГРАФОВ

1.1.
ВВЕДЕНИЕ

Настоящая брошюра посвящена изучению различных экстремальных задач теории графов, (хотя бы частичное) решение которых может быть полезно при анализе данных. Она возникла на основе
семестрового курса лекций, прочитанных автором в Школе Анализа
Данных Яндекса.
Рассмотрим одну естественную конструкцию, которая послужит своего рода мотивировкой для всей нашей дальнейшей деятельности. Современный Интернет — это огромная и крайне нетривиально устроенная сеть, состоящая из миллионов сайтов и миллиардов страниц. Многие сайты при этом ссылаются друг на друга, и в результате образуется
весьма сложный (ориентированный) граф, вершинами которого служат
как раз сайты, а ребрами — ссылки. Разумеется, точные определения
упоминаемых объектов мы дадим позже, но и сейчас обладающий минимальной подготовкой читатель понимает, о чем идет речь.
Изучение свойств упомянутого графа («веб-графа», просто «веба» и
пр.) — увлекательная и трудная работа. Вот, например, одна из возможных важных и далеко еще полностью не решенных проблем. Некоторые
владельцы сайтов, желая в определенных целях искусственно повысить
рейтинг своей продукции, договариваются между собой и создают так
называемые «ссылочные кольца» сайтов. В простейшем случае участники ссылочного кольца попарно цитируют друг друга. Поисковая система
априори воспринимает членов такого кольца как обладателей высокого
индекса цитирования и автоматически повышает их статус, так что в
ответ на какой-либо запрос, связанный с тематикой, которая объединяет представителей кольца, с большой вероятностью в первую очередь
появится информация именно о недобросовестных «заговорщиках»; однако, как показывает опыт, наиболее содержательные данные лежат
отнюдь не на сайтах, принадлежащих к пресловутым кольцам: индекс
цитирования по-хорошему еще заслужить нужно!

1.2. Основные объекты теории графов
7

Продвинутая поисковая система должна каким-то образом вылавливать ссылочные кольца и не повышать, а, напротив, понижать статус их
создателей.
Первая (и наименее, впрочем, значительная) трудность состоит в том,
что заговорщики, будучи, конечно, отнюдь не глупыми людьми, стараются организовать более сложные схемы взаимного цитирования, нежели та, которую мы привели в качестве примера выше. Дело в том, что при
попарном цитировании возникает то, что называется полным подграфом
в графе или кликой в нем, а с такими «опухолями» бороться худо-бедно
умеют. Гораздо хуже, коль скоро, вместо клики, спамеры организуют нечто значительно более «разреженное»: с одной стороны, стандартные алгоритмы поиска перестают работать; с другой стороны, разреженность
ссылок не так уж велика, и спамеры все равно получают приоритет.
Вторая трудность еще тоньше первой. Оказывается, что в исключительно сложных системах зачастую просто по необходимости или же с очень
большой вероятностью возникают образования, которые сильно напоминают «разреженные» ссылочные кольца и в то же время таковыми, вообще говоря, не являются. Как сколь-нибудь достоверно различать образования-паразиты от естественных подграфов? Требуется, по-видимому,
очень хорошо понять вероятностную природу веб-графа, дабы затем построить сильные (статистические) критерии, позволяющие аккуратно выбирать между кольцами и схожими с ними, но не зловредными объектами.
Как видно, работы невпроворот. По существу, есть две важнейшие
составляющие деятельности. Первая из них — алгоритмическая: необходимо уметь максимально быстро вылавливать те или иные экстремальные (наибольшие, наименьшие и пр.) структуры в графе; например,
наибольшую клику или наибольший подграф с данным отношением числа ребер к числу вершин. Вторая — вероятностная: нужно создать
максимально достоверную модель веб-графа — так сказать, «случайного», — и, исходя из этой модели, научиться оценивать вероятности
возникновения в таком графе тех или иных конфигураций. Вокруг этих
двух составляющих мы и построим наши лекции.
Всего лекций будет одиннадцать. Из них десять — основные, а последняя — факультативная. После каждой второй (основной) лекции в
специально выделенном разделе будут предложены задачи.

1.2.
ОСНОВНЫЕ ОБЪЕКТЫ ТЕОРИИ ГРАФОВ

1.2.1.
Графы, орграфы и пр.

Граф — это пара G = (V, E), состоящая из произвольного
(не обязательно конечного) множества объектов V и некоторой (любой)
совокупности E пар этих объектов. Элементы множества V называются

.

Лекция 1. Основные объекты теории графов

вершинами графа, а пары вершин (элементы множества E) — его ребрами. Терминология мотивирована тем, что (конечные) графы принято
изображать на плоскости: вершинам сопоставляются точки, а ребрам —
отрезки (или дуги), соединяющие соответствующие вершины. Так, например, на рис. 1 изображен граф G=
{1, 2, 3}, {(1, 2), (2, 3), (1, 3)}
: геометрически это просто треугольник.

Рис. 1. Треугольник

Граф G′ = (V′, E′) называется подграфом графа G = (V, E), если V′ ⊆ V,
E′ ⊆ E. Подграфы бывают остовными, и тогда V′ = V; бывают они также
индуцированными (порожденными), и в этом случае E′ = E|V′, т.е. (x, y) ∈
∈ E′ для x, y ∈ V′ тогда и только тогда, когда (x, y) ∈ E (рисунки 2–5).

Рис. 2. Граф G
Рис. 3. Индуцированный
подграф графа G с рис. 2

Рис. 4. Остовный, но не индуцированный подграф G с рис. 2

Рис. 5. Не подграф
в G с рис. 2

1.2. Основные объекты теории графов
9

Часто для удобства различают графы, мультиграфы, псевдографы
и орграфы (ориентированные графы) (см. [1]). В этом случае под графами понимают лишь те пары G = (V, E), для которых (x, x) ̸∈ E, коль
скоро x ∈ V (нет «петель», рис. 6), каждая пара (x, y), x, y ∈ V, встречается в E не более одного раза (нет «кратных ребер») и пары (x, y) ∈ E
неупорядочены, т. е. ребра (x, y) и (y, x) считаются одинаковыми.

Рис. 6. Петля

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

Рис. 7. Граф, псевдограф, мультиграф, псевдомультиграф

Рис. 8. Орграф, псевдоорграф, мультиоргаф, псевдомультиорграф

Если x, y ∈ V образуют ребро (x, y) ∈ E, то говорят также, что x и y
смежны (или инцидентны); для обозначения смежности (инцидентно

Лекция 1. Основные объекты теории графов

сти) используется знак ∼. Иными словами, пишут x ∼ y, коль скоро
(x, y) ∈ E.

1.2.2.
Маршруты в графах
Маршруты в графах — это чередующиеся последовательности вершин и ребер v0, e1, v1, . . . , vn−1, en, vn; эти последовательности
начинаются и кончаются вершиной, и концами каждого ребра последовательности являются вершины, из которых одна непосредственно
предшествует этому ребру, а другая непосредственно следует за ним.
Маршрут замкнут, если v0 = vn, и открыт в противном случае. Маршрут называется цепью, если все его ребра различны, и простой цепью, коль скоро различны все его вершины (а стало быть, и ребра).
Замкнутую цепь называют циклом. Простой цикл — это замкнутый
маршрут, у которого все n вершин различны и n ≥ 3. Примеры см. на
рисунках 9–12.

Рис. 9. Граф G
Рис. 10. Простая цепь в
графе G с рис. 9

Рис. 11. Цикл в графе G
с рис. 9

Рис. 12. Простой цикл
в графе G с рис. 9

Граф, который представляет собой простой цикл на n вершинах,
обычно обозначается Cn (C3 — это «треугольник» с рис. 1); граф, представляющий собой одну простую цепь с n вершинами, обозначается Pn;

1.2. Основные объекты теории графов
11

граф на n вершинах, у которого вершины попарно смежны, называется
полным и обозначается Kn. Отметим, что K1 — тоже вполне осмысленный объект: если в графе принципиально неоткуда взяться ребрам, то
можно считать, что «все» ребра проведены, а стало быть, граф полон.
Отметим, что все определения этого пункта легко перенести на случай орграфа и, вообще, на любой граф в широком смысле слова.

1.2.3.
Связность

Связный граф — это граф, у которого любые две вершины
соединены хотя бы одной простой цепью. Скажем, что вершины графа
эквивалентны, если между ними существует простая цепь. Нетрудно видеть, что, тем самым, возникает отношение эквивалентности
на множестве вершин графа. Соответствующие классы эквивалентности называются компонентами связности (связными компонентами)
графа. Иными словами, компонента связности является связным подграфом данного графа, но, если мы добавим к ней хотя бы одну (любую)
вершину того же графа, то связность пропадет. Один из наиболее важных классов связных графов составляют деревья (связные графы без
циклов или, что то же самое, связные графы, у которых на n вершинах
n − 1 ребро). Граф, все компоненты которого суть деревья, называется
лесом (рисунки 13–15).

Рис. 13. Связный граф

Рис. 14. Граф с двумя компонентами связности

Рис. 15. Дерево

1.2.4.
Независимые множества и клики

Число независимости графа — это наибольшая мощность
множества попарно несмежных его вершин. Иными словами, если G =
= (V, E) — граф, то его число независимости есть величина

α(G) = max
|W|: W ⊆ V, ∀ x, y ∈ W (x, y) ̸∈ E
.

При этом сами множества W, по которым берется максимум в определении α(G), называются независимыми подмножествами множества
вершин графа G (рисунки 16–18).

Лекция 1. Основные объекты теории графов

Рис. 16. Граф G с α(G) = 3

Рис. 17. Одно независимое
множество вершин в графе
G с рис. 16

Рис. 18. Другое независимое
множество вершин в графе G
с рис. 16

В некотором смысле двойственным к числу независимости графа G
является его кликовое число ω(G): клика в графе — это его произвольный полный подграф; соответственно,

ω(G) = max
|W|: W ⊆ V, ∀ x, y ∈ W (x, y) ∈ E
.

На рисунках 19–21 приведены примеры графа и его клик.
Если дан граф G = (V, E), то дополнительным к нему называется граф G = (V, F), у которого (x, y) ∈ F тогда и только тогда, когда
(x, y) ̸∈ E (рисунки 22 и 23). Очевидно, α(G) = ω(G) и наоборот.
Также исключительно важны независимые множества ребер графа
или паросочетания в нем. Паросочетания — это наборы ребер графа,
никакие два из которых не имеют общих вершин.
Наконец, хроматическое число графа G = (V, E) — это минимальное
число χ(G) цветов, в которые можно так раскрасить множество вершин V
этого графа, чтобы вершины, соединенные ребром из E, были разноцветными. Название числа полностью отвечает его смыслу, поскольку в переводе с греческого слово «хроматический» означает «цветной».
Хроматическое число играет огромную роль как в абстрактной теории
графов, так и в ее многочисленных приложениях. Следующий простой
пример дает естественную интерпретацию введенного понятия: требуется расселить некоторое количество людей по комнатам так, чтобы

1.3. Двудольные графы
13

Рис. 19. Граф G с ω(G) = 4

Рис. 20. Одна клика
в графе G с рис. 19

Рис. 21. Другая клика
в графе G с рис. 19

Рис. 22. Граф G
Рис. 23. Граф G для
графа G с рис. 22

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

1.3.
ДВУДОЛЬНЫЕ ГРАФЫ

1.3.1.
Определение и мотививировка

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