Карта → событие
Четыре краски: 124-летний сериал
Вопрос
23 октября 1852 года Огастес де Морган пишет письмо Уильяму Роуэну Гамильтону:
Один мой студент попросил меня сегодня объяснить факт, который я не знал за факт и не знаю до сих пор. Он говорит, что если фигуру произвольно разделить и части раскрасить так, чтобы соседние по границе имели разные цвета, то четырёх цветов может понадобиться, но не более.
Студент — Фрэнсис Гатри, заметивший это, раскрашивая карту графств Англии; вопрос он передал через брата Фредерика, слушавшего де Моргана.
ГамильтонУильям Роуэн ГамильтонПятнадцать лет искал, как умножать тройки чисел, и однажды на мосту в Дублине понял, что надо взять четвёрки и отказаться от коммутативности. ответил сухо: «Я не собираюсь заниматься вашим „четверным цветом“ в ближайшее время». Так началась история, растянувшаяся на 124 года.
Точная формулировка. Соседними считаются области, имеющие общий участок границы (а не только точку); каждая область связна. Тогда четырёх цветов достаточно.
Оба условия существенны. Если разрешить областям состоять из нескольких кусков (как Калининградская область и остальная Россия), четырёх красок не хватит. Если соседством считать касание в точке, то у «пирога», разрезанного на много секторов, все части попарно соседи — и цветов понадобится сколько угодно.
Перевод на графы
Первый ход — избавиться от карты. Поставим в каждой области точку, соединим точки соседних областей рёбрами. Получится планарный граф — граф, который можно нарисовать на плоскости без пересечения рёбер.
Задача превращается в такую: вершины планарного графа можно раскрасить в четыре цвета так, чтобы смежные вершины были разного цвета.
Тот же приём, что у Эйлера с мостами: выбросить всё, кроме структуры соединений.
Ключевая лемма
Всё дальнейшее опирается на одно наблюдение, вытекающее из формулы Эйлера.
Лемма. В любом планарном графе есть вершина степени не больше пяти.
Доказательство. Пусть граф связен, имеет $V$ вершин, $E$ рёбер и $F$ граней, $V-E+F=2$. Каждая грань ограничена не менее чем тремя рёбрами, каждое ребро принадлежит ровно двум граням, значит $2E\geqslant3F$, откуда $F\leqslant\frac23E$. Подставляя:
$$2=V-E+F\leqslant V-E+\tfrac23E=V-\tfrac13E\quad\Longrightarrow\quad E\leqslant3V-6 .$$
Сумма степеней всех вершин равна $2E\leqslant6V-12<6V$. Значит, средняя степень меньше шести, и хотя бы одна вершина имеет степень не больше пяти. $\blacksquare$
Теорема о пяти красках
Из леммы за полстраницы получается почти то, что нужно. Приведём доказательство целиком — оно школьное и красивое.
Теорема. Всякий планарный граф раскрашивается в пять цветов.
Доказательство индукцией по числу вершин. Для малых графов очевидно. Пусть утверждение верно для графов с $n-1$ вершиной; возьмём граф с $n$ вершинами.
По лемме есть вершина $v$ степени не больше пяти. Уберём её; оставшийся граф раскрашивается пятью цветами по предположению индукции. Вернём $v$ обратно.
Если среди соседей $v$ использовано не более четырёх цветов — берём пятый, и всё. Остаётся случай, когда соседей ровно пять и все они разного цвета. Обозначим их по кругу $v_1,\dots,v_5$ с цветами $1,\dots,5$.
Рассмотрим цепь Кемпе: множество вершин, покрашенных в цвета 1 и 3 и связанных с $v_1$ путём, идущим только по вершинам этих двух цветов.
- Случай А: $v_3$ в эту цепь не входит. Тогда во всей цепи поменяем цвета 1 и 3 местами. Раскраска останется правильной (внутри цепи цвета переставились согласованно, а снаружи соседей цветов 1 и 3 у цепи нет по построению). Теперь $v_1$ имеет цвет 3, и цвет 1 освободился для $v$. Готово.
- Случай Б: $v_3$ входит в цепь, то есть существует путь из $v_1$ в $v_3$ через вершины цветов 1 и 3. Вместе с вершиной $v$ этот путь образует замкнутый контур. Вершины $v_2$ и $v_4$ лежат по разные стороны от него — одна внутри, другая снаружи. Значит, цепь Кемпе из $v_2$ по цветам 2 и 4 не может дойти до $v_4$: ей пришлось бы пересечь контур, а граф планарный. Применяем к ней перекраску — и освобождается цвет 2. $\blacksquare$
Обратите внимание на то, где именно использована планарность: в случае Б, там, где сказано, что пути не пересекаются. Это единственное место — и именно оно ломается при попытке провести то же рассуждение для четырёх цветов.
Одиннадцать лет ошибки
В 1879 году лондонский адвокат и математик-любитель Альфред Кемпе опубликовал доказательство четырёхкрасочной теоремы, устроенное точно так же, но с двумя цепями сразу. Работа была принята, Кемпе избран в Королевское общество.
В 1890 году Перси Хивуд обнаружил ошибку: в случае, когда обе цепи приходится перекрашивать одновременно, перекраски мешают друг другу, и рассуждение разваливается. Хивуд построил конкретную конфигурацию, где аргумент Кемпе не проходит.
Из обломков он спас теорему о пяти красках — ровно ту, что доказана выше: она использует одну цепь и от ошибки не страдает. И тридцать лет спустя доказал ещё один результат, показывающий, что задача не безнадёжна вообще: на торе всякая карта раскрашивается семью красками, и семь необходимо.
Любопытная асимметрия: на бублике задача решена полностью и давно, а на сфере — только машиной и через век. Более сложная поверхность оказалась проще.
Идея Кемпе, впрочем, не пропала: цепи Кемпе остались рабочим инструментом и вошли в окончательное доказательство Аппеля и Хакена.
Что ещё родилось в эту эпоху
Теория графов набирается материалом не только из этой задачи. О трёх сюжетах стоит сказать отдельно — все три понадобятся дальше в линии.
КэлиАртур КэлиЧетырнадцать лет работал адвокатом и между делами написал двести пятьдесят математических работ, а заодно придумал слово «матрица» и абстрактное определение группы. считает деревья (1857–1875). Артур Кэли — тот же, что ввёл абстрактную группу, — занялся подсчётом деревьев, и мотивировка была химической: сколько существует изомеров углеводорода $C_nH_{2n+2}$? Каждый такой изомер — дерево, и вопрос чисто комбинаторный. Отсюда формула Кэли: число помеченных деревьев на $n$ вершинах равно $n^{n-2}$. Проверьте на $n=3$: получается 3 — и действительно, дерево из трёх вершин задаётся выбором центральной.
Борувка строит первый алгоритм на графах (1926). Отакар Борувка в Брно решал практическую задачу: как электрифицировать Моравию, соединив все населённые пункты сетью наименьшей общей длины. Это задача о минимальном остовном дереве, и он предложил для неё алгоритм — по-видимому, первый алгоритм на графах в истории. Позже те же задачи решат Ярник, Прим и Крускал; алгоритм Борувки, между прочим, оказался легко распараллеливаемым и потому вернулся в обиход в 2000-е.
ПонтрягинЛев Семёнович ПонтрягинОслеп в тринадцать лет и всё считал в уме; построил двойственность топологических групп, характеристические классы и принцип максимума — три вещи из разных наук, каждая из которых пережила автора. и Куратовский описывают все непланарные графы (1927 и 1930). Доказанное выше неравенство $E\leqslant3V-6$ сразу даёт пример графа, который на плоскости не нарисовать: у полного графа $K_5$ пять вершин и десять рёбер, а $3\cdot5-6=9$. Непланарен и $K_{3,3}$ — это старинная головоломка о трёх домиках и трёх колодцах. Замечательно, что этими двумя примерами дело и исчерпывается:
Теорема Понтрягина — Куратовского. Граф планарен тогда и только тогда, когда он не содержит подразбиения $K_5$ или $K_{3,3}$.
Подразбиение — тот же граф, у которого на рёбрах расставлены лишние вершины степени 2; нарисовать его на плоскости можно ровно тогда же, когда исходный. Есть и равносильная формулировка через миноры (Вагнер, 1937), из которой через полвека вырастет теория графовых миноров Робертсона и Сеймура.
Про имя стоит сказать отдельно. Лев Понтрягин доказал этот критерий в 1927 году, студентом Московского университета, незрячим с четырнадцати лет, — и не напечатал. Казимеж Куратовский опубликовал доказательство в 1930-м; тогда же и независимо теорему получили Оррин Фринк и Пол Смит, тоже не доведя дело до полной публикации. Поэтому в мире её называют теоремой Куратовского, а в русских учебниках — Понтрягина — Куратовского. Честны оба названия: приоритет и публикация здесь разошлись.
И это не единственный такой случай на нашей карте. Бюрги вычислил логарифмы раньше Непера и не напечатал; ГауссКарл Фридрих Гаусс«Король математиков», у которого напечатанное было заметно меньше сделанного: половина результатов пролежала в дневнике до самой смерти — включая неевклидову геометрию. записал быстрое преобразование Фурье в тетрадь, изданную посмертно; Кокс придумал RSA и положил в сейф. Правило выходит суровое: науке достаётся то, что рассказано. Понтрягину досталась половина названия — и то лишь дома.
Задача. Постройте карту, для которой трёх красок недостаточно, и убедитесь, что четырёх хватает.
(Указание: четыре области, попарно соседние, — например, три сектора вокруг центральной области. Соответствующий граф — полный граф $K_4$, он планарен и требует ровно четырёх цветов. А пяти попарно соседних областей на плоскости не бывает: им отвечал бы $K_5$ с пятью вершинами и десятью рёбрами, а по доказанному выше $E\leqslant3V-6=9$.)
Следующая точка: Дублин — где зададут внешне такой же вопрос, у которого не окажется простого ответа.