Попробуй нарисовать конверт — квадрат с крышей и диагоналями — одним росчерком, не отрывая ручку и не обводя линию дважды. Где-то получается, где-то нет, и заранее не угадаешь. Ровно такую задачу горожане Кёнигсберга решали не на бумаге, а ногами.
Прямо здесь, на острове Кнайпхоф у Кафедрального собора, сходились мосты через Прегель: семь штук связывали остров, второй островок и два берега. Весь XVIII век жители искали прогулку, которая прошла бы по каждому мосту ровно раз — и не находили.
Четыре участка суши (остров Кнайпхоф, второй островок и два берега) и семь мостов между ними. Для задачи важны не длины и изгибы, а только что с чем соединено.
Разобрался швейцарский и российский математик Леонард Эйлер. Его главный ход — не пройти мосты, а отбросить лишнее: длины мостов, форма островов, изгибы реки на ответ не влияют. Важно одно — связность: какой участок суши с каким соединён и сколькими мостами. Сведи карту к четырём точкам и семи линиям между ними — и задача про прогулку превращается в задачу про чертёж одним росчерком.
И ответ оказался коротким: такого маршрута нет. Не потому, что плохо искали, — а потому, что его не может быть в принципе.
Посмотри на любой «транзитный» участок — тот, где ты не начинаешь и не заканчиваешь прогулку. Раз ты туда вошёл по одному мосту, то обязан и выйти — по другому. Мосты на таком участке разбиваются на пары «вошёл — вышел», а значит, их число должно быть чётным. Нечётное число мостов могут позволить себе только два места: где маршрут стартует и где финиширует.
Переведём это на язык точек и линий. Число мостов, сходящихся к участку, — это его степень $\deg(v)$. Сумма степеней считает каждый мост дважды (у него два конца), поэтому для любого графа верно правило рукопожатий:
$$ \sum_v \deg(v) = 2\,|E| $$
где $|E|$ — число рёбер (мостов). Сумма степеней всегда чётна — а значит, вершин с нечётной степенью не может быть нечётное количество: их всегда 0, 2, 4, …
Теперь подставим Кёнигсберг. У острова Кнайпхоф сходятся пять мостов, у остальных трёх участков — по три:
$$ 5 + 3 + 3 + 3 = 14 = 2 \cdot 7 $$
Семь мостов — сходится. Но все четыре участка имеют нечётную степень, а маршрут «без повторов» терпит самое большее две нечётные вершины — старт и финиш. Четыре больше двух, и спорить тут не с чем: прогулки не существует1.
Где работает тот же закон?
Правило «нечётных вершин — 0 или 2» переживает любой сюжет, где надо обойти связи, не повторяясь. Снегоуборщик или мусоровоз, что должны проехать по каждой улице ровно раз; плоттер, рисующий чертёж одним движением пера; разводка дорожек на плате. А в биологии тот же приём собирает геном: длинную цепочку ДНК режут на короткие куски, строят из них граф де Брёйна и ищут путь, проходящий по каждому звену, — и из мозаики обрывков восстанавливают исходную последовательность2.
Эйлер изложил решение в работе «Solutio problematis ad geometriam situs pertinentis» (1736), представленной Петербургской академии наук; её принято считать первой статьёй по теории графов (Euler, 1736; обзор — Wikipedia, «Seven Bridges of Königsberg»). ↩
Если маршрут не выходит — спросим иначе: что нужно изменить, чтобы вышел? Помеха — четыре нечётные вершины, а позволено две. Каждый новый мост поднимает степень своих двух концов на единицу, превращая нечётное в чётное. Перекинем мост между двумя нечётными участками — и оба становятся чётными:
Остаются ровно две нечётные вершины — они и станут стартом и финишем. Восьмой мост открывает прогулку, которой не было при семи1.
Восьмой мост между двумя нечётными участками поднимает их степени на единицу: четыре нечётные вершины превращаются в две — и маршрут без повторов появляется.
Почему эта задачка стала наукой?
Эйлер заметил, что в ответе нет ни одного расстояния — только связи. Так родилась идея геометрии, которой безразличны длины и углы: важно лишь, что соединено и как. Из неё выросли теория графов и топология — «геометрия положения». Сегодня на этом языке описывают транспортные и компьютерные сети, молекулы, социальные связи и маршруты доставки: всюду, где суть не в том, где объекты лежат, а в том, кто с кем связан.
Как это проверяют?
Чтобы узнать, обходится ли сеть без повторов, не нужно перебирать миллионы маршрутов — достаточно сосчитать нечётные вершины. Ноль — обход есть и кончится там же, где начался; два — есть, но старт и финиш в разных местах; больше двух — обхода нет. Один взгляд на степени вместо полного перебора: в этом и сила абстракции Эйлера.
Открытый вопрос
Семь мостов давно стали четырьмя точками в учебнике — но город живёт дальше: мосты разрушались в войну, отстраивались, появлялись новые. Если пересчитать степени по нынешней карте Калининграда — найдётся ли сегодня прогулка, которой не было у горожан XVIII века?
Из семи исторических мостов часть была разрушена во время Второй мировой войны; современная конфигурация переправ через Преголю отличается от той, что видел Эйлер (Wikipedia, «Seven Bridges of Königsberg»). ↩
