Каково наименьшее число цветов, достаточное для раскраски любой карты, изображенной на сфере, таким образом, чтобы соседние страны были окрашены в разные цвета? Эта знаменитая «проблема четырех красок» еще в конце прошлого века была обобщена на случай карт,. расположенных на произвольных поверхностях, И хотя сама проблема четырех красок более ста лет оставалась нерешенной, задача о раскраске карт для всех ориентируемых поверхностей, отличных от сферы, была недавно решена. Полное решение этой задачи и составляет основу книги Г. Рингеля — известного специалиста в области теории графов, внесшего большой вклад в решение задачи о раскраске карт.
Книга написана доступно и будет полезна широкому кругу читателей, интересующихся современными проблемами математики.
**
ОГЛАВЛЕНИЕ
Предисловие редактора перевода 5
Предисловие 7
1. ПРОБЛЕМЫ, ИЛЛЮСТРАЦИИ, ИСТОРИЯ 11
1.1. Проблема четырех красок 11
1.2. Теорема о раскраске карт 13
1.3. Проблема нитей 16
1.4. Односторонние поверхности 19
2. ТЕОРИЯ ГРАФОВ 23
2.1. Хроматическое число 23
2.2. Вращения графов 30
2.3. Ориентируемые случаи 7 и 10 . 42
3. КЛАССИФИКАЦИЯ ПОВЕРХНОСТЕЙ 53
3.1. Элементы топологии 53
3.2. Полиэдры 55
3.3. Элементарные операции . 62
3.4. Нормальная форма ориентируемых поверхностей 65
3.5. Нормальная форма неориентируемых поверхностей 69
3.6. Стандартные модели 72
3.7. Частичные полиэдры - 76
4. ГРАФЫ НА ПОВЕРХНОСТЯХ 80
4.1. Теорема о вложении 80
4.2. Двойственные полиэдры . 87
4.3. Неравенство Хивуда 91
4.4. Род графов . 94
4.5. Неориентируемый род графов 96
4.6. Бутылка Клейна 98
5. КОМБИНАТОРИКА ВЛОЖЕНИЙ 105
5.1. Треугольные вложения 105
5.2. Ориентируемые особые случаи . . 112
5.3. Краткое описание общего случая 119
6. ОРИЕНТИРУЕМЫЕ СЛУЧАИ 1, 4 И 9 124
6.1. Ориентируемый случай 4 124
6.2. Арифметические гребни 128
6.3. Ориентируемый случай 1 129
6.4. Цепные диаграммы 134
6.5. Ориентируемый случай 9 .137
7. ОРИЕНТИРУЕМЫЕ СЛУЧАИ 11, 2 И 8 140
7.1. Пример для п = 35 ... 140
7.2. Ориентируемый случай 11 144
7.3. Проблема добавления соседства 151
7.4. Ориентируемый случай 2 155
7.5. Проблема добавления соседства . 159
7.6. Ориентируемый случай 8 163
8. НЕОРИЕНТИРУЕМЫЕ СЛУЧАИ (ИНДЕКС 1) 175
8.1. Метод удвоения 175
8.2. Неориентируемые случаи 0, 3, 7 180
8.3. Каскады 183
8.4. Приложение к ориентируемым случаям 193
9. РЕШЕНИЯ ИНДЕКСА 2 И 3 196
9.1. Примеры и метод 196
9.2. Ориентируемые случаи Зи5 203
9.3. Ориентируемый случай 6 207
9.4. Неориентируемый случай 9 210
10. ИНДУКТИВНЫЕ КОНСТРУКЦИИ 212
10.1. Индукция индекса 3 . 212
10.2. Индукция индекса 2 219
10.3. Неориентируемые случаи 1, 2, 6 и 10 223
11. ОРИЕНТИРУЕМЫЙ СЛУЧАЙ 0 226
11.1. Токи из неабелевых групп 226
11.2. Примеры . 227
11.3. Общее решение 233
12. РОДСТВЕННЫЕ ПРОБЛЕМЫ 238
12.1. Вопросы о вращениях 238
12.2. Вопросы о вложениях 240
Список литературы . . 246
Предметный указатель . 253
