Глибичук - Элементы дискретной математики в задачах

Доступен только на StudyGur

Страниц: 74
Опубликован:
ЧИТАЙТЕ ПОЛНЫЙ ТЕКСТ ДОКУМЕНТА

ПРЕДПРОСМОТР

Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
Элементы комбинаторики . . . . . . . . . . . . . . . .
1.1
Подсчёт и комбинаторные тождества . . . . . .
1.2
Формула включений и исключений . . . . . . .
1.3
Принцип Дирихле . . . . . . . . . . . . . . . . .
1.4
Комбинаторика булева куба . . . . . . . . . . .
1.5
Обращение Мёбиуса . . . . . . . . . . . . . . . .
1.6
Подсчёт двумя способами . . . . . . . . . . . .
1.7
Комбинаторные покрытия. А.Я. Канель . . . .
1.8
Подсказки . . . . . . . . . . . . . . . . . . . . .
1.9
Указания . . . . . . . . . . . . . . . . . . . . . .
2
Основы теории графов . . . . . . . . . . . . . . . . . .
2.1
Основные определения . . . . . . . . . . . . . .
2.2
Перечисление деревьев . . . . . . . . . . . . . .
2.3
Графы с точностью до изоморфизма . . . . . .
2.4
Плоские графы . . . . . . . . . . . . . . . . . .
2.5
Эйлеровы пути и циклы . . . . . . . . . . . . .
2.6
Гамильтоновы пути и циклы . . . . . . . . . . .
2.7
Экстремальные задачи (теорема Турана) . . .
2.8
Теорема Менгера . . . . . . . . . . . . . . . . .
2.9
Метод минимального контрпримера. А. Канель
2.10 Степенн´ые последовательности. В.А. Волков,
М.Н. Вялый и А.Б. Скопенков . . . . . . . . . .
2.11 Подсказки . . . . . . . . . . . . . . . . . . . . .
2.12 Указания . . . . . . . . . . . . . . . . . . . . . .
3
Раскраски графов и многочлены . . . . . . . . . . . .
3
6
11
11
13
17
19
21
24
26
28
30
50
50
53
56
57
62
65
67
69
70
72
79
82
95
4
Элементы дискретной математики в задачах
4
5
6
7
3.1
Раскраски графов . . . . . . . . . . . . . . . . . 95
3.2
Хроматические число и индекс . . . . . . . . . 97
3.3
Хроматический многочлен и многочлен Татта
98
3.4
Подсказки . . . . . . . . . . . . . . . . . . . . . 101
3.5
Указания . . . . . . . . . . . . . . . . . . . . . . 102
Основы теории Рамсея . . . . . . . . . . . . . . . . . . 105
4.1
Двухцветные числа Рамсея . . . . . . . . . . . 105
4.2
Многоцветные числа Рамсея . . . . . . . . . . . 106
4.3
Числа Рамсея для гиперграфов . . . . . . . . . 108
4.4
Результаты рамсеевского типа . . . . . . . . . . 109
4.5
Числа Рамсея для подграфов . . . . . . . . . . 111
4.6
Подсказки . . . . . . . . . . . . . . . . . . . . . 112
4.7
Указания . . . . . . . . . . . . . . . . . . . . . . 115
Системы множеств (гиперграфы) . . . . . . . . . . . . 126
5.1
Пересечения подмножеств . . . . . . . . . . . . 126
5.2
Системы общих представителей . . . . . . . . . 127
5.3
Системы различных представителей . . . . . . 129
5.4
Перманент . . . . . . . . . . . . . . . . . . . . . 131
5.5
Размерность Вапника-Червоненкиса . . . . . . 132
5.6
Подсолнухи . . . . . . . . . . . . . . . . . . . . . 134
5.7
Оценка Виссера мощности пересечений . . . . 135
5.8
Структуры на конечном множестве . . . . . . . 137
5.9
Подсказки . . . . . . . . . . . . . . . . . . . . . 142
5.10 Указания . . . . . . . . . . . . . . . . . . . . . . 144
Аналитические и вероятностные методы . . . . . . . . 153
6.1
Асимптотики . . . . . . . . . . . . . . . . . . . . 153
6.2
Независимость и доказательства существования 156
6.3
Случайные графы . . . . . . . . . . . . . . . . . 174
6.4
Случайные графы-2 . . . . . . . . . . . . . . . . 178
6.5
Подсказки . . . . . . . . . . . . . . . . . . . . . 181
6.6
Указания . . . . . . . . . . . . . . . . . . . . . . 184
Алгебраические методы . . . . . . . . . . . . . . . . . . 195
7.1
Линейно-алгебраический метод в комбинаторике195
7.2
Матрицы Адамара . . . . . . . . . . . . . . . . 199
7.3
Подсказки . . . . . . . . . . . . . . . . . . . . . 201
7.4
Указания . . . . . . . . . . . . . . . . . . . . . . 202
ОГЛАВЛЕНИЕ
8
Теоремы об инцидентностях в геометрии . . . . . . . .
8.1
Задачи . . . . . . . . . . . . . . . . . . . . . . .
8.2
Подсказки . . . . . . . . . . . . . . . . . . . . .
8.3
Указания . . . . . . . . . . . . . . . . . . . . . .
9
Аддитивная комбинаторика . . . . . . . . . . . . . . .
9.1
Задачи . . . . . . . . . . . . . . . . . . . . . . .
9.2
Подсказки . . . . . . . . . . . . . . . . . . . . .
9.3
Указания . . . . . . . . . . . . . . . . . . . . . .
10 Графы: задачи для исследования . . . . . . . . . . . .
10.1 Степенные последовательности. А. Скопенков
10.2 Гамильтоновость (А. Веснин, А. Скопенков) .
10.3 Изоморфизмы графов. И.Н. Шнурников . . . .
10.4 Турниры. Д. Пермяков . . . . . . . . . . . . . .
Предметный указатель . . . . . . . . . . . . . . . . . . . . .
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11 Программа курса ДА 2014-16 уч. годов . . . . . . . .
5
207
207
209
209
212
212
215
216
218
218
219
221
222
223
227
233
6
Элементы дискретной математики в задачах
Введение
Зачем эта книга?
Мы приводим подборки задач по комбинаторным разделам математики. Эти задачи подобраны так, что в процессе их решения
читатель (точнее, решатель) освоит основы важных теорий — как
классических, так и современных. Ср. [S4],[Z],[J]. Книга будет полезна руководителям и участникам кружков для старшеклассников и
младшекурсников (в частности, ориентированных на олимпиады).
Некоторые приводимые красивые задачи и важные темы малоизвестны в традиции кружков по математике, но полезны как для
математического образования, так и для подготовки к олимпиадам.
Решение этих задач (т. е. изучение соответствующих теорий)
будет полезно также всем, кто хочет стать математиком, специалистом по computer science или программистом, работающим в наукоёмких отраслях информационных технологий. Именно таких специалистов мы готовим на факультете инноваций и высоких технологий Московского Физико-Технического Института. Приведенные
задачи используются при изучении курсов дискретных структур и
дискретного анализа на этом факультете. Эти курсы читают А.Б.
Дайняк и А.М. Райгородский, а остальные авторы ведут семинары по этим курсам. Некоторые материалы основаны на занятиях,
проведенных А.Б. Скопенковым в Кировской летней математической школе, Московской выездной олимпиадной школе, а также на
кружках «Математический семинар» и «Олимпиады и математика».
Комбинаторика — один из самых красивых разделов современной математики. Постановки задач этого раздела зачастую доступны школьникам. А результаты, тем не менее, носят фундаментальный характер и важны как для развития других разделов математики, так и для приложений в информатике, биологии, экономике
и др. Мы постараемся рассказать о тех мощных современных методах, благодаря которым кристаллизуется серьезная научная дисциплина — комбинаторика. Среди этих методов, помимо более или
менее стандартных, вероятностный и линейно-алгебраический методы. Они лежат в основе самых продвинутых комбинаторных результатов, полученных за последние десятилетия.
ОГЛАВЛЕНИЕ
7
Параграфы второй половины книги дают экскурс в активно развивающиеся области математики. Хотя здесь изучаются только самые простые результаты и методы, они дают некоторое представление об основных направлениях научных исследований в соответствующих областях. Этому посвящены замечания, которые не используются ни в формулировках, ни в решениях задач. Важные
факты выделены словом «теорема» или «следствие».
Используемый материал.
Формулировки большинства задач доступны старшеклассникам,
интересующимся математикой; 1 мы приводим все определения, не
так часто изучаемые на кружках. Без определения используются
только простейшие определения и результаты теории чисел [O, §8§9], [Vi, §§1-3], [Z, §§3.1-3.4 и 3.7]. Если в некотором разделе для понимания условий или для решения задач нужны дополнительные
сведения (или консультация специалиста), то в начале соответствующего раздела приводятся ссылки.
При этом многие задачи трудны: для их решения нужно предварительно прорешать другие приведенные задачи на данную тему.
Как устроена книга.
Эту книгу не обязательно читать (точнее, прорешивать) подряд. Параграфы и разделы книги практически независимы друг от
друга (кроме разделов в §3 и §4, которые желательно прорешивать
подряд). Если в задаче одного из разделов все-таки используется
материал другого раздела, то либо эту задачу можно игнорировать,
либо посмотреть конеретно указанный материал другого раздела.
Основные обозначения приведены в конце введения. Основные понятия и обозначения теории графов введены в §2.1.
При этом параграфы расположены примерно в порядке возрастания сложности материала.
К важнейшим задачам приводятся подсказки, указания и решения. Подсказки и указания расположены в конце каждого парагра1
Часть материала (например, §1.1) на некоторых кружках и летних школах изучается даже 6-классниками. Однако приводимые подсказки, указания
и решения рассчитаны на читателей с некоторой математической культурой
(необходимой для освоения бо́льшей части книги). Разбирать эти решения с
6-классниками нужно по-другому, см., например, [GIF].
8
Элементы дискретной математики в задачах
фа. Однако к ним стоит обращаться после прорешивания каждой
задачи.
Общие замечания к формулировкам задач.
Задачи обозначаются жирными цифрами. Если в условии задачи написано «найдите», то нужно дать ответ без знака суммы
и многоточия. Если же условие задачи является формулировкой
утверждения, то в задаче требуется это утверждение доказать. Как
правило, мы приводим формулировку утверждения перед его доказательством. 2 В таких случаях для доказательства утверждения могут потребоваться следующие задачи. Это всегда явно оговаривается в подсказках, а иногда и прямо в тексте. (На занятии
задача-подсказка выдается только тогда, когда школьник или студент немного подумал над самой задачей.)
Большинство задач не оригинальны, но установить первоисточник не представляется возможным. Многие задачи взяты из [IKRS],
[Z], [L] и из неопубликованных материалов кафедры дискретной математики ФИВТ МФТИ.
О литературе.
В список литературы не вошли многие хорошие стандартные
учебники по комбинаторике и теории графов (ввиду необъятности
их количества). Мы цитировали те из них, которые по тем или иным
причинам чаще используем в преподавании. Мы цитировали всю
известную нам более продвинутую учебно-научную литературу. Но
этот список тоже не претендует на полноту, поскольку мы можем
не знать о некоторых публикациях.
В списке литературы [Ga, GKP, Gr, Har, Hal, K, M, R1, R2, R3,
R4, S1, S2, VS, 8] и [AM, BKS, BKKSS, I, Ja, J, KZP, KR, O, P, Vi, R5,
R6, S3, S5] — базовые учебники и статьи по темам этой книги и по
связанным темам, [AS, B, Bo, G, L, S7, So] — более продвинутая литература. Остальное — источники замечаний, основное содержание
2
Часто происходит обратное: формулировки красивых результатов и важных проблем, ради которых была придумана теория, приводятся только после
продолжительного изучения этой теории (или не приводятся совсем). Это способствует появлению представления о математике как науке, изучающей немотивированные понятия и теории. Такое представление принижает ценность математики.
10
Элементы дискретной математики в задачах
Основные обозначения
• [x] — (нижняя) целая часть числа x.
• d | n — число n делится на число d (для целых d и n).
• Rn — множество {1, 2, . . . , n}.
• N — множество {1, 2, . . . , n, . . .} целых положительных чисел.
• R, Q, Z — множества всех действительных, рациональных и
целых чисел, соответственно.
• Z2 — множество {0, 1} остатков от деления на 2 с операциями
сложения и умножения по модулю 2.
• Zm — множество {0, 1, . . . , m − 1} остатков от деления на m
с операциями сложения и умножения по модулю m.
( )
n
•
— количество k-элементных подмножеств n-элементного
k
множества (другое обозначение: Cnk ).
( )
X
•
— множество всех k-элементных подмножеств множеk
ства X.
• |X| — число элементов во множестве X.
• A \ B = {x | x ∈ A и x ∈
/ B} — разность множеств A и B (не
путайте этот знак с /).
• A⊔B — дизъюнктное объединение множеств A и B. Оно равно
A ∪ B, если A ∩ B = ∅.
• A ⊂ B — «множество A содержится в множестве B». (В некоторых других книгах это обозначают A ⊆ B, а A ⊂ B означает
«множество A содержится в множестве B и не равно B».)
• фраза ‘обозначим x = a’ сокращается до x := a.
1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
1
1.1
11
Элементы комбинаторики
Подсчёт и комбинаторные тождества
( ) (
)
( )
( )
n
n
n
n
1.1.1. (a)
=
. (b) Найдите сумму
+. . .+
.
k
n−k
0
n
) (
) ( )
n+1
n
n
=
+
, если 0 6
1.1.2. (a) Правило Паскаля.
k+1
k+1
k
k 6 n{− 1. (Подсказка
приведена
}
{
} после
{ }задачи 1.1.4.a.)
{ }
n+1
n
n
n
= (k + 1)
+
. Здесь
— количество
(b)
k+1
k+1
k
k
разбиений n-элементного множества на k частей (т. е. непустых подмножеств); разбиения считаются неупорядоченными, т. е. разбиение
множества {1, 2, 3} на части {1, 2} и {3} и разбиение того же множества на части {3} и {1, 2} считаются одинаковыми. Ср. с задачей
1.4.7.e.
{ }
n
Замечание. Числа
называются числами Стирлинга втоk
рого рода; подробнее о них см., например, [GKP, с. 287].
(
1.1.3. (a) Во скольких подмножествах множества R11 не найдётся
двух подряд идущих чисел?
(b) То же для трёх подряд идущих чисел.
( )
n
n!
n(n − 1) . . . (n − k + 1)
1.1.4. (a)
=
=
.
k
k!(n − k)!
k!
( )
∑n
n j n−j
n
(b) Бином Ньютона. (a + b) = j=0
a b .
j
Как решать задачи этого раздела? Мы предлагаем три метода,
которые продемонстрируем на примере трех доказательств правила
Паскаля 1.1.2.a.
(Большинство задач этого раздела решаются несколькими методами из трех предложенных Но, конечно, не каждый метод применим к каждой задаче. Обычно в указаниях для краткости приводится только один способ решения.)
1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
13
1.1.5.( Найдите
) ( )суммы:
( )
n
n
n
(a)
−
+ . . . + (−1)n
;
1 )
n
(0)
(
( )
( )
1 n
1 n
1
n
n
(b)
+
+
+ ... +
;
3( 2)
n
( 0 ) 2( 1)
( +)1 n
n
n
n
n
(c)
+2
+3
+ ... + n
;
1
2
3
n
( ) (
)
(
)
n
n+1
n+m
(d)
+
+ ... +
;
k
k+1
k+m
( )2
( )2
n
n
(e)
+ ... +
;
0
n
( )( ) ( )(
)
( )( )
n m
n
m
n m
(f)
+
+ ... +
;
0
k
1
k
−
1
k
0
( ) (
) (
)
( )
2n
2n − 1
2n − 2
n
(g)
−
+
− . . . + (−1)n
;
0
1
2
n
( )
(
)
(
)
( )
2n
2n − 1
2n − 2
n
(h)
+2
+4
+ . . . + 2n
.
n
n
n
n
1.1.6. Найдите
«явную» формулу
для
∑( n )
∑( n )
;
;
(a)
(b)
2k
4k
k>0
k>0
(c)
∑( n )
k>0
3k
.
В ответе используйте только целочисленные функции целочисленного аргумента.
1.1.7. (a) По кругу стоят числа 1, 2, . . . , n. Найдите число способов
выбрать k из них, чтобы никакие два выбранных не стояли рядом.
(Формально — число k-элементных подмножеств, в которых никакие два элемента не соседние.)
(b) Найдите число способов рассадить n пар враждующих рыцарей за круглый стол с нумерованными местами, чтобы никакие
два враждующих рыцаря не сидели рядом.
1.2
Формула включений и исключений
Этот раздел посвящен доказательству и использованию формулы включения-исключения. Она позволяет отвечать на вопрос
’Сколько существует объектов с данными свойствами?’ во многих
непростых случаях. Потребуются базовые навыки решения задач по
14
Элементы дискретной математики в задачах
комбинаторике. В частности, уметь приводить строгие доказательства с использованием взаимно-однозначных соответствий, правил
суммы и произведения. Например, полезно прорешать предыдущий
пункт.
В этом пункте использован материал Д.А. Пермякова.
Обозначим через φ(n) функцию Эйлера, т. е. количество чисел
от 1 до n, взаимно простых с числом n.
1.2.1. (a) Найдите количество чисел, не превосходящих 1001 и не
делящихся ни на одно из чисел 7, 11, 13.
(b) Найдите φ(1), φ(p), φ(p2 ), φ(pα ), где p — простое число, α > 2.
(c) φ(n) = n(1− p11 ) . . . (1− p1s ), где n = pα1 1 ·. . .·pαs s — каноническое
разложение числа n.
1.2.2. (a) На полу комнаты площадью 24 м2 расположены три
ковра (произвольной формы) площади 12 м2 каждый. Тогда площадь пересечения некоторых двух ковров не меньше 4 м2 .
(b) На кафтане расположено пять заплат (произвольной формы).
Площадь каждой из них больше трех пятых площади кафтана. Тогда площадь общей части некоторых двух заплат больше одной пятой площади кафтана.
(c) То же, что в (b), если площадь каждой заплаты больше половины площади кафтана.
1.2.3. Сколькими способами можно переставить числа от 1 до n,
чтобы
(a) и 1, и 2 не оказалось на своем месте?
(b) ровно одно из чисел 1, 2 и 3 оказалось на своем месте?
(c) каждое из чисел 1, 2 и 3 оказалось не на своем месте?
(d) каждое из чисел 1, 2, 3 и 4 оказалось не на своем месте?
1.2.4. На полке стоят 10 различных книг.
(a) Сколькими способами их можно переставить так, чтобы ни
одна книга не осталась на своем месте?
(b) Количество таких перестановок книг, при которых на месте
остаётся ровно 4 книги, больше 50000.
В этом разделе предлагаются задачи следующего типа: дано
конечное множество U и набор свойств (подмножеств) Ak ⊂ U ,
1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
19
Замечание. В данном случае подпоследовательность — это то,
что получается из последовательности вычеркиванием некоторых
её членов.
1.3.8. Имеется 10 яблок, каждое из которых весит не более 100 г, и
две одинаковые тарелки. Докажите, что можно положить в тарелки
(a) несколько яблок так, чтобы веса в тарелках отличались меньше, чем на 1 г.
(b) по одинаковому количеству яблок так, чтобы веса в тарелках
отличались меньше, чем на 2 г
При этом на тарелках должно лежать хотя бы одно яблоко, но не
обязательно должны лежать все яблоки (и в пункте (a) не обязательно, чтобы на каждой тарелке лежало хотя бы одно яблоко).
1.3.9. Для любых n векторов v1 , . . . , vn длины 1 на плоскости существует такой набор ε1 , . . . , εn = ±1, что
∑
∑
√
√
(a) | nk=1 εk vk | 6 n, (b) | nk=1 εk vk | > n.
1.4
Комбинаторика булева куба
1.4.1. Расставьте на шахматной доске нескольких коней, чтобы
каждый бил четырёх других.
1.4.2. 33 буквы русского алфавита кодируются последовательностями из нулей и единиц.
(a) При каком наименьшей длине последовательности кодирование можно сделать однозначным?
(b) Если при получении сообщения возможна ошибка в не более
чем одном разряде, т. е. если коды различных букв должны отличаться по крайней мере в трёх разрядах, то 8 разрядов не хватит.
(c) Если возможна ошибка в не более чем двух разрядах, то 10
разрядов не хватит.
(d)* Найдите наименьшее число разрядов, достаточное для кодирования из (b).
( )
n
1.4.3. (a) При фиксированном n число
максимально при k =
k
[n/2].
20
Элементы дискретной математики в задачах
(b) Best in their own ways. В математической олимпиаде участвовало k школьников. Выяснилось, что для любых двух школьников
A и B нашлась задача, которую решил A и не решил B, и задача,
которую решил B, но не решил A. Какое наименьшее возможное
количество задач могло быть при этом условии? Иными словами,
найдите наименьшее возможное n, для которого найдётся такое семейство из k подмножеств n-элементного множества, что ни одно
из подмножеств семейства не содержится (собственно) в другом.
1.4.4. Имеется табло с n горящими лампочками. Каждый переключатель может быть подсоединён к некоторым лампочкам. При
нажатии на кнопку переключателя соединённые с ним лампочки
меняют свое состояние: горящие тухнут, а не горящие загораются.
Какое наименьшее число переключателей необходимо, чтобы можно было зажечь любой набор лампочек (не входящие в этот набор
лампочки гореть не должны)?
1.4.5. В первый день своего правления король организует партии
среди n своих подданных. На второй день советник приносит королю список фамилий некоторых подданных (в первый день этот
список неизвестен). На третий день король может выбрать несколько партий и отправить в тюрьму всех подданных, участвующих в
каждой из них. Какое наименьшее число партий необходимо организовать в первый день, чтобы в третий день заведомо можно
было отправить в тюрьму всех подданных из принесенного списка
(и только их)?
Замечание. Следующая важная конструкция полезна (хотя и
не обязательна) для решения вышеприведенных (и многих других)
задач. Нарисуем точки, соответствующие всем подмножествам множества Rn . При этом на k-й этаж поместим точки, соответствующие k-элементным множествам. Соединим стрелкой те из них, которые получаются друг из друга добавлением одного элемента. Тогда
соединяемые стрелкой точки лежат на соседних этажах. Полученный граф называется n-мерным кубом. Его вершины соответствуют
векторам из Zn2 .
Определение множества Zn2 приведено в начале §7.1. Подмножество L ⊂ Zn2 называется линейным подпространством, если x + y ∈
1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
21
L для любых x, y ∈ L (не обязательно различных). Иными словами, линейное подпространство — такое семейство подмножеств
n-элементного множества, которое вместе с любыми двумя подмножествами содержит их симметрическую разность (т. е., сумму по
модулю 2).
1.4.6. (a) Любое линейное подпространство содержит нулевой набор (0, . . . , 0).
(b) Число элементов в любом линейном подпространстве является степенью двойки.
n количество линейных подпространств в
Обозначим через k Zn2 , состоящих из 2k элементов (такие линейные подпространства в
Zn2 называют k-мерными, ср. §7.1).
2 1.4.7. (a) Найдите для k = 0, 1, 2.
k
3 (b) Найдите для k = 0, 1, 2, 3.
k
n n n n =
= 1, =
= 2n − 1.
(c) 0
n
1
n−1 n n =
.
(d) k n−k n+1 n n
=
+ 2n−k .
(e) k+1
k+1
k n .
(f) Найдите 2 n .
(g) Найдите k Для решения этой задачи нужны некоторые понятия, приведенные в начале §7.1.
1.5
Обращение Мёбиуса
Под значком
∑
d|n
делителям числа n.
подразумевается сумма по всем натуральным
24
Элементы дискретной математики в задачах
(a) Найдите
∑
Mr (d).
d|n
(b) Выразите Tr (n) через все Mr (d), где d | n.
∑1∑
l
d.
(c) Tr (n) =
µ(d)r
l
(d) Tr (n)
l|n
= n1
d|l
∑
n
φ(d)r d . (Более простой способ доказательства
d|n
этой формулы приведен в [ZSS, §23].)
1.5.6. Найдите количество различных раскрасок карусели из n вагончиков в r цветов, в которых
(a) цвет s встречается ns раз для каждого s = 1, . . . , r. (Здесь в
качестве ответа принимается формула с суммированием по делителям, аналогичная 1.5.5.c.)
(b) присутствует ровно 4 цвета из r = 5 данных.
1.6
Подсчёт двумя способами
Мы приводим простейший вариант вероятностного метода в комбинаторике. Ср. §6.2, §6.3. Этот метод также применяется при решении задач 2.4.3, 2.6.5, 2.6.7, 2.7.2, 3.1.11.b, 4.1.5, 4.3.4.
Комбинаторные решения нижеприведенных задач можно изложить на вероятностном языке. Решения без явного построения вероятностного пространства могут привести к бессмыслице и ошибке. (Подумайте, например, с какой вероятностью случайный треугольник будет остроугольным.) Поэтому строгие решения на вероятностном языке должны начинаться с явного построения вероятностного пространства.
1.6.1. (a) Даны 21 девятиэлементных подмножеств 30-элементного
множества. Тогда какой-то элемент 30-элементного множества содержится по крайней мере в семи данных подмножествах.
(b) Комиссия собиралась 40 раз. На каждом заседании было ровно 10 человек, любые два не были вместе больше 1 раза. Тогда
в комиссии хотя бы 60 человек.
(c) В компании у любых двух знакомых друг с другом человек
есть ровно 5 общих знакомых (кроме них самих). Тогда количество
пар знакомых между собой людей в компании делится на 3.
1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
25
(d) Обозначим через Pn (k) число перестановок множества натуральных чисел от 1 до n, оставляющих ровно k чисел на своем
n
∑
месте. Тогда
k · Pn (k) = n!.
k=0
1.6.2. Пусть F — любое семейство k-элементных подмножеств nэлементного множества.
(a) Если k > l и каждое l-элементное подмножество n-элементного
множества
содержится
в некотором подмножестве из F, то
( ) /(
)
n
k
|F| >
.
l
l
(b) Количество (k − 1)-элементных подмножеств n-элементного
множества, целиком содержащихся хотя бы в одном из подмножеств
k|F|
семейства F, не меньше
.
n−k+1
1.6.3. На планете Марс 100 государств объединены в блоки, в каждом из которых не больше 50 государств. Известно, что любые два
государства состоят вместе хотя бы в одном блоке. Найдите минимально возможное число блоков. (Ср. с задачей 1.6.2.a.)
1.6.4. Ровно 19 вершин правильного 97-угольника покрашено в белый цвет, остальные вершины покрашены в чёрный. Тогда число
равнобедренных одноцветных треугольников с вершинами в вершинах 97-угольника не зависит от способа раскраски. (Треугольник
одноцветный, если все его вершины или белые, или чёрные.)
1.6.5. Даны числа n > k и множество S из n точек на плоскости.
Если любые три точки из множества S не лежат на одной прямой
и для любой точки P ∈ S существуют хотя бы k различных
точек
√
1
из множества S, равноудаленных от P , то k < 2 + 2n.
1.6.6. В любом множестве из n различных натуральных чисел найдётся подмножество из более чем n/3 чисел, в котором нет трёх
чисел, сумма двух из которых равна третьему.
1.6.7. По каждому из 100 видов работ в фирме имеется ровно 8
специалистов. Каждому сотруднику нужно дать выходной в субботу или в воскресенье. Докажите, что это можно сделать так, чтобы
50
2
2.1
Элементы дискретной математики в задачах
Основы теории графов
Основные определения
Графом G = (V, E) называется конечное множество V = V (G),
некоторые двухэлементные подмножества (т. е. неупорядоченные
пары несовпадающих элементов) которого выделены. Множество
выделенных
( ) подмножеств обозначается E = E(G). Таким образом,
V
E⊂
.
2
Элементы данного множества V называются вершинами. Выделенные пары вершин называются рёбрами. Хотя эти пары неупорядоченные, в теории графов их традиционно обозначают круглыми
скобками. Вершина, принадлежащая ребру, называется его вершиной. Если вершины a и b соединены ребром, они называются соседними или смежными, а само ребро (a, b) называется проходящим
через вершину a и вершину b или инцидентным вершине a и вершине b.
Общепринятый термин для понятия графа, данного здесь —
граф без петель и кратных рёбер или простой граф.
Если не оговорено противное, то через n и e обозначаются количества вершин и рёбер рассматриваемого графа, соответственно.
Граф можно представлять себе как набор точек (например, на
плоскости), некоторые пары которых соединены ломаными. См.
рис. 2, 3, 4, 7, 8, 10 и 11 ниже. При этом только концы каждой
ломаной являются вершинами графа и каждая пара вершин не соединена более чем одной ломаной. Точки называются вершинами
графа, а ломаные — рёбрами. Ломаные могут пересекаться, но точки пересечения «не считаются», т.е. не являются вершинами.
Путем Pn называется граф с вершинами 1, 2, . . . , n и ребрами
(i, i + 1), i = 1, 2, . . . , n − 1. Циклом Cn называется граф с вершинами 1, 2, . . . , n и ребрами (1, n) и (i, i + 1), i = 1, 2, . . . , n − 1. (Не
путайте эти графы с путем в графе и циклом в графе, определенными ниже.) Граф с n вершинами, любые две из которых соединены
ребром, называется полным и обозначается Kn . Если вершины графа можно разделить на две части так, что нет рёбер, соединяющих
вершины из одной и той же части, то граф называется двудольным,
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
51
а части называются долями. Через Km,n обозначается двудольный
граф с долями из m и из n вершин, в котором имеются все mn рёбер
между вершинами разных долей.
2.1.1. В любом графе есть двудольный подграф, содержащий не
менее половины рёбер графа.
Степенью deg v вершины v графа называется число выходящих
из нее рёбер. Изолированной вершиной называется вершина, из которой не выходит ни одного ребра.
Грубо говоря, подграф данного графа — это его часть. Формально, граф G называется подграфом графа H, если каждая вершина
графа G является вершиной графа H, и каждое ребро графа G
является ребром графа H. При этом две вершины графа G, соединённые ребром в графе H, не обязательно соединены ребром в
графе G.
k-кликой в графе называется его подграф с k вершинами, являющийся полным. Независимым множеством или антикликой в
графе называется набор его вершин, между которыми нет рёбер.
Путем в графе называется последовательность v1 e1 v2 e2 . . . en−1 vn ,
в которой для любого i ребро ei соединяет вершины vi и vi+1 . Число
n − 1 называется длиной пути. (Ребра e1 , e2 , . . . , en−1 не обязательно
попарно различны.)
Циклом в графе называется последовательность v1 e1 v2 e2 . . . en−1 vn en ,
в которой для любого i < n ребро ei соединяет вершины vi и vi+1 , а
ребро en соединяет вершины vn и v1 . Циклы считаются одинаковыми, если они отличаются циклическим сдвигом последовательности.
Число n называется длиной цикла. Несамопересекающимся называется цикл, для которого вершины v1 , v2 , . . . , vn попарно различны и
рёбра e1 , e2 , . . . , en попарно различны. Стандартный термин (менее
удобный для начинающего) — простой цикл.
2.1.2. (a) Любой цикл, не проходящий ни по одному ребру дважды, содержит несамопересекающийся цикл.
(b) Любой цикл нечётной длины содержит несамопересекающийся
цикл обход нечётной длины.
(c) Справедливо ли аналогичное утверждение для циклов чётной
длины, не проходящих ни по одному ребру дважды?
52
Элементы дискретной математики в задачах
(d) В графе есть несамопересекающийся цикл, проходящий через
рёбра a и b, а также есть несамопересекающийся цикл, проходящий
через рёбра b и c. Тогда есть несамопересекающийся цикл, проходящий через рёбра a и c.
Граф называется связным, если любые две его вершины можно
соединить путём, и несвязным иначе.
2.1.3. Если степень каждой из n вершин графа больше
то граф связен.
n
2
− 1,
Ясно, что «соединённость некоторым путём» является отношением эквивалентности на множестве вершин графа. Связной компонентой графа называется любой класс этой эквивалентности.
Рис. 1: Удаление ребра G − e, стягивание ребра G/e и удаление
вершины G − x
Определение операций удаления ребра и удаления вершины ясно из рис. 1. Операция стягивания ребра (рис. 1) удаляет из графа
это ребро и заменяет вершины A и B этого ребра на одну вершину
D, а все рёбра, выходящие из вершин A и B в некоторые вершины,
заменяет на рёбра, выходящие из вершины D в те же вершины. (Эта
операция отличается от стягивания ребра в мультиграфах, см. §2.5,
тем, что каждое получившееся ребра кратности больше 1 заменяется на ребро кратности 1.) Например, если граф — цикл с четырьмя
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
53
вершинами, то при стягивании любого его ребра получится цикл с
тремя вершинами.
Ориентированным графом (без петель и кратных рёбер) G =
(V, E) называется конечное множество V = V (G), некоторые упорядоченные пары несовпадающих элементов которого выделены. Множество выделенных пар обозначается E = E(G). Таким образом,
E ⊂ {(x, y) ∈ V × V | x ̸= y}. Если выделены и пара (a, b), и пара
(b, a), то это ребро не называется кратным.
Ориентированный путь в ориентированном графе — такая последовательность вершин, что в каждую следующую вершину ведет
ориентированное ребро из предыдущей.
2.1.4. Пусть дан ориентированный граф G, у которого на каждом
ребре u написан вес f (u). (Этот вес можно понимать как работу,
которую нужно затратить для того, чтобы пройти по ребру от начала до конца.) Функция p : V (G) → R («потенциал») такая, что
f (x, y) = p(x) − p(y) для любого ребра u = (x, y), существует тогда
и только тогда, когда сумма весов рёбер любого ориентированного
цикла равна нулю (при прохождении ребра по циклу в направлении, противоположном ориентации, вес в сумму берётся с отрицательным знаком).
Турниром называется ориентированный граф, любые две вершины которого соединены ребром. (Т.е. для любых двух вершин
v, w турнира среди его ребер есть (v, w) или (w, v), но не оба ребра
сразу.)
Некоторые другие определения приведены в начале каждого
раздела.
2.2
Перечисление деревьев
Граф называется деревом, если он связен и не содержит несамопересекающихся циклов. Остовом графа называется любой его
подграф, являющийся деревом и содержащий все вершины графа.
2.2.1. (a) В любом дереве найдется лист, т.е. вершина степени 1.
(b) В любом дереве с n вершинами n − 1 ребро.
54
Элементы дискретной математики в задачах
(c) В любом дереве между любыми двумя вершинами существует единственный путь.
(b’) Граф с n вершинами является деревом тогда и только тогда,
когда он не содержит несамопересекающихся циклов и имеет n − 1
ребро.
(b”) Граф с n вершинами является деревом тогда и только тогда,
когда он связен и имеет n − 1 ребро.
(c’) Если в графе между любыми двумя вершинами существует
единственный путь, то граф является деревом.
(d) Последовательность из n натуральных чисел является последовательностью степеней вершин некоторого дерева тогда и только
тогда, когда сумма её членов равна 2n − 2.
Заметим, что графы ({1, 2, 3}, {{1, 2}}) и ({1, 2, 3}, {{1, 3}}) различны. Графом называется именно граф, а не класс изоморфизма
графов (определение изоморфизма приведено в начале §2.3). Или,
говоря неформально, вершины графов считаются занумерованными. Поэтому вместо слова ‘граф’ иногда употребляют термин ‘помеченный граф’.
2.2.2. Каких графов с данными n вершинами больше:
(a) имеющих изолированную вершину или не имеющих?
(b) связных или несвязных?
2.2.3. (a) Формула Кэли. Число деревьев с данными n вершинами
равно nn−2 .
(b) Если сумма целых положительных чисел d1 , . . . , dn равна 2n −
2, то число деревьев с данными n вершинами, у которых i-я верши(n − 2)!
на имеет степень di , равно
.
(d1 − 1)! · . . . · (dn − 1)!
∑ deg (1)−1
deg (n)−1
Иными словами, (x1 + . . . + xn )n−2 = T x1 T
· . . . · xn T
,
где сумма берётся по всем деревьям T с вершинами 1, 2, . . . , n, и
через degT (k) обозначена степень вершины k дерева T .
(c) * Пусть T1 , . . . , Tr — деревья, множества вершин которых не пересекаются. Сколько есть деревьев, множество вершин которых есть
объединение множества вершин этих r деревьев, и которые содержат T1 , . . . , Tr ?
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
55
2.2.4. Код Прюфера сопоставляет дереву с вершинами 1, 2, . . . , n последовательность чисел от 1 до n по следующему алгоритму. Сначала код Прюфера — пустое слово. Пока количество вершин больше
двух,
1. Выбирается лист (см. задачу 2.2.1) v с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с v.
3. Вершина v и инцидентное ей ребро удаляются из дерева.
Когда осталось две вершины, алгоритм завершает работу.
(a) Найдите код Прюфера дерева с вершинами 1, 2, . . . , 10 и рёбрами (8,9),(8,4),(4,10),(10,3),(3,5),(10,6),(10,1),(1,7),(1,2).
(b) Восстановите дерево по коду Прюфера 1,1,2,5,4,2,7.
(c) Код Прюфера определяет взаимно-однозначное соответствие
между множеством деревьев с данными n вершинами и множеством
слов длины n − 2 из этих вершин.
(d) В коде Прюфера вершина степени d встречается d − 1 раз.
2.2.5. Граф называется унициклическим, если он становится деревом после удаления некоторого ребра. (Или, эквивалентно, если он
связен и имеет ровно один — с точностью до циклического сдвига
и симметрии — несамопересекающийся цикл.)
(a) Каких графов больше, деревьев с данными 100 вершинами или
унициклических графов с данными 98 вершинами?
(b) Выразите число унициклических графов с данными n вершинами в виде суммы не более чем n слагаемых.
2.2.6. (a) В дереве нет непустых подграфов, у которых степень
каждой вершины чётная и положительная.
(b) Для графа G обозначим через h1 (G) число его подграфов без
изолированных вершин, у которых степень каждой вершины чётна. (Пустой подграф удовлетворяет этому условию.) Докажите, что
h1 (G) – степень двойки. Выразите h1 (G) через количества n вершин, e рёбер и k компонент связности графа.
Замечание. Такие подграфы называют циклами в смысле теории
гомологий (не путайте с циклами в смысле теории графов). Как
они возникают, написано, например, в [S3, §6].
(c) На рёбрах дерева стоят знаки + и −. Разрешается менять знаки на всех рёбрах, выходящих из одной вершины. Тогда из любой
расстановки можно получить любую другую.
56
Элементы дискретной математики в задачах
(d) Для графа G обозначим через h1 (G) наибольшее количество
расстановок знаков + и − на его рёбрах, ни одну из которых нельзя
получить из другого описанными выше операциями. Докажите, что
h1 (G) — степень двойки. Выразите h1 (G) через n, e и k.
Замечание. В теории когомологий такие узоры называют коциклами, а приведенное отношение эквивалентности на коциклах — когомологичностью. Как возникает когомологичность коциклов, написано, например, в [S7, §11.1, §11.2].
(e)* Докажите, что h1 (G) и h1 (G) не меняются при стягивании ребра, и выведите отсюда, что h1 (G) = h1 (G).
2.3
Графы с точностью до изоморфизма
Грубо говоря, графы изоморфны, если они одинаковы (при этом
их изображения на плоскости могут быть разными). Формально,
графы G1 и G2 называются изоморфными, если существует взаимно
однозначное отображение f : V (G1 ) → V (G2 ), удовлетворяющее
условию: вершины A, B ∈ V (G1 ) соединены ребром в том и только
в том случае, если вершины f (A), f (B) ∈ V (G2 ) соединены ребром.
l◦'
lll ''
l
l
ll
''
lll
l
◦>> ''
◦.. ◦
>> '
.. >>'
. ◦
◦
l◦'
lululuu ''
l
l
ll u
lll uuu > ''
l
◦.. ◦ uu◦ > ''
>> '
..
uu
>>'
. uuu
◦u
◦
=
◦
vv◦ ===
v
v
◦===
◦
vv
v
v
= vv
◦I
◦=
IIII vvvv ===
◦===
◦
vIvII
v
II v
= vv
◦
◦
◦
◦
Рис. 2: Какие из графов на рисунке изоморфны?
2.3.1. Какие из графов на рисунке 2 изоморфны?
2.3.2. Для произвольных k, l, m, n ∈ N найдите количество
(a) клик размера k в графе Kn ,
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
57
(b) клик размера k в графе Km,n ,
(c) независимых множеств размера k в графе Kn ,
(d) независимых множеств размера k в графе Km,n ,
(e) подграфов в Kn , изоморфных Kk,l ,
(f) подграфов в Km,n , изоморфных Kk,l .
Будьте внимательны: эти задачи простые, но почти все требуют
разбора случаев.
2.3.3. Перечислите все попарно неизоморфные
(a) графы с четырьмя вершинами,
(b) связные графы с пятью вершинами и пятью рёбрами,
(c) несвязные графы с пятью вершинами.
2.3.4. Сколько существует попарно неизоморфных графов, имеющих 8 вершин и 25 рёбер?
2.3.5. Количество классов изоморфизма деревьев с n вершинами
(т. е. количество различных деревьев с n незанумерованными вершинами) меньше 4n .
2.4
Плоские графы
Плоским графом называется изображение графа на плоскости,
для которого любые два ребра пересекаются только по их общим
вершинам (в частности, если таких вершин нет, то не пересекаются).
Иногда такое изображение называют просто графом, но это неточно, поскольку один и тот же планарный граф можно изобразить
(без самопересечений) на плоскости разными способами.
Рис. 3: Различные изображения графа на плоскости
Плоский граф делит плоскость на части, называемые гранями
графа. Заметим, что одна из таких частей будет ‘бесконечной’.
58
Элементы дискретной математики в задачах
2.4.1. Дан плоский граф с треугольными гранями, имеющий более трех вершин. Удалили вершину вместе с выходящими из нее
рёбрами.
(a) Верно ли, что получившаяся грань ограничена несамопересекающимся циклом?
(b) Верно ли, что если выкинуть еще одну вершину, то все грани
опять будут ограничены несамопересекающимися циклами?
(c) Пусть в полученном графе степень каждой вершины не менее
3. Верно ли, что любую вершину нового графа можно удалить и
получить граф, все грани которого будут ограничены несамопересекающимися циклами?
2.4.2. (a) Формула Эйлера. Для любого связного плоского графа
с f гранями имеет место равенство n − e + f = 2. n, e не определены
(Доказательство см., например, в [P]. Далее этим результатом можно пользоваться без доказательства. Эта формула часто записывается в виде V − E + F = 2.)
(b) Найдите аналог формулы Эйлера для плоского графа с k компонентами связности.
K5
K3,3
Рис. 4: Непланарные графы
2.4.3. Применения формулы Эйлера.
(a) Ни один из графов K5 и K3,3 невозможно без самопересечений
нарисовать на плоскости.
(b) На плоскости отмечено n точек. Разрешается соединять некоторые две из них ломаной, не проходящей через другие точки. Два
игрока по очереди соединяют ломаной какие-то две еще не соединённые точки. При этом требуется, чтобы эти ломаные не самопересекались и не пересекались нигде, кроме отмеченных точек. Проиг-
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
59
рывает тот, кто не может сделать ход. Для каких n при правильной
игре выигрывает тот, кто ходит первым?
(c) Перечислите все связные плоские графы (с точностью до изоморфизма), у которых степени всех вершин равны и «степени» всех
граней равны (т. е. граница каждой грани состоит из одного и того
же числа рёбер).
Замечание. Если пункты (a), (b) или (c) не получаются, решайте
следующие пункты. Определение изоморфизма см. в §2.3.
(d)* Выпуклых правильных многогранников (все грани — правильные многоугольники с одинаковым числом сторон, степени всех вершин равны) ровно 5 (с точностью до изоморфизма их графов). Конструкцию соответствующих многогранников нужно привести, она
не предполагается известной.
(e) Для любого плоского связного графа без петель и кратных
рёбер, имеющего более двух вершин, 2e > 3f и e 6 3n − 6.
(f) В любом плоском графе есть вершина степени не более 5.
(g) Если каждая вершина плоского связного графа имеет степень
d, а граница каждой грани состоит из ровно k > 3 рёбер, то
1 1
1 1
+ = + .
d k
2 e
2.4.4. Картой на плоскости называется разбиение плоскости на
конечное число многоугольников (возможно, ‘бесконечных’). Раскраска карты называется правильной, если разные многоугольники,
имеющие общий граничный отрезок, имеют разные цвета. Докажите, что любую карту можно правильно раскрасить в
(a) 6 цветов; (b) * 5 цветов; (c)** [Всё равно не докажете.]
Замечание. Используя конструкцию двойственного графа, можно доказать, что правильная раскрашиваемость любой карты на
плоскости в d цветов равносильна правильной раскрашиваемости
любого плоского графа в d цветов (§3.1).
Граф называется планарным, если его можно без самопересечений нарисовать на плоскости. Ясно, что любой подграф планарного
графа планарен.
Операция подразделения ребра графа показана на рисунке.
60
Элементы дискретной математики в задачах
Рис. 5: Подразделение ребра
Два графа называются гомеоморфными, если от одного можно
перейти к другому при помощи операций подразделения ребра и
обратных к ним; или, эквивалентно, если существует граф, полученный из каждого из данных графов операциями подразделения
ребра.
Ясно, что гомеоморфные графы являются или не являются планарными одновременно.
Теорема Куратовского. Граф является планарным тогда и
только тогда, когда он не содержит подграфа, гомеоморфного графу K5 или K3,3 (рис. 4). (Доказательство этой теоремы см., например, в [S1].)
2.4.5. Придумайте алгоритм
(a) распознавания планарности графа (здесь можно использовать
без доказательства теорему Куратовского);
(b)* рисования без самопересечений заведомо планарного графа на
плоскости.
Найдите асимптотику сложности вашего алгоритма в зависимости от числа n рёбер графа. т. е. асимптотику максимума по графам
с n рёбрами от числа шагов в алгоритме, примененному к данному
графу. См. «определение» нахождения асимптотики в §6.1.
Теорема Хопкрофта-Тарджана. Существует линейный по
количеству рёбер алгоритм распознавания планарности графа.
2.4.6. (a) Теорема Фари. Плоский граф можно нарисовать без самопересечений на плоскости так, что все рёбра будут отрезками.
(b) Дан невыпуклый многоугольник с непрозрачными сторонами.
Назовем вершину A видимой из точки X, если внутренность отрезка AX не пересекается с границей многоугольника. Назовем ядром
многоугольника множество его внутренних точек, из которых видны все вершины многоугольника. Докажите, что если точку из ядра
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
61
соединить отрезками с произвольно выбранными несколькими (не
менее чем с двумя, и не обязательно со всеми) вершинами исходного
многоугольника, то многоугольник разобьется на многоугольники
с непустыми ядрами.
Тор и лента Мёбиуса изображены на рис. 6. Эти фигуры предполагаются прозрачными, т. е. точка (или подмножество), «лежащая
на одной стороне поверхности», «лежит и на другой стороне». Это
аналогично тому, что при изучении геометрии мы говорим, например, о треугольнике на плоскости, а не о треугольнике на верхней
(или нижней) стороне плоскости.
Рис. 6: Тор, лист Мёбиуса и цилиндр
2.4.7. Нарисуйте без самопересечений на торе граф
(5) K5 ; (33) K3,3 ; (6) K6 ; (34) K3,4 ; (7) K7 ;
(44) K4,4 .
2.4.8. Нарисуйте без самопересечений на ленте Мёбиуса граф
(5) K5 ; (33) K3,3 ; (6) K6 ; (34) K3,4 .
2.4.9. Картой на торе называется разбиение тора на конечное число (криволинейных и изогнутых) многоугольников. Раскраска карты на торе называется правильной, если разные многоугольники,
имеющие общую граничную кривую, имеют разные цвета. Любую
ли карту на торе можно правильно раскрасить в
(5) 5 цветов; (6) 6 цветов; (7) 7 цветов?
Подробнее см. [S3, §2].
Замечание. Любой связный граф с g рёбрами можно так нарисовать «на сфере с g ручками» (т.е. внутри правильного 2g-угольника,
диаметрально противоположные стороны которого «склеены»), что
62
Элементы дискретной математики в задачах
некоторые рёбра являются отрезками, а остальные рёбра являются объединениями двух непересекающихся отрезков, у каждого из
которых один конец — вершина графа, а другой конец лежит на
стороне 2g-угольника.
2.5
Эйлеровы пути и циклы
Мультиграфом (или графом с петлями и кратными рёбрами)
называется квадратная таблица из целых неотрицательных чисел,
симметричная относительно главной диагонали. (Мы не используем более правильную, но более громоздкую, терминологию: мультиграф — граф с кратными рёбрами, псевдограф — графом с петлями, псевдомультиграф — граф с петлями и кратными рёбрами.)
При этом число, стоящее на пересечении i-й строки и j-го столбца, интерпретируют как число рёбер (или кратность ребра) между
вершинами с номерами i и j при i ̸= j и как число петель в вершине с номером i при i = j. Ребро называется кратным, если его
кратность больше единицы.
Степенью вершины мультиграфа называется число выходящих
из нее рёбер. При этом ребро кратности k, соединяющее вершину с
другой вершиной, ‘вносит вклад’ k в степень, а петля кратности k
‘вносит вклад’ 2k в степень.
Ориентированным мультиграфом (или ориентированным графом с петлями и кратными рёбрами) называется квадратная таблица из целых неотрицательных чисел. Если в некоторой клетке
(неважно, диагональной или нет) стоит число, большее 1, то говорят, что ориентированный мультиграф имеет кратные рёбра.
Читатель легко сообразит, как определить (ориентированный)
путь в (ориентированном) мультиграфе, а также как изображать с
самоперечечениями на плоскости (ориентированные) мультиграфы.
2.5.1. Сколько всего мультиграфов с данными n вершинами
(a) ориентированных без кратных рёбер, но, возможно, с петлями?
(b) неориентированных без петель, но, возможно, с кратными рёбрами?
2.5.2. Сколько всего мультиграфов с данными n вершинами, имеющих k рёбер и
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
63
(a) неориентированных без петель и кратных рёбер?
(b) неориентированных, у которых допускаются кратные рёбра и
петли?
Эйлеров цикл (путь) в мультиграфе — цикл (путь), проходящий
по каждому ребру мультиграфа ровно один раз.
2.5.3. (a) В связном мультиграфе есть эйлеров цикл тогда и только тогда, когда степень каждой его вершины чётна.
(b) В связном мультиграфе есть эйлеров цикл тогда и только тогда, когда множество его ребер распадается на несамопересекающиеся циклы.
(c) При каком условии в мультиграфе существует эйлеров путь?
(d) При каком условии в ориентированном мультиграфе существует ориентированный эйлеров цикл?
(e) При каких n граф Kn имеет эйлеров цикл?
(f) То же для графа Km,n .
Входящей степенью вершины ориентированного мультиграфа
называется число входящих в нее рёбер (с учетом кратности). Аналогично определяется исходящая степень. При петля кратности k
‘вносит вклад’ k и во входящую, и в исходящую степень.
2.5.4. (a) Если количество вершин нечётной степени в связном
графе равно 2k, то множество его рёбер можно представить в виде
объединения k путей, никакой из которых не проходит ни по какому
ребру дважды и никакие два из которых не имеют общих рёбер.
(b) На рёбрах графа, у которого степень каждой вершины чётна,
можно поставить стрелки так, что у каждой вершины входящая
степень будет совпадать с исходящей.
(c) Все рёбра связного графа раскрашены в два цвета. Из каждой
вершины выходит поровну рёбер обоих цветов. Тогда из любой вершины до любой другой можно добраться, каждый раз меняя цвет
ребра.
(d) В нарисованном на плоскости без самопересечений связном
графе есть эйлеров цикл тогда и только тогда, когда грани можно раскрасить в 2 цвета правильно, т.е. так, что при переходе через
каждое ребро цвет меняется.
64
Элементы дискретной математики в задачах
2.5.5. Математик забыл трёхзначный код своего замкá. Замок открывается, если три цифры кода набраны подряд (даже если перед
этим были набраны другие цифры). Математик набирает одну цифру в секунду; набранная цифра добавляется в конец. Докажите, что
математик сможет открыть замок за
(a) 29 секунд, если в коде могут быть использованы только цифры
1, 3 и 7;
(b) 1002 секунды, если в коде могут быть использованы только
десять цифр.
(c) Сформулируйте и докажите правило «0 < 1 < 2 . . . < 8 < 9»
открытия замка за 1002 секунды.
Последовательность де Брёйна (П. д. Б.) с параметрами n и k
— последовательность, элементы которой принадлежат заданному
множеству из k элементов (обычно — {0, 1, . . . , k − 1}), причём все
её подпоследовательности длины n различны, и среди этих подпоследовательностей встречаются все k n возможных последовательностей. (Таким образом, длина П. д. Б. равна k n + n − 1.)
(Также П. д. Б. называют бесконечную периодическую последовательность с периодом k n , каждая подпоследовательность которой
длины k n + n − 1 является П. д. Б. с параметрами n и k.)
2.5.6. Постройте последовательность де Брёйна с параметрами k =
2 (‘двоичную’) и
(a) n = 3, начинающуюся с 111;
(b) n = 4, начинающуюся с 1011;
(c) n = 4, заканчивающуюся на 1010.
2.5.7. Правило «0 лучше 1». Рассмотрим последовательность из 0
и 1, построенную по следующим правилам. Она начинается с k единиц. Дальше мы пишем 1, только если при написании 0 не все подпоследовательности длины k новой последовательности различны.
Если даже при написании 1 не все подпоследовательности длины
k новой последовательности различны, то заканчиваем написание
последовательности. Докажите, что таким образом получится последовательность де Брёйна.
2.5.8. Дан связный ориентированный мультиграф с n вершинами.
Входящая степень dk каждой вершины k равна исходящей.
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
65
(a) Существует дерево, содержащее все вершины этого мультиграфа, все рёбра которого направлены в сторону вершины 1.
(b) Фиксируем дерево T из (a). Будем обходить этот граф (по
стрелкам), проходя по каждому ребру не более одного раза. Сначала выйдем из вершины 1 в произвольном направлении. Далее, пусть
мы пришли в некоторую вершину v. Выходим из нее по любому ребру, не принадлежащему T , если это возможно. А если невозможно,
то выходим из нее по ребру, принадлежащему T (такое ребро единственно). Докажите, что движение закончится в вершине 1, и что
в результате получится ориентированный эйлеров цикл.
(c) Число ориентированных эйлеровых циклов в этом мультиграфе кратно числу (d1 − 1)! · . . . · (dn − 1)!.
2.6
Гамильтоновы пути и циклы
Гамильтонов путь (цикл) в графе — путь (цикл), проходящий
через каждую вершину ровно по одному разу.
2.6.1. Грани гамильтонова плоского графа можно правильно раскрасить в 4 цвета.
Напомним (§2.1), что длина пути — число его ребер (а не вершин).
2.6.2. (a) Если граф связен и 2e > n2 − 3n + 6, то в нём есть
гамильтонов цикл.
(b) Теорема Дирака. Граф, сумма степеней любых двух несмежных вершин которого не меньше n, имеет гамильтонов цикл.
(c) Лемма Дирака. Если a0 . . . as — максимальный из путей в графе, проходящих по каждой своей вершине только один раз, s > 3
и deg a0 + deg as > s, то в этом графе есть несамопересекающийся
цикл длины s.
(d) Если в связном графе есть несамопересекающийся цикл длины
s < n, то в этом графе есть путь длины s, проходящий по каждой
своей вершине только один раз.
(e) Граф, сумма степеней любых двух несмежных вершин которого не меньше n − 1, имеет гамильтонов путь.
66
Элементы дискретной математики в задачах
2.6.3. Пусть для некоторых графа и целого k > 2 среди любых
k + 1 вершин графа есть ребро и после удаления любого набора
из k − 1 вершины граф остается связным. Тогда в этом графе есть
гамильтонов цикл.
2.6.4. Пусть среди любых k + 1 вершин графа есть ребро и после
удаления любого набора из k − 1 вершины граф остается связным.
(a) В этом графе есть хотя бы один несамопересекающийся цикл.
(b) Обозначим через v1 , . . . , vs максимальный несамопересекающийся цикл в этом графе. Обозначим через W любую компоненту связности графа, полученного удалением вершин этого цикла
из исходного графа. Обозначим через X множество вершин цикла,
соседних с W .
Тогда |X| > k.
(c) Вершины vi , vi+1 не лежат одновременно в X.
(d) Если vi , vj ∈ X, то в графе нет ребра vi+1 vj+1 .
1
6
8
7
13
9
2
14
16
5
12
15
11
3
10
4
Рис. 7: Есть ли в этом графе гамильтонов путь?
2.6.5. (a) Есть ли гамильтонов путь в графе на рисунке 7?
(b) Есть ли гамильтонов цикл в графе на рисунке 8?
(c) Для каких n есть гамильтонов цикл в графе, вершинами которого являются 3-элементные подмножества n-элементного множества, и два подмножества соединены ребром, если они пересекаются
ровно по одному элементу?
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
67
Рис. 8: Граф многогранника Гринбергса. Есть ли в нём гамильтонов
путь?
2.6.6. Максимальное число попарно непересекающихся
по рёбрам
[
]
n−1
гамильтоновых циклов в графе Kn равно
.
2
2.6.7. (a) В любом турнире имеется ориентированный гамильтонов путь.
(b) Для любого n существует турнир с n вершинами, в котором
имеется не менее n!/2n ориентированных гамильтоновых путей.
2.6.8. Рёберным графом графа G называется граф, вершины которого — рёбра графа G; две вершины рёберного графа соединены
ребром, если соответствующие рёбра графа G имеют общую вершину. Найдите в терминах графа G необходимое и достаточное условие
наличия гамильтонова цикла в его рёберном графе.
См. также [Ve].
2.7
Экстремальные задачи (теорема Турана)
2.7.1. Пункты этой задачи, кроме (b), являются различными версиями и частными случаями теоремы Турана.
Треугольником в графе называется цикл длины 3.
(a) Если граф не содержит треугольников, то e 6 n2 /4.
(b) Если e = [n2 /4] + 1, то в графе есть по крайней мере [n/2]
треугольников.
68
Элементы дискретной математики в задачах
(c) Если n = km и граф не содержит (k + 1)-клики, то 2e 6 k(k −
1)m2 . (Переходя к дополнительному графу, получаем, что если n =
km и граф не содержит (k + 1)-антиклики, то 2e > km(m − 1).)
(d) Если граф не содержит (k +1)-антиклики, то 2e > km(m−1)+
2mr, где m := [n/k] и r := k{n/k}.
2.7.2. (a) Если граф не содержит несамопересекающегося цикла
длины 4, то e < n3/2 .
(b) Если граф не содержит подграфа K3,2 , то e < 2n3/2 .
(c) Если граф не содержит подграфа K3,3 , то e < 2n5/3 .
(d)* Для любых целых s, t, 2 6 s 6 t, если граф не содержит
подграфа Ks,t , то e < tn2−1/s .
2.7.3. Для любых n точек на плоскости существует не более n диаметров, т. е. (неупорядоченных) пар точек, расстояние между которыми равно максимуму из всех возможных расстояний между
парами из этих n точек.
2.7.4. Для любых n точек A1 , . . . , An в Rd обозначим через D(A1 , . . . , An )
число (неупорядоченных) пар точек, расстояние между которыми
равно 1. Обозначим
En (d) = max{D(A1 , . . . , An ) : A1 , . . . , An ∈ Rd }.
Тогда:
(a) En (2) > n[log2 n]/4; (b) En (2) 6 2n3/2 ; (c) En (3) 6 2n5/3 ;
(n − 1)2
2(n + 4)2
(d)
6 En (4) 6
.
4
5
2.7.5. (a) Пусть V — 11q -элементное подмножество пространства
Rq (определение пространства Rq см. в главе 7) любое 10q -элементное подмножество которого содержит две точки x, y на расстоянии
1: |x − y| = 1. Докажите, что для достаточно большого q количество
единичных расстояний между точками множества V больше, чем
12q /2:
12q
1
|{(x, y) ∈ V × V : |x − y| = 1}| >
.
2
2
(b) Докажите, что в условиях предыдущего пункта можно заменить число 12q /2 на 12q .
72
2.10
Элементы дискретной математики в задачах
Степенны́е последовательности. В.А. Волков, М.Н.
Вялый и А.Б. Скопенков
1. (a) При каких E и n существует граф с n вершинами и E
ребрами, каждая вершина которого имеет степень 3? (Такие графы
называют кубичными или правильными степени 3.)
(b) При каких n и k существует граф на n вершинах, степени
которых равны k?
2. Графом с петлями и кратными ребрами называется набор
точек среди которых некоторые пары, возможно совпадающих, вершин соединены линиями. Ребра, соединяющие вершину саму с собой, называются петлями, а несколько ребер, соединяющих одну и
ту же пару вершин — кратными ребрами.
Даны целые положительные числа n, d1 , . . . , dn .
(a) При каких условиях существует граф с n вершинами (возможно, имеющий петли и кратные ребра), из которых выходит d1 , . . . , dn
ребер, соответственно?
(b) То же, если граф не может иметь кратных ребер (но, возможно, имеет петли, даже кратные).
(c) То же, если граф не может иметь петель (но, возможно, имеет
кратные ребра).
(d)* То же, если граф не может иметь ни петель, ни кратных
ребер.
Основной вопрос (задача 2d): какие последовательности являются степенными, то есть представляют последовательность степеней
вершин некоторого графа без петель и кратных ребер? Невозрастающую последовательность из n положительных целых чисел будем
называть правильной, если первый ее член не превосходит n − 1, а
сумма всех членов четна.
3. Докажите, что невозрастающая степенная последовательность
является правильной.
4. Являются ли степенными последовательности
(a) (43 , 16 ), (b) (64 , 23 ), (c) (53 , 33 ), (d) (1810 , 123 , 68 ), (e)
(158 , 106 , 34 )?
(Мы используем экспоненциальную запись невозрастающих целочисленных последовательностей: ak означает, что k последова-
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
73
тельных членов последовательности равны a.)
5. Докажите, что для степенной последовательности d1 , . . . , dn
(∗)
k
∑
i=1
di 6 k(k−1)+
n
∑
min(k, di ) для любого k = 1, 2, . . . , n−1.
i=k+1
6. Пусть a, b, c, d — различные вершины графа, причем (ab),
(cd) — ребра, а (ac), (bd) — не ребра. Назовем обменом преобразование графа, состоящее в удалении ребер (ab), (cd) и добавлении
ребер (ac), (bd).
Пусть G1 , G2 — два графа с одинаковыми последовательностями степеней d1 > d2 > . . . > dn . Докажите, что обменами можно
перевести граф G1 в граф G2 .
7. (a) Приведите пример правильной, но не степенной, последовательности из n чисел, лежащих в промежутке [2004, n/2004].
(b) Докажите, что любая правильная последовательность из n
√
чисел, меньших n/2, — степенная.
8. Пусть последовательность d1 , d2 , . . . , dn правильная, выполнено условие (*) и не все di равны. Обозначим t = min{i : di > di+1 }.
Определим новую последовательность
{
di ,
i ̸= t, n,
c = (c1 , c2 , . . . , cn ) формулой ci :=
di − 1, i = t, n.
Докажите, что если последовательность
(a) c степенная, то и d степенная.
правильная.
(b) d правильная, то и c
9. В обозначениях предыдущей задачи докажите условие (*) с
заменой d на c
(a) при k > t; (b) при dk 6 k−1 6 t−2; (c) при dk = k 6 t−1;
(d) при dk > k + 1 6 t.
10. Докажите, что невозрастающая последовательность является степенной тогда и только тогда, когда сумма ее членов четна и
выполнено условие (*).
11.* (abcd) То же, что в задаче 2, для связных графов.
74
Элементы дискретной математики в задачах
(a’b’c’d’) Сформулируйте и решите аналог задачи 2 для ориентируемых графов.
Ответы, указания и решения
2.9.1. (a) Ясно, что цепь и антицепь могут пересекаться не более
чем по одному элементу. Поэтому количество цепей, на которые
можно разбить частично упорядоченное множество, не меньше его
диаметра.
(b) (Доказательство теоремы Дилуорса.) Рассмотрим минимальный контрпример. Пусть C — цепь диаметра D. Тогда каждый элемент множества M − D либо больше некоторого элемента
из D, либо строго его меньше. Таким образом, M −D есть несвязное
объединение двух частей M ′ (выше D) и M ′′ (ниже D).
Если M ′ ∪ D и M ′′ ∪ D разбиваются на d цепей, то и все M разбивается на d цепей (каждая цепь склеивается из верхней и нижней
половин).
Если
M ′ ̸= ∅ и M ′′ ̸= ∅,
то #(M ′ ∪D) < #M
и #(M ′′ ∪D) < #M.
Мы осуществили спуск. В противном случае имеется не более двух
максимальных антицепей: верхняя (если M ′ = ∅) и нижняя (если
M ′′ = ∅). Рассмотрим случай наличия только верхней антицепи
(случай наличия только нижней антицепи симметричен).
Пусть имеется единственная максимальная антицепь D и x ∈
D. Тогда M − {x} имеет диаметр d − 1 и в силу минимальномти
контрпримера разбивается на d − 1 цепь C1 , . . . , Cd−1 . Поэтому x ∪
{Ci }d−1
i=1 есть искомое разбиение на d цепей.
Пусть имеются две максимальные антицепи D1 и D2 . Легко показать, что найдется пара элементов x ∈ D1 и y ∈ D2 таких, что
x ≺ y. Тогда диаметр множества M −{x, y} строго меньше диаметра
M и доказательство завершается аналогично.
2.10.1. (a) Ответ: такой граф существует при (V, E) = (2k, 3k)
для произвольного целого k > 1.
Рассмотрим произвольный кубический граф: каждая его вершина имеет степень 3. Сумма степеней всех вершин есть 2E. Поэтому
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
75
3V = 2E. Тогда пары чисел (V, E) имеют вид (2k, 3k) для некоторого натурального k. Так как нет петель и кратных ребер, то k = 1
невозможно.
При k > 1 условию удовлетворяют, например, 2k-угольник с
проведенными в нем диагоналями, соединяющими i-тые и (i + k)тые вершины.
(b) Ответ: такой граф существует при k ∈ {0, 1, . . . , n − 1} и
kn четном.
Для доказательства достаточности расположите вершины графа в вершинах правильного n-угольника. Соедините ребрами вершины, расстояние между которыми по окружности не превосходит
[k/2]. Для четного k построение графа закончено. Для нечетного k
число n четно, поэтому можно и нужно добавить большие диагонали.
Обозначим e := (d1 + · · · + dn )/2.
2.10.2. Ответы: (a,b) e целое. (c) e целое и di 6 e для любого
i. (d) См. задачи 5 и 10.
(с) Теорема. Граф без петель (но, возможно, с кратными ребрами и, возможно, не связный) с n вершинами степеней d1 , d2 , ..., dn >
0 существует тогда и только тогда, когда e := (d1 + · · · + dn )/2
целое и di 6 e для любого i.
Доказательство (предложено А. Руховичем). Необходимость
целочисленности e вытекает из того, что e равно числу ребер в
графе. Второе условие необходимо, поскольку в графе нет петель, а
значит степень каждой вершины не больше суммы степеней остальных вершин.
Докажем достаточность индукцией по e. База индукции: утверждение для e = 0 очевидно. Докажем шаг индукции. Пусть утверждение для e < k. Докажем, что оно верно и для e = k > 1. Из
k > 1 и условия di 6 e следует, что найдутся хотя бы две вершины
ненулевой степени. Можно считать, что d1 > d2 > ... > dn . Рассмотрим набор d1 − 1, d2 − 1, d3 , ..., dn . Условия теоремы для него
выполнены, поскольку сумма степеней вершин уменьшилась на 2,
а степень каждой вершины понизилась не более, чем на 1. Поэтому можно воспользоваться предположением индукции: существует
граф для набора d1 − 1, d2 − 1, d3 , ..., dn . В этом графе соединим реб-
76
Элементы дискретной математики в задачах
ром вершины 1 и 2. Поскольку эти вершины различны, то петель не
появилось. Следовательно, новый граф не содержит петель. Ясно,
что набор степеней его вершин — d1 , d2 , d3 , ..., dn . QED
2.10.4. (a,c) да. (b,d,e) нет.
2.10.5. Оцените сверху количество ребер, выходящих из первых
k вершин.
2.10.8. (a) Если хотим добавить ребро AB, а оно уже есть, то
возьмем вершину C, не соединенную с A. А потом возьмем вершину
D, соединенную с C, но не с B.
Доказательство С.А. Чоудама теоремы о степенных последовательностях (решение задач 9, 10). Докажем, что если последовательность d1 , d2 , . . . , dn неотрицательных чисел правильная и
k
∑
i=1
di 6 k(k − 1) +
n
∑
min(k, dj ),
j=k+1
для любого k = 1, 2, . . . , n − 1, то существует граф со степенями
d1 , d2 , . . . , dn .
Доказательство
ведем индукцией по сумме элементов последо∑
вательности
di . Случай, когда все di равны, рассмотрен в задаче 1b. Пусть теперь не все di равны. Можно считать, что dn > 0.
Обозначим t = min{i : di > di+1 }. Определим новую последовательность
{
di ,
i ̸= t, n,
c = (c1 , c2 , . . . , cn ) формулой ci :=
di − 1, i = t, n.
Обозначим
Sk =
казать неравенства
(∗)
k
∑
di ,
i=1
Sk′
= Sk −1 6 k(k−1)+
=
k
∑
ci . По задаче 8 достаточно до-
i=1
6 k(k − 1) +
При k > t
Sk′
Sk′
n
∑
i=k+1
n
∑
i=k+1
min{k, ci }.
min{k, di }−1 6 k(k−1)+
n
∑
i=k+1
min{k, ci }.
2. ОСНОВЫ ТЕОРИИ ГРАФОВ
77
Пусть теперь k 6 t − 1. Тогда Sk′ = Sk = kdk .
Для dk 6 k − 1 неравенство (*) тривиально.
Для dk = k
(4)
(3)
Sk′ − k(k − 1) = k 2 − k(k − 1) = k = dk+1 6
6 dk+1 +
(
n
∑
i=k+2
di − 2
)
(5)
=
n
∑
i=k+1
где
min{k, ci },
• равенство (3) выполнено, поскольку k 6 t − 1;
• неравенство (4) очевидно, если k + 2 < n; если же k + 2 = n, то
d = ((n−2)(n−1) , dn ) и dn > 2 в силу четности суммы d1 +d2 +· · ·+dn .
• равенство (5) выполнено, поскольку min{k, ci } = ci при i >
k + 1.
Случай dk > k+1. Если dn > k+1, то min{k, di } = min{k, ci } = k
при i > k + 1 и неравенство (*) следует из аналогичного для Sk .
Пусть теперь dn 6 k. Имеем
min{k, ci } = min{k, di } при k+1 6 i < n и
min{k, cn } = min{k, dn }−1.
В нашем случае Sk′ = Sk , поэтому достаточно показать, что
(∗∗)
Sk 6 k(k−1)+
n
∑
i=k+1
min{k, ci } = k(k−1)+
n
∑
i=k+1
min{k, di }−1.
Учитывая, что dk+1 = dk > k + 1, получаем
Sk+1
n
k + 1 (3)
k+1 ∑
= (k+1)dk =
Sk 6 (k+1)(k−1)+
min{k, di } =
k
k
i=k+1
n
(5)
k+1 ∑
= (k + 1)(k − 1) + (k + 1) +
min{k, di } >
k
i=k+2
> (k + 1)k +
n
∑
i=k+2
min{k + 1, di } > Sk+1 .
78
Элементы дискретной математики в задачах
Неравенство (5) выполнено, так как при всех k + 2 6 i < n имеем
нестрогое неравенство и при i = n строгое. Значит, в (3) неравенство
строгое. Отсюда вытекает (**).
Комментарий. Можно также доказать, что если для правильной последовательности d1 , . . . , dn выполняются неравенства из задачи 5, то последовательность, полученная из d2 −1, d3 −1, . . . , dd1 +1 −
1, dd1 +2 , dd1 +3 , . . . , dn−1 , dn расположением чисел по возрастанию, правильная и для нее выполняются аналогичные неравенства.
2.10.11. (abcd) То же, что в соответствующих пунктах задачи
2, с добавлением условия e > n − 1.
(c) Теорема. Связный граф без петель (но, возможно, с кратными ребрами) с n вершинами степеней d1 , d2 , ..., dn > 1 сушествует тогда и только тогда, когда выполнены следующие три условия:
(1) e := (d1 + d2 + ... + dn )/2 целое;
(2) di 6 e для любого i;
(3) n − 1 6 e.
Доказательство (предложено А. Руховичем). Для доказательства необходимости обозначим через e количество ребер в графе.
Условия (1) и (2) необходимы по задаче 2.c. Необходимость условия
(3) легко проверяется.
Для доказательства достаточности рассмотрим граф, полученный по задаче 2.c. Обозначим через c количество компонент связности этого графа.
Докажем, что если c > 1, то можно уменьшить количество компонент связности, не меняя степеней вершин. Ввиду условия (3)
e > n − 1 > n − c. Поэтому хотя бы в одной компоненте связности
есть цикл. Тогда можно взять ребро a1 a2 этого цикла и ребро b1 b2
из другой компоненты связности. Удалим эти ребра, и вместо них
добавим ребра a1 b1 и a2 b2 (ср. с задачей 6). Тогда степени вершин
сохранятся, а количество компонент связности уменьшится на 1.
Такими операциями можно понизить количество компонент связности до 1. Получится связный граф без петель с заданными степенями вершин. QED
3. РАСКРАСКИ ГРАФОВ И МНОГОЧЛЕНЫ
3
3.1
95
Раскраски графов и многочлены
Раскраски графов
Раскраска графа (т.е. вершин графа) в несколько цветов называется правильной, если концы любого ребра разноцветны.
3.1.1. Докажите, что следующие три условия эквивалентны:
• граф двудолен;
• граф можно правильно раскрасить в 2 цвета;
• граф содержит циклы только чётной длины.
3.1.2. (a) Если в графе степень каждой вершины не превосходит
d, то его можно правильно раскрасить в d + 1 цвет.
(b) Если в связном графе степень каждой вершины не превосходит d и есть вершина степени менее d, то его можно правильно
раскрасить в d цветов.
(c) Если в связном графе степень каждой вершины не превосходит
d, и есть вершина, после удаления которой граф перестает быть
связным, то граф можно правильно раскрасить в d цветов.
(d) Если связный граф G, имеющий более двух вершин, при удалении некоторого ребра распадается на два графа, каждый из которых можно правильно раскрасить в d цветов, то и исходный граф
можно правильно раскрасить в d цветов.
3.1.3. Если для некоторого k в графе с n вершинами среди любых
k + 1 вершин есть ребро, то граф невозможно правильно покрасить
менее, чем в n/k цветов.
3.1.4. В выпуклом многоугольнике провели несколько диагоналей,
не имеющих общих внутренних точек. Полученный плоский граф
можно правильно раскрасить в 3 цвета.
3.1.5. (a) В связном графе степень каждой вершины не превосходит трёх. Известно, что его можно правильно раскрасить в 3 цвета
так, чтобы соседи некоторой вершины были одноцветны. Добавили
одну вершину и выходящие из нее рёбра так, что по-прежнему степени всех вершин не превосходят трёх. Докажите, что полученный
граф можно правильно раскрасить в 3 цвета.
3. РАСКРАСКИ ГРАФОВ И МНОГОЧЛЕНЫ
97
3.1.9. Ориентированный граф, из каждой вершины которого выходит не более d рёбер, можно правильно раскрасить в 2d + 1 цвет.
3.1.10. Имеется несколько цветов. Каждой вершине двудольного
графа с n 6 2k−1 вершинами сопоставлено не менее, чем k цветов. («Списки» цветов, сопоставленные разным вершинам, могут
быть и одинаковыми, и различными.) Тогда существует правильная раскраска графа, приписывающая каждой вершине некоторый
сопоставленный ей цвет.
3.1.11. (a) Если степень каждой вершины графа не превосходит
d, то рёбра графа можно раскрасить в d + 1 цвет так, чтобы рёбра,
имеющие общий конец, были разноцветны.
(b) Существует такая раскраска рёбер графа K
в два
(m,n)(
) цвета, что
m n 1−ab
число одноцветных подграфов Ka,b не больше
2
.
a
b
3.2
Хроматические число и индекс
Хроматическим числом χ(G) графа G называется минимальное
количество цветов, в которые можно правильно покрасить вершины
графа G.
3.2.1. Если при удалении из графа любой вершины хроматическое
число уменьшается, то χ(G) 6 1 + [2e/n].
3.2.2. (a) На какое число может измениться хроматическое число
графа, если добавить к графу одно ребро? Или, формально, найдите все целые k, для которых существует граф G и его ребро u
такие, что χ(G) − χ(G − u) = k.
(b) χ(V, E1 ∪E2 ) 6 χ(V, E1 )χ(V, E2 ). (Напомним, см. §2.1, что через
(V, E) обозначается граф со множеством вершин V и множеством
ребер E.)
(c) Для любых r1 , r2 ∈ N постройте такие графы (V, E1 ) и (V, E2 ),
что χ(V, E1 ∪ E2 ) = χ(V, E1 )χ(V, E2 ), χ(V, E1 ) = r1 и χ(V, E2 ) = r2 .
3.2.3. Следующий алгоритм раскраски вершин графа называется
жадным. Сначала все вершины произвольно нумеруются. После
этого последовательно каждую вершину, начиная с первой, красим
98
Элементы дискретной математики в задачах
в цвет с минимальным номером, отсутствующим среди уже покрашенных соседей этой вершины.
(a) Вершины произвольного графа G можно занумеровать так,
чтобы жадный алгоритм его раскраски использовал ровно χ(G)
цветов.
(b) Для каждого целого k > 0 постройте такие двудольный граф и
нумерацию его вершин, что раскраска графа, построенная жадным
алгоритмом, отвечающим построенной нумерации, имеет не менее
k цветов.
Эта задача показывает, что «качество» раскраски, построенной
жадным алгоритмом, сильно зависит от упорядочения вершин.
Раскраска рёбер графа называется правильной, если любые два
ребра, имеющие общую вершину, окрашены в разные цвета. Хроматический индекс графа — минимальное число цветов, в которые
можно правильно раскрасить рёбра этого графа.
Рис. 10: Граф Петерсена
3.2.4. Исследуйте на планарность (§2.4), найдите хроматическое
число и хроматический индекс графов:
(a) графа Петерсена, изображённого на рисунке 10;
(b) графов с рисунка 11.
3.3
Хроматический многочлен и многочлен Татта
Значением хроматической функции χG графа G в точке t называется количество правильных раскрасок графа в t цветов.
3. РАСКРАСКИ ГРАФОВ И МНОГОЧЛЕНЫ
jjj◦TTTTTTT
j
j
j
◦''=j==
◦
'' ◦I ◦
◦
'' IIII uuuu IuIu
''
I
'' ◦uu ◦== =
◦
◦
1
=N=NN
◦GF
==NNN
◦ pp◦
ppp
p
◦@A
ED
p◦-p
p
pp - C
◦pNNN◦N=== -NN=  -◦ BC
2
99
jjj◦TTTTTTT
j
j
j
◦''=j== ◦
'' ◦ ◦.
.. uuu◦ ''
u
''
uu..
u
'' ◦u ◦== =
◦
◦
3
Рис. 11: Исследуйте на планарность, найдите хроматическое число
и хроматический индекс графов
3.3.1. Найдите хроматическую функцию для (a) полного графа;
(b) графа, не имеющего ребер; (c) пути; (d) цикла; (e) дерева
с n вершинами.
3.3.2. (a) χG = χG−u − χG/u для любого ребра u графа G.
(b) Теорема Биркгофа–Уитни. Для каждого графа G существует
ровно один такой многочлен, что для любого t число χG (t) правильных раскрасок графа G в t цветов равно значению в точке t этого
многочлена.
Ввиду этой теоремы хроматическая функция называется хроматическим многочленом и считается определенной не только для целых
t > 0 (ср. с (e)).
(c) Степень хроматического многочлена χG равна n, старший коэффициент равен 1, второй коэффициент равен (−e), коэффициенты знакопеременны (т. е. коэффициент при tn−2k неотрицателен и
коэффициент при tn−2k+1 неположителен для любого целого k).
(d) Третий коэффициент хроматического многочлена графа, считая с самого старшего, однозначно определяется набором подграфов графа, содержащих 3 вершины.
(e) Число |χG (−1)| равно числу ациклических ориентаций графа
G, т. е. числу способов так расставить стрелки на его рёбрах, чтобы
полученный ориентированный граф не содержал ориентированных
циклов.
3.3.3. (a) Если хроматический многочлен графа равен t(t−1)n−1 ,
100
Элементы дискретной математики в задачах
то граф — дерево.
(b) Не существует графа с хроматическим многочленом t4 − 3t3 +
3t2 .
3.3.4. (a) Найдите χG⊔H , зная χG и χH .
(b) Путь из m вершин «прицепили» за один из концов к одной из
вершин графа G, содержащего n вершин. Выразите хроматический
многочлен полученного графа с m + n − 1 вершиной через χG .
(c) Если H, K — графы, на которые распадается связный граф G
при удалении его ребра, то tχG = (t − 1)χH χK .
3.3.5. Обозначим через χ′G = χ′G (t) количество правильных раскрасок рёбер графа G в t цветов.
(a) Функция χ′G является многочленом от t.
(b) Старший моном в χ′G равен te .
( v)
∑
.
(c) Коэффициент при te−1 в χ′G равен − v∈V (G) deg
2
Мостом называется ребро, при удалении которого количество
связных компонент графа увеличивается. Граф называется лесом,
если он не содержит несамопересекающихся циклов. Напомним, что
при стягивании ребра в мультиграфах, в отличие от графов, получившиеся ребра кратности больше 1 не заменяются на ребра кратности 1.
3.3.6. Для любого мультиграфа G выполнено TG = TG−u + TG/u ,
где u — ребро мультиграфа G, не являющееся ни петлей, ни мостом,
и TG — число
(a) остовных лесов (т. е. объединений остовов его компонент);
(b) таких наборов рёбер, что для любой компоненты связности
графа лежащие в ней рёбра из набора образуют связный подграф;
(c) подграфов, являющихся лесами.
3.3.7. Даны связный мультиграф и набор ребер в нем, не содержащий несамопересекающихся циклов и ни одного ребра некоторого
максимального дерева. В мультимножестве (т. е. в неупорядоченном наборе с кратностями) мультиграфов разрешается для любого
мультиграфа G и его ребра u, не являющегося ни петлёй, ни мостом,
заменять один мультиграф G на два мультиграфа G − u, G/u. Эта
126
5
5.1
Элементы дискретной математики в задачах
Системы множеств (гиперграфы)
Пересечения подмножеств
Когда речь идет о множестве подмножеств, употребляют синонимы ‘система’, ‘семейство’ или ‘набор’ подмножеств.
5.1.1. В любом семействе попарно пересекающихся подмножеств
n-элементного множества не более 2n−1 подмножеств.
5.1.2. Пусть 2 6 t 6 n − 2.
(a) Постройте семейство из 2n−t подмножеств n-элементного множества, любые два из которых пересекаются не менее, чем по t
элементам.
(b) Существует ли такое семейство из 2n−t + 1 подмножеств?
5.1.3. Теорема Эрдеша—Ко—Радо. Пусть F — любое семейство kэлементных подмножеств n-элементного множества.
(a) Если( 2k 6)n и любые два подмножества из F пересекаются,
n−1
то |F| 6
.
k−1
(b) Если 2k > n и объединение никаких двух
из F
( подмножеств
)
n−1
не есть все n-элементное множество, то |F| 6
.
k
5.1.4. Любое семейство из двадцати 5-элементных подмножеств 15элементного множества можно так разбить на 6 подсемейств, чтобы
любые два непересекающихся подмножества лежали бы в разных
подсемействах.
Замечание. В таких ситуациях (см. §7.1) обычно вместо разбиении на подсемейства говорят о раскраске в разные цвета. Тогда
вопреки наглядному представлению о раскраске красятся множества, но при этом не красятся их элементы.
5.1.5. Для l < k обозначим через M (n, k, l) минимальное количество таких k-элементных подмножеств множества Rn , что любое
l-элементное подмножество множества Rn целиком содержится хотя бы в одном
(n) из
(k)них. Например, задача 1.6.2.a утверждает, что
M (n, k, l) > l / l .
6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
6
6.1
153
Аналитические и вероятностные методы
Асимптотики
Если не оговорено противное, то o, O (рукописные обозначения: o, O), асимптотики и пределы рассматриваются при n → ∞.
f (n)
Запись f (n) ≪ g(n) означает, что f (n) = o(g(n)), т.е. lim
= 0.
n→∞ g(n)
Запись f (n) & g(n) означает, что f (n) > (1 + o(1))g(n).
Найти асимптотику для функции f (n) означает найти «явную»
f (n)
функцию a(n), для которой lim
= 1.
n→∞ a(n)
6.1.1. Найдите асимптотику для
(a,b,c) сумм из задачи 1.1.6;
(d) количества An подмножеств множества {1, 2, . . . , n}, не содержащих двух подряд идущих чисел;
(e)* То же, что в (d), для трёх подряд идущих чисел.
В ответе можно использовать функцию xP (a, b), которая по числам
a, b и многочлену P , имеющему единственный корень на отрезке
[a, b], выдает этот корень.
6.1.2. Найдите асимптотику наибольшего количества рёбер в графе
с n вершинами, не содержащем k-клики. Здесь k = kn = o(n).
6.1.3. Докажите следующие соотношения, предполагая в асимптотиках, что n → ∞, а k фиксировано. (Число exH (n) определено в
задаче 2.7.6.)
n2
k−1
(a) exPk (n) & k−2
2 n. (b) exC2k+1 (n) & 4 . (c) exK1,k (n) ∼ 2 n.
Замечание. Знаменитая теорема Эрдеша-Стоуна-Шимоновича
утверждает, что для любого фиксированного H такого, что χ(H) >
n2 χ(H) − 2
2, при n → ∞ выполнено exH (n) ∼
. (Для двудольных
2 χ(H) − 1
H известно лишь, что exH (n) = o(n2 ).) То есть, если мы запрещаем
графу иметь некоторый фиксированный подграф H, то доля рёбер, которые при этом можно провести, среди всевозможных рёбер
определяется хроматическим числом графа H. Удивительно, что
154
Элементы дискретной математики в задачах
хроматическое число возникает в этой задаче! Доказательство теоремы можно прочесть по ссылке [1]. (Этой теоремой нельзя пользоваться при решении задачи 6.1.3.b.)
)n
(
6.1.4. (a) n2 2 + n1 = (2+o(1))n . По определению, это
( означает,
)n
2
что существует функция ψ(n) = o(1), для которой n 2 + n1
=
√ (
)n
(2 + ψ(n))n ; или, что то же самое, n n2 2 + n1 − 2 = o(1).
√ (
)n
(b) 3 n 2 + n1 = (2 + o(1))n .
√(
)
n
n
6.1.5. (a) Найдите асимптотику для
(ср. с задачами
[n/2]
1.4.3.b и 6.1.10.b).
(
)
2n
n
<
< 2n .
(b)
n+1
[n/2]
√( )
3m
(c) Найдите асимптотику для m
.
m
( )
33m
3m
(d)
< 22m
< 33m .
3m +)1
m
(
n
(e)
= (a−a (1 − a)a−1 + o(1))n .
[an]
n!
(f)
=
(e−a1 ln a1 −...−as ln as + o(1))n , где
[a1 n]! . . . [as n]!
a1 + . . . + as = 1.
6.1.6. (a) Найдите асимптотику
для ln(n!).
√
n
(b) Найдите асимптотику для n!.
(c) nn e−n+1 6 n! 6 nn+1 e−n+1 ;
√
(d) n! 6 nn e−n+1 n.
√
(e)* Формула Стирлинга. n! ∼ nn e−n 2πn, т. е. lim
n→∞
1.
n!
√
nn e−n 2πn
=
( )
n
nk
6.1.7. (a)
<
.
k
k!
(
( ))
(n − 1)(n − 2) . . . (n − k)
k
k(k + 1)
(b) ln
1
+
O
для k =
=
−
nk
2n
n
( )
kn < n/2. Это означает, что существует функция ψ(n) = O nk , для
6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
155
(n − 1)(n − 2) . . . (n − k)
k(k + 1)
=
−
(1 + ψ(n));
2n
nk
2n
(n − 1)(n − 2) . . . (n − k)
или, что то же самое, −1 −
ln
=
k
k(k
+
1)
n
( )
k
O
.
n( )
n
nk − k(k−1) +O(k3 /n2 )
(c)
=
e 2n
для k = kn < n/2.
k!
k
которой
ln
k(k−1)
3
2
(Сформулируйте
сами, что здесь означает e− 2n +O(k /n ) .)
( )
√
n
nk
(d)
∼
для k = kn = o( n).
k
k!
√
Неформально, это означает, что для k ≪ n вероятность выпадения ровно k орлов при n подбрасываниях монеты приближенно
nk −n
равна
2 . В неформальном замечании к этому и следующему
k!
пунктам достаточно интуитивного понимания того, что такое вероятность.
(
) ( )
2
2n
2n
− kn (1+o(1))
(e)
/
=e
для k = kn = o(n).
n−k
n
k2
(Сформулируйте сами, что здесь означает e− n (1+o(1)) .)
Неформально, это означает, что для k ≪ n вероятность Pk выпадения ровно n−k орлов при 2n подбрасываниях монеты приближенно
2
равна P0 e−k /n (нормальное распределение).
6.1.8. (a) Верно ли, что записи eo(n) и o (en ) «равнозначны»?
т. е., верно ли, что для любой функции f : Z → (0, +∞) условия
ln f (n)
lim
= 0 и lim f (n)e−n = 0 равносильны?
n→∞
n→∞
n
(b) Подберите функции f, g : Z → (0, +∞) такие, что f (n) ∼ g(n),
но ef (n) ̸= O(eg(n) ).
(c) Могут ли функции f, g : Z → (0, +∞) одновременно удовлетворять соотношениям f (n) = o(g(n)) и g(n) = o(f (n))?
(d) Могут ли функции f, g : Z → (0, +∞) одновременно удовлетворять соотношениям f (n) = O(g(n)) и g(n) = O(f (n))?
(e) Следует ли из двух соотношений из (d), что f (n) ∼ g(n)?
6.1.9. (a) Какая функция растет быстрее: x(x
x
x
найдите lim x(x ) (x!)(−2 ) .
x→∞
x)
x
или (x!)(2 ) ? т. е.
156
Элементы дискретной математики в задачах
(b) Существует √ли функция ψ(n) = o(1), для которой
(2 + ψ(n))n 2−n e− n → ∞?
(Как в любой математической задаче, нужно обосновать ответ: привести пример такой функции или доказать её существование или
доказать, что такой функции не существует.)
В задачах 6.1.10.bcde и 6.1.11.cef, в отличие от остальных, можно
пользоваться без доказательства формулой Стирлинга 6.1.6.e.
6.1.10. Найдите
(
)
( 2)
( 2 ) асимптотику для
n
n
n
(a) ln
;
(b)
(c)
;
[n/2]
n
n
(
)
n
(d)*
(e) (2n−1)!! := (2n−1)·(2n−3)·. . .·3·1;
, α ∈ (0, 1);
[nα ]
n ( )2
n ( )4
∑
∑
n
n
(f)
;
(g)*
.
k
k
k=0
k=0
6.1.11. Найдите асимптотику функции s = s(n), заданной как
(a) ss = n;
3
(b) ss = n;
(c) s(n) := max{k
{ | k! 6 n};
}
(n)
m
(
)
(d) s(n) := min m ∈ N | m < 2 2 ;
(e) s(n) := min {m ∈ N | 2m /m > n} (функция 2m /m возникает
как сложность реализации
функций алгебры
логики);
{
}
( m )
(f) s(n) := min m ∈ N | [m/2] > n (ср. с задачей 1.4.3.b).
6.1.12.* В ответах можно использовать константы, заданные в виде
суммы рядов. Найдите асимптотику для
(a) количества линейных подпространств в Zn2 (см. задачу 1.4.7 и
определение перед ней);
(b) количества унициклических графов с n вершинами (см. задачу
2.2.5.b и определение перед ней).
6.2
Независимость и доказательства существования
Введение
Цель этого раздела — продемонстрировать метод доказательства некоторых интересных комбинаторных результатов (пункты
174
Элементы дискретной математики в задачах
доказательство вместо локальной леммы Ловаса использует квазислучайные графы, неравенства плотной концентрации и пр.
6.3
Случайные графы
Начнем с интересных задач, которые можно решить при помощи
случайных графов. (Более простые решения без случайных графов
неизвестны. Известны такие же или более сложные, и то не для
всех задач.)
6.3.1. Если в графе G = (V, E) с n вершинами минимальная степень вершины равна δ, то
(a) Для любого p ∈ (0, 1) существует такое множество вершин A ⊂
V , что в объединении A и множества всех вершин, не соединённых
ни с какой вершиной из A, имеется не более np+n(1−p)δ+1 вершин.
(b) Существует такое множество вершин D ⊂ V , что любая вершина из V \D соединена ребром с некоторой вершиной из D, и
1 + ln(δ + 1)
|D| 6 n
.
δ+1
Для решения следующих задач 6.3.2 и 6.3.3.c нужна приведенная ниже теория. К их решению разумно вернуться после задачи
6.3.9.
( )
( )
n
k (m)
k
6.3.2. (a) Eсли
p 2 +
(1 − p)( 2 ) < 1 для некоторого p ∈
m
n
(0, 1), то R(m, n)(> k. )
n2
(b)* R(4, n) > Ω
(мы пишем g > Ω(f ), если f = O(g)).
ln2 n
6.3.3. (a) Cherchez la femme. На русско-французской встрече не
было представителей других стран. Суммарное количество денег у
французов оказалось больше суммарного количества денег у русских, и суммарное количество денег у женщин оказалось больше
суммарного количества денег у мужчин. Обязательно ли на встрече была француженка?
(b) Денежные купюры разного достоинства и разных стран упакованы в два чемодана. Средняя стоимость купюры равна 100 рублей.
6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
175
Общее число купюр в левом чемодане больше, чем в правом. Обязательно ли в левом чемодане найдется купюра стоимостью не более
200 рублей? (Ср. с неравенством Маркова 6.3.9.a.)
(c) Для любых целых l, q > 0 существует граф, не содержащий обходов длины менее l и который невозможно правильно раскрасить
в q цветов. (См. определение правильности раскраски в §3.1.)
Зафиксируем p ∈ (0, 1) и назовем вероятностью графа (в модели, или в вероятностном пространстве, Эрдеша-Реньи) c n вершинаn(n−1)
ми {1, 2, . . . , n} и e рёбрами число P(G) = Pp (G) := pe (1−p) 2 −e .
Вероятностью семейства (или, что то же самое, свойства) графов
с вершинами 1, 2, . . . , n называется сумма вероятностей входящих в
него графов.
Случайной величиной называется функция, определённая на множестве графов c вершинами 1, 2, . . . , n.
Например, количество рёбер графа — случайная величина.
Пусть случайная величина Y принимает k различных значений y1 , . . . , yk . Тогда математическим ожиданием (мат. ожиданием) случайной величины Y называется её «взвешенное среднее»
k
∑
ys P(Y −1 (ys )), где Y −1 (ys ) – множество всех графов G, для
EY :=
s=1
которых Y (G) = ys . Последнюю вероятность обозначают P(Y = ys ).
6.3.4. Для данных n и p вероятность наличия k вершин, между
которыми нет рёбер, меньше ek ln n−pk(k−1)/2 .
6.3.5. Для данных n и p найдите мат. ожидание количества
(a) изолированных вершин;
(b) треугольников;
(c) k-клик;
(d) k-клик, являющихся компонентами связности;
(e) гамильтоновых циклов;
(f) обходов длины k;
(g) обходов длины k, являющихся компонентами связности;
(h) деревьев с k вершинами;
(i) древесных компонент данного размера k, т.е. деревьев с k вершинами, являющихся компонентами связности.
176
Элементы дискретной математики в задачах
6.3.6. Для данного p найдите асимптотику (при постоянном k и
n → ∞) функции E(k) (Y ) := E (Y (Y − 1) . . . (Y − k + 1)) (т. е. k-го
факториального момента), если Y — число изолированных вершин.
Дисперсией случайной величины X называется число DX :=
E(X − EX)2 .
6.3.7. Для данных n и p найдите дисперсию количества (a) изолированных вершин; (b) треугольников.
6.3.8. (a) E(ξ + η) = Eξ + Eη;
(b) D(ξ + η) = Dξ + Dη, если ξ и η независимы.
6.3.9. Пусть X — случайная величина (определенная выше) и a >
0.
(a) Неравенство Маркова. P(|X| > a) 6 E|X|/a. (Ср. с задачей
6.3.3.a.)
(b) Неравенство Чебышева. P(|X − EX| > a) 6 DX/a2 .
Событие An происходит асимптотически почти наверное (или
с асимптотической вероятностью 1) относительно последовательности f (n), если Pf (n) (An ) → 1. Общепринятое сокращение: при
p(n) = f (n) событие An происходит а.п.н. (формально, эта фраза
не имеет смысла, поскольку означает «если p(n) = f (n), то событие An происходит а.п.н.», а без указания последовательности f (n)
фраза «событие An происходит а.п.н.» не может быть определена
как надо). Напомним, что здесь n — число вершин графа.
6.3.10. При p(n) = 1/(2n)
(a) а.п.н. имеется более n/2 изолированных вершин.
(b) для некоторого C > 0 а.п.н. каждая компонента связности
имеет менее C ln n вершин (специалисты говорят: менее O(ln n) вершин).
(c)* а.п.н. каждая компонента связности является деревом или унициклическим графом.
(d)* для некоторого C > 0 а.п.н. имеется менее C унициклических
компонент.
6. АНАЛИТИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ МЕТОДЫ
177
(
)
6.3.11. (a) При p(n) = o n−3/2 а.п.н. рёбра попарно не пересекаются.
(
)
(b) При p = p(n) = o n−3/2 и pn2 → ∞ существует такая функция r = r(n) = o(pn2 ), что а.п.н. число вершин степени 1 больше
pn2 − r и меньше pn2 + r, и остальные степени равны нулю.
6.3.12. Теорема о связности случайного графа. Если c > 1 (0 < c <
1), то при p(n) = c ln n/n а.п.н. случайный граф связен (несвязен).
6.3.13. (a) Найдите хотя бы одну такую функцию p∗ (n), что
• при p(n)/p∗ (n) → 0 а.п.н. граф не содержит треугольника, и
• при p(n)/p∗ (n) → +∞ а.п.н. граф содержит треугольник.
(b) То же с заменой треугольника на подграф, изоморфный K4 .
Замечание. Такая функция p∗ называется пороговой вероятностью. Пороговая вероятность существует для любого монотонного семейства. Монотонно возрастающим (убывающим) семейством
графов называется такое семейство графов, которое вместе с каждым графом содержит любой его надграф (подграф).
6.3.14. Хроматическое число графа а.п.н. не больше
(a) одного при p(n) = o(1/n2 );
(b) двух при p(n) = o(1/n);
(c) трёх при p(n) = c/n, где c < 1.
6.3.15. *
(a) Жадный алгоритм раскраски (см. задачу 3.2.3) для любого
положительного ε а.п.н. ошибается не более чем в 2 + ε раз.
(b) Для любых ε, δ > 0 существует такая последовательность Gn
графов с n вершинами, что при случайной нумерации вершин графа Gn вероятность того, что отношение числа цветов в жадной раскраске к χ(Gn ) больше n1−ϵ , больше δ. (Иными словами, с одной
стороны, почти для любого графа в любой нумерация жадная раскраска хороша, но, с другой стороны, есть графы, которые почти
как ни нумеруй, а все дрянь получится!)
(Приведите аккуратные формулировки самостоятельно.)
Замечание. См. подробнее [R3, R4, R5]. В частности, в [R4] доказаны следующие результаты.
7. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ
7
195
Алгебраические методы
7.1
Линейно-алгебраический метод в комбинаторике
Напомним, что для множества F
F n := {(a1 , a2 , . . . , an ) : a1 , a2 , . . . , an ∈ F }.
Элементы этого множества называются векторами (или наборами
или точками). Если F ∈ {Z2 , Z, Q, R}, то векторы можно покомпонентно складывать:
(x1 , . . . , xn ) + (y1 , . . . , yn ) := (x1 + y1 , . . . , xn + yn ).
Если F ∈ {Z, Q, R}, то вектор можно покомпонентно умножить на
число λ ∈ F :
λ(x1 , . . . , xn ) := (λx1 , . . . , λxn ).
(Это можно делать и для F = Z2 , но не интересно.)
7.1.1. Теорема о линейной зависимости.
(Z2 ) Среди любых n + 1 наборов длины n из нулей и единиц
найдется несколько (не ноль) наборов, покомпонентная сумма по
модулю два которых есть нулевой набор.
(Q) Для любых n + 1 векторов v1 , . . . , vn+1 ∈ Qn найдутся рациональные числа λ1 , . . . , λn+1 , не все равные нулю, для которых
λ1 v1 + . . . + λn+1 vn+1 = (0, . . . , 0).
(R) Аналог теоремы (Q) справедлив для вещественных, комплексных и целых чисел.
Наборы из задач 7.1.1.(Z2 ),(Q) называются линейно зависимыми — над Z2 и над Q соответственно. Линейная независимость
— отрицание линейной зависимости. Аналогично определяется линейная (не)зависимость многочленов над Z2 и Q соответственно.
(Эти и следующие понятия используются в формулировках задач
7.1.4.c, 7.1.5.c, 7.1.7.b и в решениях некоторых задач.)
Для F ∈ {Z2 , Z, Q, R} скалярное произведение F n × F n → F
определяется формулой
(x1 , . . . , xn ) · (y1 , . . . , yn ) := x1 y1 + . . . + xn yn .
196
Элементы дискретной математики в задачах
Векторы x, y ∈ F n называются ортогональными, если x · y = 0.
Расстояние между точками пространства Rn определяется формулой
√
|(x1 , . . . , xn ), (y1 , . . . , yn )| := (x1 − y1 )2 + . . . + (xn − yn )2 .
Линейным подпространством называется подмножество L ⊂
замкнутое относительно сложения векторов и умножения на
рациональные числа. Линейное подпространство L называется nмерным, если найдутся такие линейно независимые векторы
v1 , . . . , vn ∈ L, что любой вектор v ∈ L линейно выражается через
данные векторы, т. е. найдутся числа λ1 , . . . , λn ∈ Q, для которых
v = λ1 v1 +. . .+λn vn . Число n называют размерностью пространства
L. Ср. с определением перед задачей 1.4.7.
Замечание. Аналогичные определения можно дать и в более общей ситуации — это приводит к понятию кольца и модуля над ним.
Попытка доказать (и использовать!) аналог теоремы о линейной
зависимости (задачи 7.1.1.(Z2 ),(Q)) приводит к понятиям поля и
линейного пространства над ним. (Для случая целых чисел уже
не все обобщения проходят.) Подробности можно найти в учебнике
по линейной алгебре.
Qn ,
7.1.2. Дано семейство F подмножеств множества Rn .
(a) Если в каждом подмножестве из F нечётное число элементов,
а в пересечении любых двух подмножеств из F чётное число элементов, то |F| 6 n.
(b) Постройте пример, когда эта оценка достигается.
(c) Если в пересечении любых двух подмножеств из F ровно q
элементов и в каждом подмножестве из F более q элементов, то
|F| 6 n.
(d) Если q > 0 и в пересечении любых двух подмножеств из F
ровно q элементов, то |F| 6 n.
7.1.3. (a) Существуют 2k подмножеств 2k-элементного множества,
в каждом из которых чётное число элементов и в пересечении любых двух из которых чётное число элементов.
(b) Больше, чем 2k подмножеств, в условиях пункта (a) быть не
может.
7. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ
197
7.1.4. (a) Наибольшее число точек в Rn с равными попарными
расстояниями равно n + 1.
(b) Постройте n(n − 1)/2 точек в Rn , попарные расстояния между
которыми принимают только два различных значения.
(c) Для a ∈ R и точек v = (v1 , . . . , vn ) ∈ Rn , x = (x1 , . . . , xn ) ∈ Rn
обозначим Pv (x) := |x − v|2 − a2 . Если попарные расстояния между k точками u1 , . . . , uk ∈ Rn равны a, то многочлены Pu1 , . . . , Puk
линейно независимы над Q.
(d) Если попарные расстояния между k точками в Rn принимают
только два различных значения, то k 6 (n + 1)(n + 4)/2.
7.1.5. (a) Среди любых 327 попарно пересекающихся 9-элементных
подмножеств 25-элементного множества найдутся два подмножества, в пересечении которых ровно 3 или ровно 6 элементов.
(b) Для n, k ∈ Z обозначим
∑
n
Vn,k := {(x1 , . . . , xn ) ∈ {0, 1} :
xs = k}.
s
Среди любых 327 точек в V25,9 есть две, скалярное произведение
которых лежит в {0, 3, 6}.
(c) Для любого ⃗a ∈ V25,9 раскроем скобки в произведении
(⃗a · (x1 , x2 , . . . , x25 ) − 1)(⃗a · (x1 , x2 , . . . , x25 ) − 2),
где x1 , x2 , . . . , x25 — переменные. С каждым из полученных одночленов проведём следующую операцию: для каждого i если в одночлене есть множитель xni , то заменим этот множитель на xi . Полученный многочлен обозначим F⃗a (x1 , . . . , x25 ). Докажите, что если
скалярное произведение никаких двух векторов среди ⃗a1 , . . . , ⃗as ∈
V25,9 не делится на 3, то многочлены F⃗a1 , . . . , F⃗as линейно независимы над Q.
(d) Укажите 326 многочленов, линейными комбинациями которых
с рациональными коэффициентами можно получить каждый многочлен F⃗a , ⃗a ∈ V25,9 .
7.1.6. (a) Среди любых 107 пятиэлементных подмножеств 14-элементного множества найдутся два подмножества, в пересечении которых ровно 2 элемента.
198
Элементы дискретной математики в задачах
(b) То же для 93 подмножеств.
(c) То же для 92 подмножеств.
(d) Невозможно раскрасить в 21 цвет все пятиэлементные подмножества 14-элементного множества так, чтобы любые два пятиэлементные подмножества, пересекающиеся ровно по двум элементам,
были разноцветны.
(Ср. с замечанием в задаче 5.1.4. Вот эквивалентная формулировка. Вершинами графа являются все пятиэлементные подмножества
14-элементного множества. Его ребрами являются пары подмножеств, пересекающиеся ровно по двум элементам. Докажите, что
этот граф нельзя правильно раскрасить в 21 цвет.)
7.1.7. (a) Для простого p и целого t число G(t) := (t − 1)(t −
2) . . . (t−p+1) делится на p тогда и только тогда, когда t не делится
на p.
(b) Пусть p простое и n = 4p. Обозначим
M = {(1, y2 , y3 . . . , yn ) |
| yk ∈ {1, −1} и среди y2 , . . . , yn число минус единиц чётно}.
Обозначим G(t) := (t − 1)(t − 2) . . . (t − p + 1). Для любого ⃗a ∈ M
раскроем скобки в произведении G(⃗a · (1, x2 , . . . , xn )), где x2 , . . . , xn
— переменные. В каждом из полученных одночленов для каждого i
будем заменять x2i на 1, пока это возможно. Полученный многочлен
обозначим F⃗a (x2 , . . . , xn ).
Докажите, что если скалярное произведение никаких векторов среди ⃗a1 , . . . , ⃗as ∈ M не равно нулю, то многочлены F⃗a1 , . . . , F⃗as линейно независимы над Q.
(c) Существуют n и ограниченное подмножество в Rn , которое
невозможно разбить на n + 1 непустых частей меньшего диаметра.
7.1.8. (a) Теорема Франкла-Уилсона. Если t простое, то cреди люt−1 ( )
∑
n
бых различных 1+
подмножеств n-элементного множества,
j
j=0
в каждом из которых k-элементов, найдутся два подмножества, число элементов в пересечении которых делится на t.
(b) То же, только задано целое q и ‘делится на t’ заменено на
‘сравнимо с q по модулю t’.
218
Элементы дискретной математики в задачах
10
Графы: задачи для исследования
10.1
Степенные последовательности. А. Скопенков
0.* (a) Можно ли опустить какие-нибудь неравенства из задачи 5 так, чтобы достаточность (т.е. утверждение задачи 10) осталась верной? Если да, попробуйте найти минимальный набор неравенств.
(b) Если слить две степенные последовательности, то обязательно получится степенная последовательность. А какие степенные последовательности обладают тем свойством, что их нельзя разбить
на две степенные последовательности?
Граф называется планарным, если его можно нарисовать на
плоскости так, чтобы внутренности ребер (то есть ребра без их
концов) не пересекались и не самопересекались. Подробнее см. §3,
[P, S1].
1. (abcd*) То же, что в задаче 2 предыдущей темы, для планарных графов.
2. (abcd*) То же, что в задаче 2 предыдущей темы, для связных
планарных графов.
Тор, лист Мебиуса и сфера с ручками изображены на рис.
Тор, лист Мебиуса, цилиндр и сфера с ручками
Пусть на торе (или на сфере с ручками, или на диске с листами Мебиуса) нарисован без самопересечений граф. Назовем гранью
замкнутую область на торе, ограниченную ребрами этого графа.
Реализация графа на торе (или на сфере с ручками) называется клеточной, если каждая грань разбивается любой ломаной с
концами на границе этой грани (т.е. топологически эквивалентна
замкнутому диску на плоскости).
3. (abcd*) То же, что в задаче 2 предыдущей части, для связных
клеточно реализуемых на торе графов.
4. (abcd*) То же, что в задаче 2 предыдущей части, для связных
клеточно реализуемых на сфере с g ручками графов (g дано вместе
с n и d1 , . . . , dn ).
10. ГРАФЫ: ЗАДАЧИ ДЛЯ ИССЛЕДОВАНИЯ
219
Для получения необходимых условий в задачах 3 и 4 нужен следующий факт.
Формула Эйлера для сферы с g ручками. Пусть на сфере
с g ручками нарисован без самопересечений клеточно связный граф
с V вершинами и E ребрами. Пусть F — число граней. Тогда V −
E + F = 2 − 2g.
Для решения следующих задач 5 и 6 полезен аналог этого факта
для диска с m листами Мебиуса.
Реализация графа на листе Мебиуса (или на диске с листами Мебиуса, нарисованном на лекции) называется клеточной, если одна
грань топологически эквивалентна кольцу, а каждая из оставшихся
остальных — замкнутому диску на плоскости.
5. (abcd) То же, что в задаче 2 предыдущей части, для связных
клеточно реализуемых на листе Мебиуса графов.
6. (abcd) То же, что в задаче 2 предыдущей части, для связных
клеточно реализуемых на диске с m листами Мебиуса графов (m
дано вместе с n и d1 , . . . , dn ).
7-11. (abcd) То же, что в задачах 3-6, если требуется построить
граф с n гранями, в границе которых d1 , . . . , dn ребер, соответственно.
Пункты (a,b) задач 3-6 известны [Mo]. По-видимому, пункты (c)
этих задач неизвестны Пункты (d) этих задач неизвестны.
[Mo] B. Mohar, 2-cell embeddings with prescribed face lengths and
genus,
Ann.
Combin.
14
(2010)
525-532.
http://www.fmf.uni-lj.si/~mohar/Reprints/Inprint/BM06_AC_Mohar_
2cellEmbeddings.pdf.
10.2
Гамильтоновость (А. Веснин, А. Скопенков)
Цикл (путь) называется гамильтоновым, если он проходит через каждую вершину графа ровно по одному разу. Граф называется
гамильтоновым, если в нем есть гамильтонов цикл. См. подробнее
§2.6.
1. (a) Нарисуйте гамильтоновы циклы в графах правильных
многогранников.
220
Элементы дискретной математики в задачах
(b) Никакой граф, гомеоморфный букве θ (т.е. графу K3,2 ), не
является гамильтоновым.
Пусть H — граф. Граф X называется H-гамильтоновым, если в X существует подграф, содержащий все вершины графа X и
гомеоморфный графу H.
Следующая задача (кроме (f)) проста и приводится для того,
чтобы помочь решателю войти в курс дела. Задачи, отмеченные
звездочкой, являются нерешенными.
2. (a) Любой гамильтонов граф, отличный от окружности, является θ-гамильтоновым.
(b) Существует θ-гамильтонов граф, не являющийся гамильтоновым.
(c) Существует гамильтонов граф, отличный от окружности и
θ, не являющийся K4 -гамильтоновым.
(d) Существует K4 -гамильтонов граф, не являющийся θ-гамильтоновым.
(e) Для любых графов G и H существует G-гамильтонов граф,
не являющийся H-гамильтоновым.
(f)* Опишите "иерархию"графов по их гамильтоновости: когда
H-гамильтонов граф является G-гамильтоновым?
2’. (b,d*,e*,f*) То же, что в 2, для графов многогранников.
Граф Погорелова — граф выпуклого многогранника в трехмерном пространстве,
(1) из каждой вершины которого исходит три ребра,
(2) каждая замкнутая несамопересекающаяся ломаная на поверхности многогранника, разделяющая какие-либо две его грани,
пересекает по крайней мере пять ребер многогранника.
3. (Greenbergs) Постройте не гамильтонов граф Погорелова.
4. (a) Негамильтонов граф Погорелова из [Boll, Kokseter, Matematicheskie
esse i razvlecheniya, M, Mir, 1986, str. 285] является θ-гамильтоновым.
(b)* (гипотеза) Существует K4 -гамильтонов граф Погорелова,
не являющийся θ-гамильтоновым.
Идея доказательства: udalit’ trehvalentnuyu vershiny i na ee mesto
vkleit’ graf Greenbergsa s udalennoi vershinoi.
5.* (a) Опишите "иерархию"графов Погорелова по их гамильтоновости: когда H-гамильтонов гиперболический граф является
10. ГРАФЫ: ЗАДАЧИ ДЛЯ ИССЛЕДОВАНИЯ
221
G-гамильтоновым?
(b) (гипотеза) Для любого графа G существует граф Погорелова, не являющийся G-гамильтоновым. (Идея доказательства: "vkleivanie"grafa
Greenbergsa.)
(c) Для любых ли графов G и H существует G-гамильтонов граф
Погорелова, не являющийся H-гамильтоновым?
ва,
6.* Постройте минимальный (по числу граней) граф Погорело-
(a) являющийся K4 -гамильтоновым, но не θ-гамильтоновым.
(b) не являющийся K4 -гамильтоновым.
(c) не являющийся H-гамильтоновыми ни для какого подграфа
H данного графа G. (Например, G = K4 .)
10.3
Изоморфизмы графов. И.Н. Шнурников
Используемое здесь определение изоморфизма графов напомнено в [?].
1. (a) Сколько существует изоморфизмов K5 → K5 ? А K3,3 →
K3,3 ?
(b) Изоморфны ли графы G2 и G3 , вершины каждого из которых занумерованы числами от 1 до 7, вершины графа Gk соединены
ребром, если либо i − j ≡ 1 mod 7, либо i − j ≡ k mod 7.
(c) Постройте граф с наименьшим числом n > 1 вершин такой,
что никакая не тождественная перестановка его вершин не является
изоморфизмом.
2. Симметричные графы. Мы будем работать со связными ориентированными графами, из каждой вершины графа выходят два
ребра и в каждую входят два ребра. Такой граф назовем симметричным, если для любой пары ребер a, b существует перестановка вершин графа (а если есть кратные ребра, то и перестановка
их между собой), при которой все ребра графа переходят в ребра
этого же графа, а ребро a переходит в ребро b (направления всех
ребрах сохраняются). При этом никакое ребро не должно остаться
на месте.
(a) Для каждого натурального n придумайте два (неизоморфных) симметричных графа с n вершинами каждый.
222
Элементы дискретной математики в задачах
(b) Придумайте симметричные графы с 6, 12 и 30 вершинами,
не изоморфные графам из (a).
(c) Найдите все симметричные графы, которые имеют хотя бы
одну петлю или хотя бы одно кратное ребро.
(d) Найдите все симметричные графы с p-вершинами (p — простое число).
(e) Найдите все симметричные графы с не более, чем 8 вершинами.
(f) Найдите все симметричные графы, которые можно нарисовать (без самопересечений) на плоскости так, что для каждой вершины входящие ребра чередуются с выходящими.
(g)* Найдите все плоские симметричные графы.
3. У Васи есть несвязный граф. Он всеми возможными способами удалил из этого графа по одной вершине и каждый из полученных графов нарисовал на отдельном листочке бумаге, после чего
все листочки отдал Коле. Докажите, что Коля может восстановить
исходный граф.
4*. Нерешенные задачи о вершинной и реберной реконструируемости.
(a) Пусть G и G̃ — связные графы без петель и кратных ребер
с V > 3 занумерованными вершинами. Для каждого k ∈ {1, . . . , V }
рассмотрим графы G − k и G̃ − k, полученные из графов G и G̃
удалением в каждом из них вершины с номером k и всех выходящих из нее ребер. Пусть для всех k ∈ {1, . . . , V } графы Gk и G̃k
изоморфны. Верно ли, что графы G и G̃ изоморфны?
(b) Пусть G и G̃ — простые графы с E > 5 ребрами. Для каждого k ∈ {1, . . . , E} рассмотрим графы Gk и G̃k , полученные из графов
G и G̃ соответственно путем удаления в каждом из них ребра с номером k. Пусть для всех k ∈ {1, . . . , E} графы Gk и G̃k изоморфны.
Верно ли, что графы G и G̃ изоморфны?
10.4
Турниры. Д. Пермяков
Для решения основной задачи этого пункта потребуются некоторые навыки работы с графами. Перед этой серией полезно (но не
обязательно) прорешать пункт ’Пути в графах’.
10. ГРАФЫ: ЗАДАЧИ ДЛЯ ИССЛЕДОВАНИЯ
223
Ориентированный граф – граф, каждое ребро которого является стрелкой от одной вершины ребра к другой. Турнир — ориентированный граф, между любыми двумя вершинами которого есть
ровно одно ребро. Ориентированный граф называется сильносвязным, если от любой его вершины можно добраться до любой другой,
двигаясь по направлению стрелок на ребрах.
1. (Основная) Какое минимальное количество несамопересекающихся циклов длины k может быть в сильносвязном турнире с
n вершинами?
Эта задача сложная, к ней непросто подступиться. Обычно при
решении сложной задачи полезно рассмотреть частные случаи, попытаться решить близкие задачи. Это позволяет заметить закономерности, которые можно сформулировать в виде гипотез и затем
доказать. Мы не будем подсказывать эти гипотезы, а предлагаем
вам самим исследовать эту задачу и высказывать ваши предположения. Сформулируйте и докажите какую-нибудь лемму, которая,
по вашему мнению, поможет в решении задачи 1. После того, как
вы попробовали найти путь к решению самостоятельно, предлагаем
вам доказать следующие утверждения. Они могут оказаться полезными в решении Задачи 1 и, возможно, помогут довести его до
конца.
2. (a) Турнир сильносвязен тогда и только тогда, когда в нем
есть несамопересекающийся ориентированный цикл (т.е., цикл, идущий по направлениям стрелок на ребрах), проходящий по всем вершинам.
(b) В сильносвязном турнире через любую вершину проходит
несамопересекающийся ориентированный цикл любой длины от трех
до количества вершин турнира.
Ответы, указания и решения
10.1.1, 2. (a,b,c) То же, что в 11abc.
(d) Не знаем.
10.1.4. (a) e целое и e > n − 1 + 2g [Mo].
max di и e > n − 1 + 2g [Mo].
10.1.6. (a) e целое и e > n−1+m [Mo].
и e > n − 1 + m [Mo].
(b) e целое, e >
(b) e целое, e > max di
11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
11
233
Программа курса ДА 2014-16 уч. годов
Нужно уметь решать задачи, аналогичные пп. 2.1-2.7, 3.1, 3.2,
4.1, 4.2, 4.5, 5.1, 5.2, 5.5, 6.1-6.3, 7.1, 7.2 книги
Элементы дискретной математики в задачах, А.А. Глибичук,
А.Б. Дайняк, Д.Г. Ильинский, А.Б. Купавский, А.М. Райгородский,
А.Б. Скопенков, А.А. Чернов, Изд-во МЦНМО, 2016,
http://www.mccme.ru/circles/oim/discrbook.pdf
В скобках указана ориентировочная сложность пункта (или части пункта) программы. Формального смысла эти баллы не имеют.
Но мы надеемся, что они помогут студентам разумно организовать
подготовку к экзамену: не изучать более ‘сложных’ пунктов программы, пока не изучены более ‘простые’. Пунктами ‘на 5 и меньше’ студенты (и преподаватели) могут пользоваться в дальнейших
курсах (без повторения материала).
«Без доказательства» сокращается до «б/д». В пунктах программы приводятся ссылки на вышеуказанную книгу (или на имеющийся в ней список литературы или на другую литературу).
Образцы вопросов приведены после программы.
Глава 2. Графы (1-й семестр)
1. (4) Определение графа, графов с петлями и кратными ребрами. Ориентированые графы. Соотношение между числом вершин и
ребер дерева. (П. 2.1 и задачи 2.2.1.)
2. (5) Код Прюфера. Формула Кэли. (Задачи 2.2.3.a и 2.2.4.c.)
3. (6) Точная формула для числа унициклических графов. (Задача
2.2.5.b.)
4. (5) Определение плоских и планарных графов. Формула Эйлера (б/д). Примеры непланарных графов. Критерий Куратовского
планарности графов (б/д). (П. 2.4 и задачи 2.4.2.)
5. (6) Классификация правильных многогранников с точностью до
изоморфизма их графов. (Задачи 2.4.3.cdefg.) 6-раскрашиваемость
любой карты на плоскости. (Задача 2.4.4.a.)
234
Элементы дискретной математики в задачах
6. (3) Пути и циклы. Простые пути и циклы (обходы). (П. 2.1.)
Критерии эйлеровости графа и ориентированного графа. (Задачи
2.5.3.ac.)
7. (5) Последовательности и графы де Брёйна. Правило «ноль лучше единицы». (Задачи 2.5.5–2.5.8.)
8. (5) Гамильтоновы пути и циклы. Достаточное условие Дирака
гамильтоновости графа. (Задача 2.6.2.b.)
9. (6) Вершинная связность и число независимости графа. Достаточное условие гамильтоновости в их терминах. Гамильтоновость
графа 1-пересечений 3-элементных подмножеств n-элементного множества. (Задачи 2.6.3, 2.6.4 и 2.6.5.c.)
10. (3) Гамильтоновы цепи в турнирах. Нижняя оценка с доказательством, верхняя — без. (Задача 2.6.7.)
11. (5) Теорема Турана о числе ребер в графе с данным числом
вершин и числом независимости. Асимптотика наибольшего числа
ребер в графе с n вершинами без k-клик. (Задачи 2.7.1 и 6.1.2.)
12. (6) Оценка числа ребер у дистанционного графа на плоскости
и в пространстве произвольной размерности. Сравнение с теоремой
Турана. (Задачи 2.7.2, 2.7.4, 2.7.5.)
Глава 3. Раскраски графов (1-й семестр)
13. (5) Число независимости и кликовое число. Хроматическое число. Соотношения между хроматическим числом, числом независимости и кликовым числом. (Задача 3.1.3.)
Глава 4. Основы теории Рамсея (2-й семестр)
14. (3) Числа Рамсея R(s, t): точные значения для s + t 6 7. Рекуррентная верхняя оценка Эрдеша–Секереша. (Задачи 4.1.1, 4.1.2.ac.)
15. (4) Следствие рекуррентной верхней оценки Эрдеша–Секереша
для недиагональных и диагональных чисел Рамсея. Уточнение Конлона (б/д). Нижняя оценка диагональных чисел Рамсея с помощью
простого вероятностного метода. (Задачи 4.1.2.b, 4.1.5.)
11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
235
16. (5) Многоцветные числа Рамсея Rk (l1 , . . . , lr ) и их рекуррентная верхняя оценка. Следствие для R3 (s, t). Нижняя вероятностная
оценка для R3 (s, s). (Задачи 4.2.2.b, 4.2.7.)
17. (8) Верхняя оценка Конлона для двудольных чисел Рамсея:
лемма с конкретными l, m, r, s и ее аналог с последовательностями
(б/д); доказательство оценки с использованием леммы. (Есть оригинальная статья Conlon’а, скачивается с его домашней страницы.)
18. (8) Конструктивная нижняя оценка Франкла–Уилсона для R(s, s).
[R3]
19. (6) Замечание о распределении простых в натуральном ряде
и его роли в аккуратном доказательстве нижней оценки Франкла–
Уилсона для R(s, s). [R3]
Глава 5. Системы множеств (гиперграфы) (20-23 1-й семестр, 24-31 2-й семестр)
20. (5) Гиперграфы. Гиперграфы t-пересечений. Теорема Эрдеша–
Ко–Радо (о максимальном числе ребер в гиперграфе 1-пересечений);
б/д. (Задача 5.1.3.)
21. (7) Теорема Эрдеша–Ко–Радо. (Задача 5.1.3.)
( )
22. (7) Пример n−t
k−t подмножеств n-элементного множества, в каждом из которых ровно k элементов и любые два из которых пересекаются не менее чем по t элементам.
23. (7) История последовательных продвижений в задаче: теорема Эрдеша–Ко–Радо (общий случай), теорема Франкла, теорема
Уилсона, теорема Алсведе–Хачатряна (все б/д, но с подробными
комментариями). (Задачи 5.1.2, 5.1.3.)
24. (2) Системы общих представителей (с.о.п.). «Тривиальные» нижние и верхние оценки.
25. (5) Верхняя оценка (размера минимальной) с.о.п. с помощью
жадного алгоритма. (Задачи 5.2.1, 5.2.5, 5.2.6.a.)
26. (9) Конструктивная нижняя оценка с.о.п. (Задача 5.2.6.b.)
236
Элементы дискретной математики в задачах
27. (7) Нижняя оценка с.о.п. с помощью обобщенных с.о.п. (Задача
5.2.6.c.)
28. (10) Вероятностная нижняя оценка с.о.п. (Задача 5.2.6.def.) Следствие из нее.
29. (6) С.о.п. в геометрии (теорема о треугольниках на плоскости).
Размерность Вапника–Червоненкиса. (Задача 5.5.1.) Теорема Радона (б/д). Подсчет размерности семейства полупространств (Задача
5.5.2.bc.) Оценка числа подмножеств в семействе заданной размерности на n-элементном множестве. (Задача 5.5.9.) Лемма о размерности измельчения (с не очень подробными выкладками).
30. (8) Эпсилон-сети. Теорема Вапника–Червоненкиса об эпсилонсетях и теорема о треугольниках как частный случай.
31. (6) Теорема Вапника–Червоненкиса (б/д). Приложения в статистике: равномерная сходимость в ЗБЧ (УЗБЧ) и теорема Гливенко–
Кантелли как частный случай.
Глава 6. Аналитические и вероятностные методы (32-36
1-й семестр, 37-49 2-й семестр)
32. (3) Оценки для факториалов
( n )и биномиальных коэффициентов.
(Задача 6.1.7.a.) Оценки для n/2 с помощью тождества. (Задача
6.1.5.ab.)
√
33. (5) Асимптотика ln n! и n n! с доказательством без использования формулы Стирлинга. Формула Стирлинга (б/д). (Задача 6.1.6.)
( n )
34. (5) Оценка биномиальных коэффициентов вида [an]
, a ∈ (0, 1).
Аналогичный результат для полиномиальных коэффициентов. (Задача 6.1.5.cdef.)
( )
35. (5) Асимптотика для nk при k 2 = o(n).
( nОценки
) ( n той
) же величины при больших k. Асимптотики для n/2 / n/2−x . (Задача
6.1.7.bcde.)
36. (7) Асимптотика числа унициклических графов. (Задача 6.1.12.b.)
11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
237
37. (5) Симметричный и несимметричный случай ЛЛЛ (б/д). Вывод оценки диагонального числа Рамсея (теорема Спенсера). (Задачи 6.2.15, 6.2.21.b и 6.2.26.а.)
38. (6) Симметричный и несимметричный случай ЛЛЛ (с доказательством симметричного — либо напрямую, либо с доказательством несимметричного и выводом из него). (Задачи 6.2.15 и 6.2.26.а.)
39. (9) Вывод из несимметричного случая ЛЛЛ нижней оценки для
R(3, t): Самые точные известные оценки для R(3, t) (б/д). (Задача
6.2.26.b и замечание после нее.)
40. (5) Двудольные числа Рамсея: нижние оценки простым вероятностным методом и с помощью ЛЛЛ. Отличие нижних оценок
для двудольных чисел Рамсея от аналогичных нижних оценок для
R(s, t). (Литературы нет; делается совершенно аналогично тому,
как то же самое делается для обычных чисел Рамсея.)
41. (5) Случайные графы. Неравенства Маркова и Чебышёва. Неравенство для случайного блуждания. (п. 6.3, [R4, п. 1.11 и 1.12])
42. (5) Связность случайного графа (б/д). Случайные величины и
вероятностные неравенства, необходимые для доказательства. [R4,
п. 2.5]
43. (7) Связность случайного графа: случай p = c ln n/n при c < 1.
ln n + γ + o(1)
Теоремы о
и о гигантской компоненте (б/д). [R4, п.
n
2.5]
44. (8) Связность случайного графа: случай p = c ln n/n при c > 1.
[R4, п. 2.5]
45. (3) Теоремы Боллобаша о хроматическом числе случайного графа (б/д). Пояснения к ним: случаи p = o(1/n2 ) и p = o(1/n). [R4,
п. 2.6]
46. (9) Пояснения к теоремам Боллобаша о хроматическом числе
случайного графа: случай p = c/n, c < 1 (б/д) и случай, когда
функция из второй теоремы Боллобаша может стремиться к бесконечности. [R4, п. 2.6]
238
Элементы дискретной математики в задачах
47. (7) Сравнение оценок хроматического числа через кликовое
число и число независимости в терминах случайных графов: одна
«почти всегда» значительно лучше другой (распределение кликового числа и числа независимости). [R4, п. 2.7]
48. (10) Теорема о том, что почти наверное жадный алгоритм найдет множество, размер которого лишь, как максимум, в 2 раза отличается от реального. Теорема Кучеры о слабости жадного алгоритма на специальных графах (б/д). (А. Райгородский, "Экстремальные задачи теории графов и Интернет" , Интеллект.)
49. (9) Теорема Эрдеша о графе с большим обхватом и большим
хроматическим числом. (Задача 6.3.3.c.)
Глава 7. Алгебраические методы (50-58 1-й семестр, 5964 2-й семестр)
50. (4) Граф пересечений для полного однородного гиперграфа.
Его кликовое число и число независимости (б/д). (Задача 5.1.3.)
51. (5) Кнезеровский граф. Верхняя оценка его хроматического
числа. Простые нижние оценки. Примеры конкретных кнезеровских графов. Кликовое число и число независимости кнезеровского
графа. ([R7] := А. Райгородский, "Гипотеза Кнезера и топологический метод в комбинаторике МЦНМО.)
52. (6) Верхняя оценка хроматического числа кнезеровского графа.
Теорема Ловаса о хроматическом числе кнезеровского графа (б/д;
с доказательством — на ‘8’). [R7]
53. (7) Теорема Борсука–Улама–Люстерника–Шнирельмана в разных формулировках, но с доказательством только в случае плоскости и трехмерного пространства. [R7]
54. (6) Максимальное число m(n, k, t) подмножеств n-элементного
множества, в каждом из которых ровно k элементов и среди которых любые два множества пересекаются не по t элементам. Точное
значение для m(n, 3, 1): явная конструкция и оценка по индукции.
Линейно-алгебраическая оценка для m(n, 3, 1). Аналогичная оценка
для m(n, 5, 2) и ее асимптотическая неулучшаемость. [R1]
11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
239
55. Общая теорема Франкла–Уилсона об m(n, k, k − p) при k < 2p
(6). Замечание о непростом «модуле» (10). (Задача 7.1.8 и [R1].)
56. (только в 2015) (9) Теорема Франкла–Уилсона об m(n, k, k−p)
при k > 2p. [R1]
57. (только в 2015) (7) Точность обеих теорем Франкла–Уилсона
при постоянных k, t. Максимальное число k-элементных подмножеств n-элементного множества, из которых любые два множества
пересекаются не более чем по t элементам. Связь с теорией кодирования, теорема Редля (б/д). [R1]
58. (6) Хроматические числа пространств. Историческая справка.
Интерпретация величины m(n, k, t) как числа независимости дистанционного графа. Нижняя оценка хроматического числа пространства с помощью результатов для m(n, k, t). Возможные улучшения. ([R1] и А. Райгородский, "Хроматические числа".)
59. (3) Матрицы Адамара. Необходимое условие существования.
Гипотеза Адамара. Нормализация. (Задачи 7.2.1-7.2.3, определения
и гипотеза в §7.2, [Hal].)
60. (5) Неудачная попытка построить матрицу Адамара «строчка
за строчкой».
61. (5) Теорема о плотности порядков матрицы Адамара в натуральном ряде (б/д). [Hal, AS]
62. (6) Приложения матриц Адамара к задаче о раскраске
гипер√
графа: определение уклонения, верхняя оценка вида 2n ln(2s) с
√
доказательством и оценка вида 6 n (б/д). [R3]
63. (8) Приложения матриц Адамара к задаче о раскраске гиперграфа: нижняя оценка с помощью матриц Адамара. [R3]
64. (6) Интерпретация в терминах дистанционного графа, возникающего в теореме Франкла–Уилсона (клики и независимые множества).
240
Элементы дискретной математики в задачах
ОБРАЗЦЫ ВОПРОСОВ НА ЭКЗАМЕНЕ
Предварительная часть (вариант 2014 года). Нужен только ответ/формулировка; доказательства приводить не нужно.
( )
1. Найдите асимптотику биномиального коэффициента nk при
k 2 = o(n).
2. Найдите количество деревьев с данными n вершинами, с точностью до изоморфизма.
3. Дайте определение гамильтонова цикла в графе. (Можно использовать только определение графа. Если Вы используете другие
определения — например, цикла — то их тоже нужно дать.)
4. Сформулируйте теорему о хроматическом числе случайного
графа в модели G(n, p) при p = o(1/n) и n → ∞.
5. У дистанционного графа на плоскости 4n вершин, и среди
любых n+1 вершин есть ребро. Сформулируйте наилучшую оценку
на количество ребер такого графа, доказанную в курсе.
6. Найдите кликовое число графа, вершины которого — все 5элементные подмножества 20-элементного множества, и ребро между вершинами проводится в том и только в том случае, когда множества не пересекаются?
7. Найдите R4 (15, 4, 4, 4).
8. Найдите максимальную VC-размерность семейства подмножеств множества {1, . . . , 10} в каждом подмножестве которого более 5 элементов.
Основная часть (точно таких вопросов на экзамене не
будет). Здесь главное — не ответы, а доказательства. В частности, формулировки и доказательства всех используемых студентом результатов из курса ДА (в частности, всех результатов из
курса ДА, используемых для доказательства других результатов
из курса ДА). При этом можно пользоваться без доказательства
результатами из других курсов.
Вопрос из билета. Существует ли 57 подмножеств 60-элементного
множества, в каждом из которых 30 элементов, и любые два из которых пересекаются по 15 элементам?
(Если используется задача 7.2.4, то ее нужно доказать.)
Доп. вопрос попроще.
Каково наибольшее число ребер в
11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
241
графе с 52 вершинами, в котором среди любых 5 вершин есть 2, не
соединенные ребром?
(Если используется теорема Турана, то ее нужно доказать.)
Доп. вопрос посложней. Укажите функцию f (n), для которой R(n, n) & f (n). (Чем больше функция, тем выше Ваша оценка.)
(Если используется неравенство n! > (n/e)n (6.1.6.с) или ЛЛЛ
(6.2.15.b), то их нужно доказать; это неравенство доказывается без
использования формулы Стирлинга.)
ЗАРЕГИСТРИРУЙТЕСЬ - ЭТО БЕСПЛАТНО

Похожие документы