Задача о семи кёнигсбергских мостах

Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах (лат. Problema Regiomontanum de septem pontibus, нем. Königsberger Brückenproblem) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером, доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.

История

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Джованни Джакобо Маринони от 13 марта 1736 года. В этом письме Эйлер приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя». В письме Карлу Готлибу Элеру от 3 апреля 1736 года Эйлер обосновывает найденное им правило, а позднее на эту тему Эйлер публикует статью в научном журнале Петербургской академии наук «Commentarii Academiae Scientiarum Imperialis Petropolitanae».

Решение задачи по Леонарду Эйлеру

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

• Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
• Если все вершины графа чётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
• Если ровно две вершины графа нечётные, то можно начертить этот граф без отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных вершин и завершить его в другой нечётной вершине.
• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все) — следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

→ →

Дальнейшая история

В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. Всего до 2016 года в Кёнисберге было восемь мостов.