Почему семь мостов нельзя обойти по разу?

Попробуйте нарисовать конверт — квадрат с крышей и диагоналями — одним росчерком, не отрывая ручку и не обводя линию дважды. Где-то получается, где-то нет, и заранее не угадаете. Ровно такую задачу горожане Кёнигсберга решали не на бумаге, а ногами.

Прямо здесь, на острове Кнайпхоф у Кафедрального собора, сходились мосты через Прегель: семь штук связывали остров, второй островок и два берега. Весь XVIII век жители искали прогулку, которая прошла бы по каждому мосту ровно раз — и не находили.

1. у всех четырёх точек нечётное число мостов
2. северный берег
3. северный берег
4. Кнайпхоф
5. второй островок
6. островок
7. Кнайпхоф
8. южный берег
9. семь мостов, четыре участка суши
10. южный берег
11. то же самое: точки и линии; в кружке — число мостов

Разобрался швейцарский и российский математик Леонард Эйлер. Его главный ход — не пройти мосты, а отбросить лишнее: длины мостов, форма островов, изгибы реки на ответ не влияют. Важно одно — связность: какой участок суши с каким соединён и сколькими мостами. Сведите карту к четырём точкам и семи линиям между ними — и задача про прогулку превращается в задачу про чертёж одним росчерком.

И ответ оказался коротким: такого маршрута нет. Не потому, что плохо искали, — а потому, что его не может быть в принципе.

Посмотрите на любой «транзитный» участок — тот, где вы не начинаете и не заканчиваете прогулку. Раз вы туда вошли по одному мосту, то обязаны и выйти — по другому. Мосты на таком участке разбиваются на пары «вошёл — вышел», а значит, их число должно быть чётным. Нечётное число мостов могут позволить себе только два места: где маршрут стартует и где финиширует.

Переведём это на язык точек и линий. Число мостов, сходящихся к участку, — это его степень $\deg(v)$. Сумма степеней считает каждый мост дважды (у него два конца), поэтому для любого графа верно правило рукопожатий:

$$ \sum_v \deg(v) = 2\,|E| $$

модель

где $|E|$ — число рёбер (мостов). Сумма степеней всегда чётна — а значит, вершин с нечётной степенью не может быть нечётное количество: их всегда 0, 2, 4, …

Теперь подставим Кёнигсберг. У острова Кнайпхоф сходятся пять мостов, у остальных трёх участков — по три:

$$ 5 + 3 + 3 + 3 = 14 = 2 \cdot 7 $$

модель

Семь мостов — сходится. Но все четыре участка имеют нечётную степень, а маршрут «без повторов» терпит самое большее две нечётные вершины — старт и финиш. Четыре больше двух, и спорить тут не с чем: прогулки не существует¹.

Где работает тот же закон?

Правило «нечётных вершин — 0 или 2» переживает любой сюжет, где надо обойти связи, не повторяясь. Снегоуборщик или мусоровоз, что должны проехать по каждой улице ровно раз; плоттер, рисующий чертёж одним движением пера; разводка дорожек на плате. А в биологии тот же приём собирает геном: длинную цепочку ДНК режут на короткие куски, строят из них граф де Брёйна и ищут путь, проходящий по каждому звену, — и из мозаики обрывков восстанавливают исходную последовательность².

Если маршрут не выходит — спросим иначе: что нужно изменить, чтобы вышел? Помеха — четыре нечётные вершины, а позволено две. Каждый новый мост поднимает степень своих двух концов на единицу, превращая нечётное в чётное. Перекинем мост между двумя нечётными участками — и оба становятся чётными:

$$ (5,\,3,\,3,\,3) \;\longrightarrow\; (6,\,4,\,3,\,3) $$

модель

Остаются ровно две нечётные вершины — они и станут стартом и финишем. Восьмой мост открывает прогулку, которой не было при семи¹.

