Хорошо известен критерий Понтрягина–Куратовского [22,
59], утверждающий, что граф не является планарным тогда и
только тогда, когда у него найдется подграф, гомеоморфный
полному графу K5 или полному двудольному графу K3,3 (точные определения см. ниже). <...> Скажем, что граф имеет крестовую
структуру, если в каждой вершине графа указано разбиение
четырех (полу)ребер, инцидентных вершине, графа на две пары
(формально) противоположных ребер, см. рис. <...> Когда можно такой граф вложить в плоскость, причем так,
чтобы формально противоположные ребра переходили в локально противоположные ребра на плоскости? <...> Васильева формулируется так: крестовый
граф не влож´
им в плоскость тогда и только тогда, когда у него
найдутся два цикла без общих ребер, имеющие ровно одну точку перекрестья (т. е. общую вершину, в которой оба цикла переходят с ребра на противоположное ребро). <...> Гипотеза Васильева и теорема Понтрягина–Куратовского
тесно связаны: ниже мы приводим в виде серии упражнений
схему вывода одного критерия планарности из другого. <...> Граф с крестовой структурой
Пусть дан крестовый граф, который не вкладывается в плоскость. <...> Так, например, используя поворачивающие обходы, мы можем закодировать хордовой диаграммой
каждый граф вне зависимости от количества его уникурсаль4
ных компонент, см. далее. <...> Кроме того, на языке поворачивающих обходов вопрос о планарности графа решается значительно
проще, чем в случае трансверсальных обходов. <...> В связи с этим
возникает естественный вопрос: как формульно связаны матрицы, описывающие один и тот же граф с точки зрения поворачивающих обходов и с точки зрения трансверсальных обходов? <...> Кроме того, трансверсальный обход у графа единствен (если
существует), а поворачивающих обходов может быть много. <...> Задача о вложении крестовых графов в поверхности естественным образом приводит к понятию атома как допускающего шахматную раскраску клеточного разбиения поверхности
четырехвалентным графом. <...> В классе <...>
Комбинаторная_топология_и_теория_графов_в_задачах_и_упражнениях__учебное_пособие.pdf
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
Международная научно-исследовательская лаборатория
«Дискретная и вычислительная геометрия» им. Б. Н. Делоне
Д.П. Ильютко, В. О. Мантуров, И.М. Никонов
Комбинаторная топология
и теория графов
в задачах и упражнениях
Допущено УМО по классическому университетскому
образованию в качестве учебного пособия для студентов
высших учебных заведений, обучающихся по направлению
010100 Математика
Ярославль
ЯрГУ
2013
Стр.1
УДК 519.1(075)
ББК B152.5я73-4+B174.2я73-4
И 48
Серия «Библиотека Делоне»
Главные редакторы: Н. П. Долбилин, Х. Эдельсбруннер,
А. О. Иванов
Редакторы: В.М. Бухштабер, В. Л. Дольников,
Р. Н. Карасёв, В. О. Мантуров, Н.Г. Мощевитин,
О.Р. Мусин, М.В. Невский, И. Х. Сабитов, М.И. Штогрин
Рецензенты:
А. В. Чернавский, д-р физ.-мат. наук, проф.;
кафедра дифференциальных уравнений и приложений
механико-математического факультета
МГУ им. М.В. Ломоносова
Ильютко, Денис Петрович.
И48 Комбинаторная топология и теория графов в задачах
и упражнениях : учебное пособие / Д. П. Ильютко,
В. О. Мантуров, И.М. Никонов; Яросл. гос. ун-т
им. П.Г. Демидова. — Ярославль: ЯрГУ, 2013. — 150 с.
ISBN 978-5-8397-0980-5
В учебном пособии представлены оригинальные задачи
по комбинаторной топологии и теории графов. Часть
задач была решена авторами и открывает новые направления
исследований. Приведены также некоторые нерешенные
задачи.
Учебное пособие рассчитано на студентов-математиков,
аспирантов-математиков и всех, кто интересуется комбинаторикой
и маломерной топологией.
УДК 519.1(075)
ББК B152.5я73-4+B174.2я73-4
Опубликовано за счет средств гранта Правительства РФ
по постановлению № 220, договор 11.G34.31.0053
Иллюстрации А.Т. Фоменко
Дизайн обложки выполнен К. Эдельсбруннер
ISBN 978-5-8397-0980-5
-ЯрГУ, 2013
c
Стр.2
Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1. ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1. Двумерные многообразия . . . . . . . . . . . . . 7
1.2. Эйлерова характеристика многообразия . . . . . 19
1.3. Фундаментальная группа и накрытия . . . . . . 20
1.4. Графы и эйлеровы циклы . . . . . . . . . . . . . 24
1.5. Планарные графы: формула Эйлера и теорема
Понтрягина–Куратовского . . . . . . . . . . . . . 28
1.6. Раскраски графов . . . . . . . . . . . . . . . . . . 30
2. КРЕСТОВЫЕ ГРАФЫ . . . . . . . . . . . . . . . . . . . 32
2.1. Введение . . . . . . . . . . . . . . . . . . . . . . . 32
2.2. Планарные крестовые графы . . . . . . . . . . . 35
2.3. Эквивалентность критериев планарности
Васильева и Понтрягина–Куратовского . . . . . 41
2.4. Гауссовы циклы и поворачивающие обходы . . . 61
2.5. Вложение крестовых графов в двумерные
поверхности . . . . . . . . . . . . . . . . . . . . . 81
3. МАКСИМАЛЬНО СИММЕТРИЧНЫЕ АТОМЫ . . . 88
3.1. Введение . . . . . . . . . . . . . . . . . . . . . . . 88
3.2. Максимально симметричные атомы . . . . . . . 90
3.3. Примитивные максимально симметричные атомы 98
3.4. Классификация максимально симметричных
атомов . . . . . . . . . . . . . . . . . . . . . . . . 109
4. ХРОМАТИЧЕСКИЕ ЧИСЛА ЦЕЛОЧИСЛЕННЫХ
И РАЦИОНАЛЬНЫХ РЕШЕТОК . . . . . . . . . . . . 114
4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . 114
4.2. Маломерные целочисленные решетки . . . . . . 118
4.3. Для каждого m рост числа χ(Zn,√2m)
полиномиален по n и имеет степень не больше m124
4.4. Нижние оценки для хроматических чисел
целочисленных решеток . . . . . . . . . . . . . . 130
4.5. Оценки для рациональных решеток Qn . . . . . 132
4.6. Раскраски некоторых конечных графов . . . . . 135
4.7. Оценки для решеток над алгебраическими
расширениями кольца Z . . . . . . . . . . . . . . 136
4.8. Некоторые открытые проблемы . . . . . . . . . . 137
149
Стр.149