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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Семь мостов Кёнигсберга»)
Перейти к: навигация, поиск
Кёнигсберг в XVII—XVIII вв. (карта 1652 года)

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

История[править | править вики-текст]

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

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

Решение задачи по Леонарду Эйлеру[править | править вики-текст]

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

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

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

Konigsberg bridges.png7 bridges.svgKönigsberg graph.svg

Дальнейшая история[править | править вики-текст]

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

См. также[править | править вики-текст]

Литература[править | править вики-текст]