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

Задача о семи мостах Кёнигсберга — это математическая задача, впервые сформулированная и решённая швейцарским математиком Леонардом Эйлером в 1736 году. Она заключается в поиске маршрута, который проходит ровно один раз по каждому из семи мостов города Кёнигсберга (ныне Калининград) и возвращается в исходную точку. Решение этой задачи положило начало теории графов и топологии.

История

Предыстория

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

Формулировка Эйлера

В 1736 году Леонард Эйлер, работавший в то время в Санкт-Петербургской академии наук, заинтересовался этой задачей. Он опубликовал статью «Solutio problematis ad geometriam situs pertinentis» (Решение задачи, относящейся к геометрии положения), в которой доказал, что такой маршрут невозможен. Эйлер абстрагировался от конкретной географии города, представив мосты как рёбра, а участки суши (берега и острова) — как вершины графа.

Математическая модель

Граф Кёнигсберга

Эйлер свел задачу к анализу графа, состоящего из четырёх вершин (A, B, C, D) и семи рёбер (мостов). Вершины обозначали:

• A — левый берег реки (район Альтштадт),
• B — правый берег (район Лёбенихт),
• C — остров Кнайпхоф,
• D — остров Ломзе.

Мосты соединяли эти вершины следующим образом:

• Мост 1: A — C (Лавочный мост)
• Мост 2: A — C (Зелёный мост)
• Мост 3: A — D (Кузнечный мост)
• Мост 4: B — C (Дровяной мост)
• Мост 5: B — C (Высокий мост)
• Мост 6: C — D (Медовый мост)
• Мост 7: D — B (Мост через ручей)

Степени вершин

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

• A: 3 (нечётная)
• B: 3 (нечётная)
• C: 5 (нечётная)
• D: 3 (нечётная)

Все четыре вершины имели нечётные степени, что делало прохождение всех мостов ровно один раз с возвратом в исходную точку невозможным.

Решение задачи

Теорема Эйлера

Эйлер сформулировал общее условие существования эйлерова цикла (замкнутого маршрута, проходящего по каждому ребру ровно один раз):

• Граф должен быть связным (все вершины соединены).
• Все вершины должны иметь чётную степень.

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

Практический вывод

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

Значение и влияние

Основание теории графов

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

Вклад в топологию

Эйлер также заложил основы топологии — раздела математики, изучающего свойства фигур, сохраняющиеся при непрерывных деформациях. В своей статье он упомянул «геометрию положения» (geometriam situs), которая позже стала называться топологией. Задача о мостах является классическим примером топологической задачи, где важны не расстояния и формы, а только связи между объектами.

Современные приложения

Теория графов, возникшая из этой задачи, используется в:

• Маршрутизации (задача коммивояжёра, поиск кратчайших путей),
• Проектировании сетей (компьютерные, транспортные, электрические),
• Анализе социальных сетей (поиск сообществ, влияние),
• Биоинформатике (анализ геномов, метаболических путей),
• Логистике (оптимизация доставки, сбор мусора).

Интересные факты

• В 1905 году, после реконструкции города, количество мостов изменилось. В 1945 году, в ходе Второй мировой войны, многие мосты были разрушены. В современном Калининграде сохранились лишь некоторые из исторических мостов, а их конфигурация отличается от исходной.
• Задача о семи мостах Кёнигсберга часто используется в учебных курсах по математике и информатике для демонстрации базовых понятий теории графов.
• В честь этой задачи назван эйлеров цикл — замкнутый маршрут, проходящий по каждому ребру графа ровно один раз.
• В 2005 году в Калининграде был установлен памятник Леонарду Эйлеру, держащему в руках лист с решением задачи о мостах.

Источники

• Эйлер Л. «Solutio problematis ad geometriam situs pertinentis» (1736)
• Харари Ф. «Теория графов» (1969)
• Большая советская энциклопедия, статья «Графов теория»
• Калининградский историко-художественный музей, материалы по истории города