Теория графов

Обложка......Page 1
Титульный лист оригинального издания......Page 2
Титульный лист......Page 3
Аннотация и выходные данные......Page 4
Посвящение......Page 5
Сведения об авторе......Page 6
Оглавление......Page 7
Предисловие......Page 10
Глава 1. Основные понятия......Page 15
1.1. Графы......Page 16
1.2. Степень вершины......Page 19
1.3. Пути и циклы......Page 20
1.4. Связность......Page 24
1.5. Деревья и леса......Page 27
1.6. Двудольные графы......Page 29
1.7. Стягивание и миноры......Page 31
1.8. Эйлеровы обходы......Page 33
1.9. Немного линейной алгебры......Page 35
1.10. Другие виды графов......Page 40
Упражнения......Page 41
Примечания......Page 43
2.1. Паросочетания в двудольных графах......Page 44
2.2. Паросочетания в произвольных графах......Page 50
2.3. Покрытия путями......Page 55
Упражнения......Page 57
Примечания......Page 58
3.1. 2-Связные графы и подграфы......Page 59
3.2. Структура 3-связных графов......Page 61
3.3. Теорема Менгера......Page 66
3.4. Теорема Мадера......Page 72
3.5. Не пересекающиеся по ребрам остовные деревья......Page 74
3.6. Пути между заданными парами вершин......Page 78
Упражнения......Page 80
Примечания......Page 82
Глава 4. Планарные графы......Page 84
4.1. Топологические предпосылки......Page 85
4.2. Плоские графы......Page 87
4.3. Изображения......Page 94
4.4. Планарные графы. Теорема Куратовского......Page 98
4.5. Алгебраические критерии планарности......Page 103
4.6. Двойственность на плоскости......Page 105
Упражнения......Page 108
Примечания......Page 110
Глава 5. Раскраска......Page 112
5.1. Раскраска карт и плоских графов......Page 113
5.2. Раскраска вершин......Page 115
5.3. Раскраска ребер......Page 121
5.4. Предписанная раскраска......Page 123
5.5. Совершенные графы......Page 129
Упражнения......Page 136
Примечания......Page 139
Глава 6. Потоки......Page 142
6.1. Циркуляции......Page 143
6.2. Потоки в сетях......Page 144
6.3. Потоки со значениями в группе......Page 147
6.4. $k$-Потоки для малых $k$......Page 152
6.5. Двойственность между потоками и раскрасками......Page 155
6.6. Гипотезы Татта о потоках......Page 159
Упражнения......Page 163
Примечания......Page 165
Глава 7. Подструктуры в плотных графах......Page 166
7.1. Подграфы......Page 168
7.2. Лемма Семереди о регулярности......Page 172
7.3. Применение леммы регулярности......Page 180
Упражнения......Page 185
Примечания......Page 187
Глава 8. Подструктуры в разреженных графах......Page 188
8.1. Топологические миноры......Page 189
8.2. Миноры......Page 198
8.3. Гипотеза Хадвигера......Page 200
Упражнения......Page 204
Примечания......Page 205
Глава 9. Теория Рамсея для графов......Page 207
9.1. Первоначальные теоремы Рамсея......Page 208
9.2. Числа Рамсея......Page 212
9.3. Индуцированные теоремы Рамсея......Page 215
9.4. Рамсеевские свойства и связность......Page 227
Упражнения......Page 229
Примечания......Page 230
10.1. Простые достаточные условия......Page 232
10.2. Гамильтоновы циклы и степенные последовательности......Page 235
10.3. Гамильтоновы циклы в квадрате графа......Page 237
Упражнения......Page 246
Примечания......Page 247
Глава 11. Случайные графы......Page 249
11.1. Понятие случайного графа......Page 250
11.2. Вероятностный метод......Page 256
11.3. Свойства почти всех графов......Page 258
11.4. Пороговые функции и вторые моменты......Page 263
Упражнения......Page 268
Примечания......Page 270
12.1. Правильное квазиупорядочение......Page 272
12.2. Теорема о минорах графов для деревьев......Page 274
12.3. Древесные разложения......Page 276
12.4. Древесная ширина и запрещенные миноры......Page 285
12.5. Теорема о минорах графов......Page 297
Упражнения......Page 301
Примечания......Page 304
Указания ко всем упражнениям......Page 306
Список основных обозначений......Page 321
Предметный указатель......Page 323
Выходные данные......Page 336