WikiSort.ru - Не сортированное

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

История

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

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

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

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

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

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

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

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

См. также

• Задача о ходе коня
• Теория графов
• Эйлеров цикл
• Топология
• Мосты Калининграда
• Задача коммивояжёра

Примечания

Литература

• Леонард Эйлер. Письма к ученым / Под ред. академика В. И. Смирнова. — Москва—Ленинград: Издательство Академии наук СССР, 1963. Содержит оригинальный латинский текст писем и перевод на русский язык Ю. Х. Копелевич (письмо к Маринони) и Т. А. Лукиной (письмо к Элеру).
• Leonh. Eulero. Solutio Problematis ad Geometriam Situs pertinentis (лат.) // Commentarii Academiae Scientiarum Imperialis Petropolitanae. Tomus VIII. Ad annum MDCCXXXVI. — Petropoli, 1741. — P. 128-140.
• Irina Gribkovskaia, Øyvind Halskau sr, Gilbert Laporte (2007). “The bridges of Königsberg—A historical perspective”. Networks. 49: 199–203. DOI:10.1002/net.20159.. Препринт находится в свободном доступе.