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

Задача

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

ЭйлерЛеонард Эйлершвейцарский математик, работавший в Петербурге и Берлине · 1707–1783Самый плодовитый математик в истории: около 900 работ, половина языка современной математики — от знака $\pi$ до записи $f(x)$ — и способность считать, не глядя., служивший тогда в Петербургской академии, получил задачу от данцигского корреспондента Карла Элера и поначалу отнёсся к ней пренебрежительно: в письме 1736 года он замечает, что вопрос «весьма банален» и к математике, кажется, отношения не имеет, поскольку «для решения нужен только рассудок и никакой математики». Разобравшись, он передумал — и написал работу «Solutio problematis ad geometriam situs pertinentis», доложенную академии в 1736 году.

Уже в названии — ссылка на «геометрию положения», geometria situs: так ЛейбницГотфрид Вильгельм Лейбницнемецкий философ, математик и дипломат · 1646–1716Придумал знаки $d$ и $\int$, которыми мы пишем анализ до сих пор, — и всю жизнь искал язык, на котором спор можно было бы заканчивать словами «посчитаем». в письме ГюйгенсуХристиан Гюйгенснидерландский математик, физик и астроном · 1629–1695Написал первый печатный учебник теории вероятностей, изобрёл маятниковые часы, открыл кольца Сатурна и объяснил свет волнами. 1679 года назвал будущую науку о свойствах фигур, не сводящихся к величине. Лейбниц идею только назвал; здесь она впервые работает.

Решение

Ход Эйлера состоит в том, чтобы выбросить всё лишнее. Длины мостов, площади районов, расположение улиц — ничто из этого на ответ не влияет. Значение имеет только то, что с чем соединено.

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

Теперь рассуждение, которое стоит проговорить целиком, потому что оно элементарно и безупречно.

Пусть маршрут существует. Возьмём вершину, которая не является ни началом, ни концом пути. Всякий раз, когда путешественник в неё входит, он потом должен из неё выйти — иначе маршрут там оборвётся. Значит, рёбра при такой вершине разбиваются на пары «вход — выход», и их число чётно.

Нечётное число рёбер допустимо только у начала маршрута (первый выход не имеет пары) и у конца (последний вход не имеет пары). Итого:

Теорема Эйлера. Обход, проходящий по каждому ребру ровно один раз, существует тогда и только тогда, когда граф связен и число вершин нечётной степени равно нулю или двум.

В Кёнигсберге степени вершин равны $3$, $3$, $3$ и $5$ — все четыре нечётны. Маршрута не существует.

Обратите внимание на устройство доказательства: оно ничего не перебирает. Наивный подход — рассмотреть все $7!=5040$ порядков обхода — дал бы ответ, но не объяснение и не работал бы для города покрупнее. Эйлерово рассуждение объясняет и годится для любого графа.

Строго говоря, Эйлер доказал только необходимость условия; достаточность (что при выполнении условия маршрут действительно существует) он считал очевидной, а полное доказательство напечатал Хирхольцер в 1873 году. Такие обходы теперь называют эйлеровыми.

Почему это точка топологии

Формально перед нами первая работа по теории графов, и дискретная линия с полным правом считает её своей.

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

Эйлер сам понимал, что делает что-то новое, и потому сослался на Лейбница. Но продолжения не последовало: следующие сто лет «геометрия положения» существовала как набор занятных задач без общей теории.

Что стало с мостами

Судьба конфигурации поучительна. Два моста разрушены бомбардировкой 1944 года, ещё два снесены при перестройке города; сегодня в Калининграде из семи исторических мостов сохранились три плюс два новых. При нынешней схеме нечётных вершин ровно две — эйлеров путь существует, только начинать и заканчивать придётся в определённых точках.

Задача Эйлера имеет и близкого родственника, устроенного совершенно иначе: обойти все вершины по одному разу — это икосианская игра Гамильтона (1856). Внешне похоже, а по существу нет: для эйлеровых путей есть простой критерий, а задача о гамильтоновом цикле NP-полна (точка о Карпе) — быстрого способа её решать не знает никто. Два соседних вопроса, разница между которыми стала ясна только через двести с лишним лет.

Задача. Нарисуйте «открытый конверт» — прямоугольник с обеими диагоналями и «крышей». Можно ли обвести его, не отрывая карандаша и не проводя ни одной линии дважды?
(Ответ: посчитайте степени вершин. У классического конверта с крышей нечётных вершин ровно две — нижние углы прямоугольника; значит, обвести можно, начав в одном из них и закончив в другом. А если добавить к фигуре ещё и диагонали крыши, нечётных вершин станет четыре, и обойти станет невозможно.)