Семь мостов Кёнигсберга

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

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

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

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

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

Переведём это на язык точек и линий. Число мостов, сходящихся к участку, — это его степень $\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) $$

модель

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

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

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

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

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

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

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

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

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

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

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

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

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

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