1. четыре участка с нечётным числом мостов
2. восьмой мост (жёлтый): нечётных осталось два
3. (5, 3, 3, 3)
4. (6, 4, 3, 3)
5. семь мостов — маршрута нет
6. восьмой мост — маршрут появляется

Почему эта задачка стала наукой?

Эйлер заметил, что в ответе нет ни одного расстояния — только связи. Так родилась идея геометрии, которой безразличны длины и углы: важно лишь, что соединено и как. Из неё выросли теория графов и топология — «геометрия положения». Сегодня на этом языке описывают транспортные и компьютерные сети, молекулы, социальные связи и маршруты доставки: всюду, где суть не в том, где объекты лежат, а в том, кто с кем связан.

Как это проверяют?

Чтобы узнать, обходится ли сеть без повторов, не нужно перебирать миллионы маршрутов — достаточно сосчитать нечётные вершины. Ноль — обход есть и кончится там же, где начался; два — есть, но старт и финиш в разных местах; больше двух — обхода нет. Один взгляд на степени вместо полного перебора: в этом и сила абстракции Эйлера.

Границы теоремы Эйлера Утверждение звучит просто: обход, проходящий по каждому ребру ровно один раз, существует тогда и только тогда, когда вершин нечётной степени либо ноль, либо две. Но за этой простотой прячутся оговорки.

• Граф должен быть связным. Если мосты делят город на две части, между которыми нет ни одного перехода, никакая чётность не спасёт: обойти всё за один маршрут нельзя. Проверять связность приходится отдельно, и в задачах на реальных сетях это как раз самая частая причина отказа.
• Ноль нечётных вершин и две — разные случаи. При нуле маршрут замкнут: возвращаетесь туда, откуда вышли (эйлеров цикл). При двух — начинать обязаны в одной нечётной вершине, а закончите в другой (эйлеров путь); выбора старта нет. При четырёх и более — маршрута нет вовсе.
• Теорема ничего не говорит о длине. Она отвечает на вопрос «возможно ли», а не «как короче». Если пройти по мосту дважды всё-таки разрешено, но хочется минимизировать повторы, это уже задача китайского почтальона, и решается она другими средствами.
• Соседняя задача выглядит похоже и решается иначе. Обойти все вершины по разу — гамильтонов цикл — критерия наподобие эйлерова не имеет, и задача относится к NP-полным. Разница в одном слове, «рёбра» против «вершин», а вычислительная сложность несопоставима.

Сколько это в числах В исходной задаче четыре участка суши и семь мостов; степени вершин — 3, 3, 3 и 5, все четыре нечётные, поэтому маршрута нет. Добавление одного моста между двумя нечётными вершинами поднимает обе степени на единицу и делает их чётными: нечётных остаётся две — и маршрут появляется.

Полезно заметить и общее правило: сумма степеней всех вершин равна удвоенному числу рёбер, $\sum \deg v = 2E$, — словами: каждое ребро добавляет по единице к двум концам. Отсюда следует, что вершин нечётной степени всегда чётное число; трёх нечётных вершин не бывает ни в одном графе.

Что из этого выросло Эйлер решал не головоломку, а сформулировал новый способ смотреть на задачу: важны только связи, а не расстояния и форма. С этой работы 1736 года принято отсчитывать теорию графов, на которой сегодня стоят маршрутизация транспорта, разводка микросхем, анализ социальных сетей и сборка генома из коротких прочтений — там ищут как раз эйлеров путь в графе перекрытий.

Открытый вопрос

Семь мостов давно стали четырьмя точками в учебнике — но город живёт дальше: мосты разрушались в войну, отстраивались, появлялись новые. Если пересчитать степени по нынешней карте Калининграда — найдётся ли сегодня прогулка, которой не было у горожан XVIII века?

Лекция по теме Александр Гасников, «Формула Эйлера для графов» — соотношение вершин, рёбер и граней — продолжение той же работы Эйлера.

Александр Гасников, «Реконструкция генома и задачи на графах» — эйлеров путь в современной биологии: как из коротких прочтений собирают геном.