Задача о семи кёнигсбергских мостах
Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах (лат. Problema Regiomontanum de septem pontibus, нем. Königsberger Brückenproblem) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером, изобретшим таким образом эйлеровы циклы.
Содержание
История
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Маринони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя».
Решение задачи по Леонарду Эйлеру
На упрощённой схеме города (графе) мостам соответствуют линии (ребра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
- Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
- Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
- Если ровно две вершины графа нечётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой из нечётных вершин и завершить его в другой нечетной вершине.
- Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все) — следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
→
→
Дальнейшая история
В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. На 2016 год в Калининграде восемь мостов.
См. также
Напишите отзыв о статье "Задача о семи кёнигсбергских мостах"
Литература
- [math.dartmouth.edu/~euler/docs/originals/E053.pdf Оригинальная статья Эйлера] (лат.)
- [kursinfo.himolde.no/lo-kurs/lo904/Laporte/BridgesPaper.pdf THE BRIDGES OF KÖNIGSBERG — A HISTORICAL PERSPECTIVE by Irina Gribkovskaia, Øyvind Halskau sr and Gilbert Laporte]
Отрывок, характеризующий Задача о семи кёнигсбергских мостах
Вернувшись от князя Андрея в Горки, Пьер, приказав берейтору приготовить лошадей и рано утром разбудить его, тотчас же заснул за перегородкой, в уголке, который Борис уступил ему.Когда Пьер совсем очнулся на другое утро, в избе уже никого не было. Стекла дребезжали в маленьких окнах. Берейтор стоял, расталкивая его.
– Ваше сиятельство, ваше сиятельство, ваше сиятельство… – упорно, не глядя на Пьера и, видимо, потеряв надежду разбудить его, раскачивая его за плечо, приговаривал берейтор.
– Что? Началось? Пора? – заговорил Пьер, проснувшись.
– Изволите слышать пальбу, – сказал берейтор, отставной солдат, – уже все господа повышли, сами светлейшие давно проехали.
Пьер поспешно оделся и выбежал на крыльцо. На дворе было ясно, свежо, росисто и весело. Солнце, только что вырвавшись из за тучи, заслонявшей его, брызнуло до половины переломленными тучей лучами через крыши противоположной улицы, на покрытую росой пыль дороги, на стены домов, на окна забора и на лошадей Пьера, стоявших у избы. Гул пушек яснее слышался на дворе. По улице прорысил адъютант с казаком.
– Пора, граф, пора! – прокричал адъютант.
Приказав вести за собой лошадь, Пьер пошел по улице к кургану, с которого он вчера смотрел на поле сражения. На кургане этом была толпа военных, и слышался французский говор штабных, и виднелась седая голова Кутузова с его белой с красным околышем фуражкой и седым затылком, утонувшим в плечи. Кутузов смотрел в трубу вперед по большой дороге.
Войдя по ступенькам входа на курган, Пьер взглянул впереди себя и замер от восхищенья перед красотою зрелища. Это была та же панорама, которою он любовался вчера с этого кургана; но теперь вся эта местность была покрыта войсками и дымами выстрелов, и косые лучи яркого солнца, поднимавшегося сзади, левее Пьера, кидали на нее в чистом утреннем воздухе пронизывающий с золотым и розовым оттенком свет и темные, длинные тени. Дальние леса, заканчивающие панораму, точно высеченные из какого то драгоценного желто зеленого камня, виднелись своей изогнутой чертой вершин на горизонте, и между ними за Валуевым прорезывалась большая Смоленская дорога, вся покрытая войсками. Ближе блестели золотые поля и перелески. Везде – спереди, справа и слева – виднелись войска. Все это было оживленно, величественно и неожиданно; но то, что более всего поразило Пьера, – это был вид самого поля сражения, Бородина и лощины над Колочею по обеим сторонам ее.
Над Колочею, в Бородине и по обеим сторонам его, особенно влево, там, где в болотистых берегах Во йна впадает в Колочу, стоял тот туман, который тает, расплывается и просвечивает при выходе яркого солнца и волшебно окрашивает и очерчивает все виднеющееся сквозь него. К этому туману присоединялся дым выстрелов, и по этому туману и дыму везде блестели молнии утреннего света – то по воде, то по росе, то по штыкам войск, толпившихся по берегам и в Бородине. Сквозь туман этот виднелась белая церковь, кое где крыши изб Бородина, кое где сплошные массы солдат, кое где зеленые ящики, пушки. И все это двигалось или казалось движущимся, потому что туман и дым тянулись по всему этому пространству. Как в этой местности низов около Бородина, покрытых туманом, так и вне его, выше и особенно левее по всей линии, по лесам, по полям, в низах, на вершинах возвышений, зарождались беспрестанно сами собой, из ничего, пушечные, то одинокие, то гуртовые, то редкие, то частые клубы дымов, которые, распухая, разрастаясь, клубясь, сливаясь, виднелись по всему этому пространству.
