Часть VII · Случай и данные Глава 46 из 60
Графы
Прогулка по городу: мосты, перекрёстки, дороги и карты. Эйлер оставил от города только точки и линии между ними — и решил задачу о мостах. Тем же приёмом сегодня прокладывают маршруты, составляют расписания и раскрашивают карты.
Опирается на: 45 · Комбинаторика
Вы научитесь
- переводить задачи о мостах, дорогах и знакомствах на язык графов
- по степеням вершин решать, можно ли обойти все рёбра графа по одному разу
- находить кратчайший путь алгоритмом Дейкстры и самую дешёвую сеть дорог
- доказывать с помощью формулы Эйлера, что граф нельзя нарисовать без пересечений
Прошлая глава закончилась прогулкой по Кёнигсбергу XVIII века. Город стоял на реке Прегель. Посреди реки лежал остров Кнайпхоф с кафедральным собором (сегодня это остров Канта в Калининграде), чуть восточнее — второй остров, Ломзе. Берега и острова соединяли семь мостов. Горожане спорили: можно ли пройти по городу так, чтобы по каждому мосту пройти ровно один раз? Возвращаться в начало не обязательно, плыть и перепрыгивать нельзя.
Попробуйте сами, прежде чем читать дальше. Выберите, откуда начать, и касайтесь мостов по очереди.
Семь мостов
Задача дошла до Леонарда Эйлера, который тогда работал в Петербургской академии наук, через бургомистра Данцига Карла Элера. В августе 1735 года Эйлер представил академии решение, а в академических «Комментариях» статья вышла в томе за 1736 год. Сам он считал задачу не вполне математической. В письме Элеру весной 1736 года Эйлер заметил, что решение держится на одном рассуждении и не зависит ни от каких математических принципов, так что непонятно, почему его ждут именно от математика. Эта «не математическая» задача и положила начало новой области математики — теории графов.
Главный шаг Эйлера — выбросить всё лишнее. Неважно, какой ширины река, какой длины мосты и где стоит собор. Важно только, какие куски суши соединены какими мостами. Каждый кусок суши можно стянуть в точку, каждый мост — в линию между двумя точками. Получится картинка из четырёх точек и семи линий. Нарисовать её можно как угодно криво: задача от этого не изменится. Сам Эйлер картинок с точками не рисовал, он обозначал куски суши буквами, а переходы по мостам — парами букв. Но суть та же.
Граф — набор точек, которые называют вершинами, и линий между ними, которые называют рёбрами. Каждое ребро соединяет две вершины. Важно только, что с чем соединено; где стоят точки и как изогнуты линии, значения не имеет.
Не путайте граф с графиком функции из главы о функциях: слова родственные, а смысл разный.
В задаче о мостах между двумя вершинами бывает несколько рёбер: остров Кнайпхоф связан с северным берегом двумя мостами. Такие кратные рёбра мы разрешаем. А вот графы из задачи о шести гостях, где каждая пара соединена ровно одним отрезком, — это тоже графы, только простые.
Считаем концы
Эйлер рассуждал так. Пусть прогулка существует. Посмотрим на кусок суши, где она не начинается и не заканчивается. Всякий раз, когда мы приходим на него по мосту, мы уходим с него по другому мосту. Значит, мосты у такого куска разбиваются на пары «вход — выход», и их чётное число. Нечётное число мостов может быть только у начала и у конца прогулки.
Теперь посчитаем мосты в Кёнигсберге. У Кнайпхофа их пять, у каждого берега по три, у Ломзе три. Все четыре числа нечётные. А кусков суши с нечётным числом мостов может быть не больше двух: начало и конец. Прогулки не существует. Для этого ответа не понадобилось перебирать ни одного маршрута.
Степень вершины — число рёбер, которые из неё выходят. Вершины бывают чётные и нечётные — по чётности степени.
Сложим степени всех вершин Кёнигсберга: $5 + 3 + 3 + 3 = 14$. Мостов семь, а сумма вдвое больше. Это не совпадение.
В любом графе сумма степеней всех вершин равна удвоенному числу рёбер.
Идея: посчитать одни и те же объекты двумя способами. Объекты — концы рёбер. Отметим у каждого ребра оба его конца точками. На рисунке семь мостов Кёнигсберга, у каждого две точки.
Первый способ: пройдём по вершинам. У вершины столько точек, сколько рёбер из неё выходит, то есть её степень (петлю, ребро из вершины в себя, её два конца учитывают дважды — так и устроено определение степени). Всего точек — сумма степеней: $5 + 3 + 3 + 3 = 14$.
Второй способ: пройдём по рёбрам. У каждого ребра ровно две точки, поэтому всего их $2E$. Здесь $7 \cdot 2 = 14$.
Мы посчитали одни и те же точки двумя способами, значит, результаты равны: $\sum_v \deg v = 2E$. Тот же довод в главе о комбинаторике считал рукопожатия: каждое рукопожатие — ребро, и его «концы» — две руки.
В любом графе число вершин нечётной степени чётно.
Разобьём сумму степеней на две части: по чётным вершинам и по нечётным. Первая часть чётна как сумма чётных чисел. Вся сумма чётна по лемме о рукопожатиях. Значит, и вторая часть — разность двух чётных чисел — чётна. Но это сумма нечётных чисел, а сумма нечётных чисел чётна только тогда, когда их чётное количество.
В компании семь человек. Может ли быть, что каждый из них знаком ровно с тремя другими?
Люди — вершины, знакомства — рёбра. Сумма степеней была бы $7 \cdot 3 = 21$, а она обязана быть чётной: это удвоенное число рёбер. А вот в компании из восьми человек каждый может знать ровно троих.
В графе девять вершин: у четырёх степень $3$, у трёх — степень $4$, у двух — степень $5$. Сколько у него рёбер?
Сумма степеней: $4 \cdot 3 + 3 \cdot 4 + 2 \cdot 5 = 12 + 12 + 10 = 34$. Рёбер вдвое меньше: $34 / 2 = 17$.
Правило Эйлера
Эйлер доказал, что в Кёнигсберге прогулка невозможна, и заметил, что того же подсчёта хватает для любого города. Сформулируем его результат на языке графов. Нам понадобятся ещё два слова.
Связный граф — граф, в котором из любой вершины можно добраться по рёбрам до любой другой. Эйлеров путь — маршрут, который проходит по каждому ребру ровно один раз. Если он заканчивается там же, где начался, его называют эйлеровым циклом.
В связном графе эйлеров цикл есть тогда и только тогда, когда степени всех вершин чётные. Эйлеров путь, который не замыкается, есть тогда и только тогда, когда нечётных вершин ровно две; он начинается в одной из них и заканчивается в другой.
Необходимость условия и есть рассуждение Эйлера о входах и выходах. Достаточность он считал ясной, а аккуратное доказательство опубликовали только в 1873 году, по записям рано умершего немецкого математика Карла Хирхольцера. Вот доказательство целиком, в обе стороны.
Необходимость. Пусть обход есть. Возьмём вершину, где он не начинается и не заканчивается. Каждый раз, приходя в неё по ребру, обход уходит по другому ребру, и каждое ребро используется один раз. Рёбра этой вершины разбиваются на пары «вход — выход», поэтому её степень чётна. Если обход замкнут, то же верно и для начальной вершины: первый выход в пару к последнему входу. Значит, у замкнутого обхода все степени чётные, а у незамкнутого нечётными могут быть только начало и конец.
Достаточность. Пусть граф связный и все степени чётные. Выйдем из любой вершины $A$ и пойдём по непройденным рёбрам куда угодно, пока можно. Застрять мы можем только в $A$: входя в любую другую вершину, мы использовали на одно её ребро больше, чем уходя, а рёбер у неё чётное число, так что свободное ребро для выхода остаётся. Получился замкнутый маршрут (на рисунке — $A B C D A$).
Если маршрут прошёл не все рёбра, то на нём есть вершина с непройденными рёбрами: иначе рёбра маршрута не были бы связаны с остальными, а граф связный. Здесь это $B$. У каждой вершины маршрут занял чётное число рёбер, поэтому непройденных у неё тоже чётное число, и из $B$ можно тем же способом пройти ещё один замкнутый маршрут по непройденным рёбрам: $B E F B$.
Вклеим второй маршрут в первый: дойдя до $B$, пройдём сначала его, а потом продолжим первый маршрут. Получится один замкнутый маршрут $A B E F B C D A$. Повторяем, пока рёбра не кончатся; их конечное число, так что это произойдёт.
Если нечётных вершин ровно две, соединим их временным ребром. Теперь все степени чётные, и по доказанному есть замкнутый обход. Удалим из него временное ребро: цикл разрежется в путь, который начинается в одной нечётной вершине и заканчивается в другой.
Сегодня в Калининграде на месте семи мостов пять: два не пережили бомбардировок Второй мировой войны, ещё два снесли и заменили широкой магистралью. Степени изменились: у каждого берега теперь по два моста, у каждого острова по три. Нечётных вершин две, и прогулка возможна. Правда, начинать её придётся на одном острове, а заканчивать на другом. Проверьте это в виджете: выберите «Калининград сегодня».
По той же причине знаменитый «домик» — квадрат с двумя диагоналями и крышей — рисуется не отрывая карандаша, но только если начать в одном из нижних углов. Именно у них степень три.
В графе ровно четыре нечётные вершины, и он связный. За какое наименьшее число «росчерков» (маршрутов, каждый из которых проходит по своим рёбрам ровно раз) можно обойти все его рёбра?
Каждый росчерк «обслуживает» не больше двух нечётных вершин — своё начало и свой конец. Поэтому нужно хотя бы два. А двух хватает: соединим две нечётные вершины временным ребром, получим граф с двумя нечётными вершинами, пройдём его одним путём и разрежем путь на месте временного ребра. Кёнигсбергу понадобились бы две прогулки.
Обойти все перекрёстки
Теперь зададим похожий на вид вопрос о вершинах, а не о рёбрах. Можно ли обойти все перекрёстки города, побывав на каждом ровно один раз, и вернуться домой?
В середине 1850-х годов ирландский математик Уильям Роуэн Гамильтон придумал головоломку «Икосиан». На вершинах додекаэдра (многогранника из двенадцати пятиугольников) стояли названия двадцати городов мира, и нужно было совершить кругосветное путешествие по рёбрам, побывав в каждом городе по разу. В 1859 году Гамильтон продал права на игру лондонской фирме игрушек за двадцать пять фунтов.
Гамильтонов цикл — цикл, который проходит через каждую вершину графа ровно один раз. Если маршрут не обязан возвращаться в начало, говорят о гамильтоновом пути.
Для рёбер Эйлер дал простой признак: посчитай степени — и всё ясно. Для вершин такого признака никто не знает. У додекаэдра гамильтоновых циклов тридцать (если не различать, откуда и в какую сторону идти). А у графа, который в 1898 году описал датский математик Юлиус Петерсен, их нет ни одного, хотя все его вершины одинаковы, у каждой по три соседа, и граф выглядит не хуже додекаэдра. Проще всего убедиться в этом перебором: компьютер справляется с ним за мгновение, но для графа из тысячи вершин такой перебор растянулся бы на века.
Здесь проходит одна из самых глубоких границ в математике. Если вам покажут маршрут, проверить, что он гамильтонов, легко: пройти по нему и отметить вершины. А для поиска никто не знает способа, принципиально лучшего перебора: все известные алгоритмы в худшем случае тратят время, которое растёт экспоненциально с числом вершин. В 1972 году Ричард Карп включил задачу о гамильтоновом цикле в свой знаменитый список задач, которые одинаково трудны: если найти быстрый способ решать одну, быстро решатся и все. Верно ли, что «проверить легко» всегда означает «найти легко», — это вопрос P против NP, одна из задач тысячелетия. К ней мы вернёмся в последней главе курса.
Деревья
Посмотрим на графы без циклов. Родословная, папки на компьютере, река с притоками — в каждом случае из одной вершины в другую ведёт ровно одна дорога, и по кругу не пройти.
Дерево — связный граф без циклов. Вершину степени один называют листом.
В дереве с $V$ вершинами ровно $V - 1$ рёбер.
Сначала убедимся, что в дереве с хотя бы двумя вершинами есть лист. Пойдём из любой вершины по рёбрам, никогда не возвращаясь по только что пройденному ребру. В уже посещённую вершину мы прийти не можем: получился бы цикл, а в дереве циклов нет. Вершин конечное число, поэтому путь оборвётся — в вершине, из которой нет других рёбер, то есть в листе.
Оторвём этот лист вместе с его единственным ребром. Остаток по-прежнему связен (лист не лежал ни на каком пути между другими вершинами) и по-прежнему без циклов, то есть снова дерево. Вершин и рёбер в нём стало на одну меньше, поэтому разность «вершины минус рёбра» не изменилась: $7 - 6 = 6 - 5$.
Будем обрывать листья, пока не останется одна вершина. На каждом шаге разность «вершины минус рёбра» сохраняется, а в конце она равна $1 - 0 = 1$.
Значит, она была равна единице с самого начала: $V - E = 1$, то есть $E = V - 1$.
Граф без циклов состоит из трёх отдельных деревьев, и всего в нём $30$ вершин. Сколько в нём рёбер?
Если в деревьях $a$, $b$ и $c$ вершин, то рёбер в них $a - 1$, $b - 1$ и $c - 1$. Всего $(a + b + c) - 3 = 30 - 3 = 27$.
Сколько деревьев можно построить на $n$ пронумерованных вершинах
На $n$ пронумерованных вершинах можно построить ровно $n^{n-2}$ разных деревьев.
Ответ неожиданно прост. На трёх вершинах деревьев $3^1 = 3$ (какая вершина окажется посередине), на четырёх $4^2 = 16$, на десяти — сто миллионов. Эту формулу называют формулой Кэли: Артур Кэли опубликовал её в 1889 году, хотя равносильный результат есть у Карла Борхардта ещё в 1860-м. Идея самого красивого доказательства, которое предложил Хайнц Прюфер в 1918 году: закодировать каждое дерево словом из $n - 2$ номеров вершин. Обрываем лист с наименьшим номером и записываем номер его соседа, и так $n - 2$ раза. Слов из $n - 2$ номеров ровно $n^{n-2}$, а по слову дерево восстанавливается однозначно. Проверка этой однозначности занимает пару страниц аккуратных рассуждений, поэтому целиком мы её здесь не приводим; её можно найти в любом учебнике теории графов.
Кратчайший путь
Навигатор в телефоне решает задачу про граф: перекрёстки — вершины, улицы — рёбра, и у каждого ребра есть длина или время в пути.
Взвешенный граф — граф, у каждого ребра которого есть число, его вес: длина дороги, время в пути, цена прокладки кабеля. Длина маршрута — сумма весов его рёбер.
Как найти самый короткий маршрут, не перебирая все? В 1956 году голландский программист Эдсгер Дейкстра хотел показать публике возможности нового компьютера ARMAC и выбрал задачу, понятную без объяснений: кратчайший путь между городами Нидерландов. По его собственному рассказу, алгоритм он придумал примерно за двадцать минут, без карандаша и бумаги, когда сидел с невестой на террасе кафе в Амстердаме. Для демонстрации он взял упрощённую карту из $64$ городов: так номер города помещался в шесть двоичных разрядов. Статья вышла в 1959 году.
Идея алгоритма такая. Расходимся из начальной вершины волной. У каждой вершины есть пометка — лучшее известное время до неё: у начала это ноль, у остальных бесконечность. На каждом шаге берём непосещённую вершину с наименьшей пометкой и объявляем её пометку окончательной. Затем проверяем её соседей: если через неё к соседу выходит быстрее, чем записано, исправляем пометку соседа.
Если веса всех рёбер неотрицательны, то пометка вершины, которую алгоритм только что выбрал, равна длине кратчайшего пути до неё.
Пометки никогда не бывают меньше настоящих расстояний: каждая пометка — длина какого-то реального пути, найденного алгоритмом. Пусть алгоритм выбрал вершину $v$ с пометкой $d$, а все выбранные раньше вершины уже имеют верные пометки. Возьмём любой путь $P$ из начала в $v$. Он начинается в посещённой вершине, а кончается в $v$, которая пока не посещена; пусть $u$ — первая непосещённая вершина на $P$, а $w$ — посещённая вершина прямо перед ней. Когда алгоритм посещал $w$, её пометка уже была верной, то есть не больше длины участка $P$ от начала до $w$; тогда же он проверил ребро $w$–$u$ и сделал пометку $u$ не больше длины участка $P$ от начала до $u$. Веса неотрицательны, так что этот участок не длиннее всего $P$. А $v$ выбрана как непосещённая вершина с наименьшей пометкой, значит, $d$ не больше пометки $u$. Итого $d \le$ длины $P$ для любого пути $P$, то есть $d$ — длина кратчайшего пути.
Другой вопрос о той же карте: как соединить все перекрёстки сетью дорог (или кабелей, или труб), чтобы из любого места можно было попасть в любое другое, а стоила сеть как можно меньше? Лишние дороги такой сети не нужны: если в ней есть цикл, одно его ребро можно убрать, и связность сохранится. Поэтому самая дешёвая сеть — дерево.
Остовное дерево графа — дерево, составленное из его рёбер и проходящее через все его вершины. Остовное дерево наименьшего суммарного веса называют минимальным.
Первым эту задачу решил чешский математик Отакар Борувка в 1926 году: он помогал спроектировать электрическую сеть для Моравии. Самый простой способ описал в 1956 году американец Джозеф Краскал: берите рёбра по возрастанию веса и пропускайте те, что замкнули бы цикл. Жадность, которая обычно подводит, здесь не подводит, и вот почему.
Разделим вершины связного взвешенного графа на две группы. Самое дешёвое ребро между группами входит в какое-нибудь минимальное остовное дерево.
Пунктир делит вершины на две группы. Между группами идут три ребра; самое дешёвое из них, $e$, стоит $2$.
Возьмём остовное дерево $T$, в котором $e$ нет (на рисунке — дерево стоимостью $13$). Покажем, что его можно заменить деревом с ребром $e$, которое не дороже.
Добавим $e$ к дереву. Его концы уже были соединены путём по $T$, так что появился ровно один цикл. Цикл пересекает пунктир по ребру $e$ и должен вернуться на свою сторону, значит, пересекает его ещё раз — по какому-то ребру $f$ дерева $T$. Так как $e$ — самое дешёвое ребро через пунктир, $f$ не дешевле: здесь $4 \ge 2$.
Уберём $f$. Цикл разомкнулся, связность не нарушилась (вместо $f$ теперь работает остальная часть цикла), и рёбер снова $V - 1$: получилось остовное дерево. Его стоимость $13 - 4 + 2 = 11$ не больше прежней.
Возьмём теперь в роли $T$ минимальное дерево. Если $e$ в нём нет, замена даёт дерево не дороже — значит, тоже минимальное, — и в нём есть $e$. Отсюда правильность способа Краскала: каждое ребро, которое он берёт, соединяет какой-то уже построенный кусок сети с остальными вершинами и дешевле всех рёбер через эту границу — все более дешёвые уже рассмотрены. По лемме такое ребро можно взять, не проиграв в цене.
Потренируйтесь: вот задачи на степени, обходы и кратчайшие пути. Карты в них небольшие, так что Дейкстру можно выполнить в уме.
Три дома, три колодца
Старая головоломка: в деревне три дома и три колодца. Каждый хозяин хочет протоптать тропинку к каждому колодцу, но соседи в ссоре и не желают, чтобы их тропинки пересекались. Можно ли так проложить все девять тропинок? Другой вариант: пять городов, и каждые два нужно соединить дорогой без перекрёстков и мостов.
Планарный граф — граф, который можно нарисовать на плоскости так, чтобы рёбра пересекались только в вершинах. Граф из $n$ вершин, где каждые две соединены ребром, называют полным и обозначают $K_n$. Граф из двух групп вершин, где рёбра идут только между группами, называют двудольным; три дома и три колодца со всеми тропинками — это $K_{3,3}$.
Сколько ни тяни, у $K_{3,3}$ и $K_5$ остаётся хотя бы одно пересечение. Чтобы доказать, что это не наша неловкость, понадобится формула, которую Эйлер открыл в 1750 году, изучая многогранники. Нарисуем связный граф на плоскости без пересечений. Рёбра разрежут плоскость на куски.
Грань плоского рисунка графа — каждый из кусков, на которые рёбра разрезают плоскость. Внешний, бесконечный кусок тоже считается гранью.
Если связный граф нарисован на плоскости без пересечений рёбер, то $V - E + F = 2$, где $V$ — число вершин, $E$ — рёбер, $F$ — граней.
Выберем в графе остовное дерево. У него $V$ вершин и $V - 1$ рёбер, а грань одна — вся плоскость: без циклов от неё ничего не отрезать. Получается $V - (V - 1) + 1 = 2$. На рисунке это граф куба, расплющенный на плоскость: $8 - 7 + 1 = 2$.
Добавим одно из оставшихся рёбер. Его концы уже соединены путём по дереву, поэтому новое ребро вместе с этим путём замыкает цикл. Цикл — замкнутая линия без самопересечений, и она делит плоскость на внутреннюю и внешнюю части (это кажется очевидным, а строго доказывается непросто: теорема Жордана; для ломаных доказательство короткое). Грань, по которой прошло ребро, распалась на две: граней стало на одну больше. Рёбер тоже стало на одно больше, и $V - E + F$ не изменилось: $8 - 8 + 2 = 2$.
Так же с каждым следующим ребром: оно проходит внутри одной грани и соединяет две точки её границы, поэтому разрезает эту грань надвое. $E$ и $F$ растут одновременно, и сумма не меняется. Когда добавлены все рёбра, у куба $8 - 12 + 6 = 2$.
Мы начали с суммы $2$ и ни разу её не изменили. Значит, для любого связного графа, нарисованного на плоскости без пересечений, $V - E + F = 2$.
Из формулы Эйлера следует, что рёбер в плоском графе не может быть слишком много.
У простого (без кратных рёбер и петель) планарного графа с $V \ge 3$ вершинами не больше $3V - 6$ рёбер. Если в нём к тому же нет треугольников, рёбер не больше $2V - 4$.
Достаточно доказать это для связного графа: несвязный можно сделать связным, добавив рёбра, и число рёбер от этого только вырастет. Если рёбер меньше трёх, неравенства выполнены сами ($E \le 2 \le 3V - 6$ и $2 \le 2V - 4$ при $V \ge 3$). Пусть рёбер хотя бы три; нарисуем граф без пересечений.
Обойдём каждую грань по её границе и запишем, сколько рёбер встретили; сложим эти числа по всем граням. Каждое ребро учтено в сумме ровно дважды — по разу с каждой своей стороны (если с обеих сторон одна и та же грань, то дважды в её обходе). Значит, сумма равна $2E$. С другой стороны, граница каждой грани содержит хотя бы три ребра: грань с одним ребром — это петля, с двумя — два ребра между одними вершинами, а их в простом графе нет. Поэтому сумма не меньше $3F$, и $3F \le 2E$.
По формуле Эйлера $F = 2 - V + E$. Подставляем: $3(2 - V + E) \le 2E$, то есть $6 - 3V + 3E \le 2E$, откуда $E \le 3V - 6$. Если треугольников нет, граница каждой грани содержит хотя бы четыре ребра, и то же рассуждение даёт $4F \le 2E$, $4(2 - V + E) \le 2E$, откуда $E \le 2V - 4$.
Ни пять точек, соединённых каждая с каждой, ни три дома с тремя колодцами нельзя нарисовать на плоскости без пересечений.
У $K_5$ вершин $5$, а рёбер $\binom{5}{2} = 10$. Если бы он был планарным, по предыдущему следствию рёбер было бы не больше $3 \cdot 5 - 6 = 9$. Противоречие.
У $K_{3,3}$ вершин $6$, рёбер $3 \cdot 3 = 9$. Треугольников в нём нет: из трёх вершин треугольника две оказались бы в одной группе (домов или колодцев), а внутри группы рёбер нет. Значит, для планарного $K_{3,3}$ было бы $E \le 2 \cdot 6 - 4 = 8$. А рёбер девять — противоречие. Никакая ловкость в виджете не поможет: хотя бы одно пересечение останется всегда.
У выпуклого многогранника $12$ вершин и $30$ рёбер. Сколько у него граней?
По формуле Эйлера $F = 2 - V + E = 2 - 12 + 30 = 20$. Это икосаэдр: двадцать треугольных граней. Проверка из подсчёта рёбер: у двадцати треугольников $60$ сторон, и каждое ребро — сторона двух граней, так что рёбер $60 / 2 = 30$.
Оказывается, $K_5$ и $K_{3,3}$ — единственные настоящие препятствия.
Граф планарен тогда и только тогда, когда в нём нельзя найти $K_5$ или $K_{3,3}$, у которых некоторые рёбра, возможно, разбиты промежуточными вершинами на цепочки.
Половину теоремы мы уже доказали: если в графе сидит $K_5$ или $K_{3,3}$ (пусть даже с рёбрами, разбитыми на цепочки), то граф не планарен — рисунок графа без пересечений дал бы такой же рисунок и для них. Обратное утверждение, которое доказал польский математик Казимир Куратовский, гораздо тоньше: из графа без таких «запрещённых кусков» нужно построить рисунок без пересечений. Доказательство занимает несколько страниц разбора случаев и выходит за рамки главы; его можно найти в учебниках теории графов, например у Р. Дистеля.
А если деревня стоит не на плоскости? На поверхности бублика, торе, три дома соединяются с тремя колодцами без единого пересечения: часть тропинок уходит «вокруг дырки». Включите в виджете рисунок на торе. Формула Эйлера на торе тоже меняется: там $V - E + F = 0$. Число в правой части зависит только от поверхности, и о нём подробно расскажет глава о топологии.
Четыре краски
В 1852 году Фрэнсис Гатри раскрашивал карту графств Англии и заметил, что ему хватает четырёх красок, так чтобы соседние графства всегда были разного цвета. Он спросил брата Фредерика, студента Огастеса де Моргана, верно ли это для любой карты. 23 октября 1852 года де Морган написал об этом вопросе Гамильтону. Так появилась задача, которую решали больше ста двадцати лет.
Карту легко превратить в граф: в каждой стране поставим точку-столицу и соединим столицы соседних стран. Соседи — это страны с общим участком границы. Касание в одной точке не в счёт: в США четыре штата, Юта, Колорадо, Аризона и Нью-Мексико, сходятся углами в одной точке, но Юта с Нью-Мексико не соседи. Если бы в счёт шли и точки, торт, нарезанный на сорок кусков от центра, потребовал бы сорока красок. Граф карты всегда получается планарным: рёбра можно провести от столицы к столице через общие границы так, что они не пересекутся.
Хроматическое число графа — наименьшее число красок, которыми можно раскрасить его вершины так, чтобы концы каждого ребра были разного цвета.
Трёх красок хватает не всегда. Если страну окружает кольцо из пяти соседей, само кольцо требует трёх красок (при двух цветах они чередовались бы, а пять — нечётное число), и центральной стране нужна четвёртая. А вот пятая, как оказалось, не нужна никогда.
Вершины любого планарного графа можно раскрасить в четыре цвета так, чтобы концы каждого ребра были разного цвета. Иными словами, любую карту на плоскости можно раскрасить четырьмя красками.
Доказывать эту теорему здесь мы не будем: её доказательство — сотни страниц и компьютерный перебор. Идея такая: найти конечный список особых кусков карты, из которых хотя бы один обязательно встречается в любой карте, и для каждого куска показать, что его можно «сжать», раскрасить уменьшенную карту и вернуть кусок, не испортив раскраску. Тогда по индукции красок хватает для всех карт. Вся трудность — в том, чтобы найти список и проверить каждый кусок.
История доказательства похожа на детектив. В 1879 году английский юрист и математик Альфред Кемпе опубликовал доказательство, и одиннадцать лет его считали верным. В 1890 году Перси Хивуд нашёл в нём ошибку, но спас из рассуждения Кемпе то, что спасалось: пяти красок хватает всегда. Четыре краски доказали только в 1976 году Кеннет Аппель и Вольфганг Хакен. Они свели задачу к проверке почти двух тысяч особых кусков карт, и проверял их компьютер больше тысячи часов. Многие математики были недовольны: доказательство, которое человек не может прочитать целиком, казалось не вполне доказательством. В 1996 году Нил Робертсон, Дэниел Сандерс, Пол Сеймур и Робин Томас нашли более простой путь с 633 случаями, но тоже с компьютером. А в 2005 году Жорж Гонтье проверил всё доказательство в системе Coq, которая проверяет каждый логический шаг формально. Сомнений больше нет.
Раскраска нужна не только картографам. Составьте граф экзаменов: вершины — экзамены, ребро — если какой-то студент сдаёт оба. Цвета — дни сессии. Раскраска без конфликтов — расписание, в котором ни у кого не совпадают два экзамена в один день, а хроматическое число — наименьшее число дней. Судоку — тоже раскраска: $81$ клетка, девять цветов, и клетки одной строки, столбца или квадрата соединены рёбрами. Только графы расписаний обычно не планарны, и четырёх красок им может не хватить.
Мир тесен
Последняя остановка — самый большой граф из тех, что мы видели: граф знакомств всех людей на Земле. В 1967 году американский психолог Стэнли Милгрэм попросил жителей Небраски и Канзаса переслать письмо незнакомому человеку в Массачусетсе, но только через знакомых, которых они знают по имени. Дошла лишь часть писем, зато дошедшие в среднем прошли всего через пять-шесть рук. Отсюда пошло выражение «шесть рукопожатий».
В 2011 году исследователи из Facebook и Миланского университета посчитали расстояния в графе дружбы всех активных пользователей сети — около $721$ миллиона вершин и десятков миллиардов рёбер. Среднее расстояние между двумя людьми оказалось $4{,}74$ ребра. Математики давно пользуются собственной шкалой такого рода: числом Эрдёша, расстоянием до Пала Эрдёша в графе соавторства. У самого Эрдёша, написавшего около полутора тысяч статей с сотнями соавторов, оно равно нулю, у его соавторов — единице, у их соавторов — двум, и так далее. У большинства математиков, у которых это число вообще есть, оно не больше пяти.
Граф забывает всё, кроме связей: расстояния, форму, цвет. Поэтому одни и те же теоремы работают для мостов, дорог, карт, знакомств и расписаний. Чтобы решить задачу, часто достаточно разглядеть в ней граф.
Куда дальше
Представьте город, улицы которого образуют бесконечную клетчатую сетку. Из дома выходит прохожий и на каждом перекрёстке выбирает одно из четырёх направлений наугад, подбрасывая монету дважды. Вернётся ли он когда-нибудь домой? А если город трёхмерный, сложенный из одинаковых кубиков, и на каждом перекрёстке шесть направлений?
Граф здесь самый простой, а вопрос — о случае: какие маршруты вероятнее и что произойдёт «почти наверняка». Ответ, найденный Джорджем Пойа в 1921 году, удивляет: на прямой и на плоскости прохожий вернётся с вероятностью единица, а в пространстве с немалым шансом не вернётся никогда. Что такое вероятность, как её считать и где интуиция о шансах подводит — об этом следующая глава.