Каково наименьшее число цветов, достаточное для раскраски любой карты, изображенной на сфере, таким образом, чтобы соседние страны были окрашены в разные цвета? Эта знаменитая «проблема четырех красок» еще в конце прошлого века была обобщена на случай карт, расположенных на произвольных поверхностях. И хотя сама проблема четырех красок более ста лет оставалась нерешенной, задача о раскраске карт для всех ориентируемых поверхностей, отличных от сферы, была недавно решена. Полное решение этой задачи и составляет основу книги Г. Рингеля — известного специалиста в области теории графов, внесшего большой вклад в решение задачи о раскраске карт. Книга написана доступно и будет полезна широкому кругу читателей, интересующихся современными проблемами математики.
Author(s): Г.Рингель
Publisher: Мир
Year: 1977
Language: Russian
Pages: 257
City: М.
Титул ......Page 4
Аннотация ......Page 5
Предисловие редактора перевода ......Page 6
Предисловие ......Page 8
1.1. Проблема четырех красок ......Page 12
1.2. Теорема о раскраске карт ......Page 14
1.3. Проблема нитей ......Page 17
1.4. Односторонние поверхности ......Page 20
2.1. Хроматическое число ......Page 24
2.2. Вращения графов ......Page 31
2.3. Ориентируемые случаи 7 и 10 ......Page 43
3.1. Элементы топологии ......Page 54
3.2. Полиэдры ......Page 56
3.3. Элементарные операции ......Page 63
3.4. Нормальная форма ориентируемых поверхностей ......Page 66
3.5. Нормальная форма неориентируемых поверхностей ......Page 70
3.6. Стандартные модели ......Page 73
3.7. Частичные полиэдры ......Page 77
4.1. Теорема о вложении ......Page 81
4.2. Двойственные полиэдры ......Page 88
4.3. Неравенство Хивуда ......Page 92
4.4. Род графов ......Page 95
4.5. Неориентируемый род графов ......Page 97
4.6. Бутылка Клейна ......Page 99
5.1. Треугольные вложения ......Page 106
5.2. Ориентируемые особые случаи ......Page 113
5.3. Краткое описание общего случая ......Page 120
6.1. Ориентируемый случай 4 ......Page 125
6.2. Арифметические гребни ......Page 129
6.3. Ориентируемый случай 1 ......Page 130
6.4. Цепные диаграммы ......Page 135
6.5. Ориентируемый случай 9 ......Page 138
7.1. Пример для п = 35 ......Page 141
7.2. Ориентируемый случай 11 ......Page 145
7.3. Проблема добавления соседства ......Page 152
7.4. Ориентируемый случай 2 ......Page 156
7.5. Проблема добавления соседства ......Page 160
7.6. Ориентируемый случай 8 ......Page 164
8.1. Метод удвоения ......Page 176
8.2. Неориентируемые случаи 0, 3, 7 ......Page 181
8.3. Каскады ......Page 184
8.4. Приложение к ориентируемым случаям ......Page 194
9.1. Примеры и метод ......Page 197
9.2. Ориентируемые случаи 3-й 5 ......Page 204
9.3. Ориентируемый случай 6 ......Page 208
9.4. Неориентируемый случай 9 ......Page 211
10.1. Индукция индекса 3 ......Page 213
10.2. Индукция индекса 2 ......Page 220
10.3. Неориентируемые случаи 1, 2, 6 и 10 ......Page 224
11.1. Токи из неабелевых групп ......Page 227
11.2. Примеры . ......Page 228
11.3. Общее решение ......Page 234
12.1. Вопросы о вращениях ......Page 239
12.2. Вопросы о вложениях ......Page 241
Список литературы ......Page 247
Предметный указатель ......Page 254
Оглавление ......Page 256
