Loading AI tools
старинная математическая задача Из Википедии, свободной энциклопедии
Зада́ча о кёнигсбе́ргских моста́х[1][2][3] (лат. problema Regiomontanum de septem pontibus[4][5], англ. the Königsberg bridges problem[6][7][8], нем. das Problem der Königsberger Brücken, das Königsberger Brückenproblem[9][10]), или зада́ча Э́йлера[11] — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам центра старого Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в статье, датированной 1736 годом[2][12], математиком Леонардом Эйлером, который доказал, что это невозможно, и по ходу доказательства изобрёл эйлеровы циклы. Решение Эйлером задачи о кёнигсбергских мостах явилось первым в истории применением теории графов, но без использования термина «граф» и без рисования диаграмм графов.
В центре Кёнигсберга (ныне Калининград) на реке Прегель (ныне Преголя) находятся два острова: Кнайпхоф (ныне остров Иммануила Канта) и Ломзе (ныне Октябрьский остров). На берегах Прегеля к северу от острова Кнайпхоф расположен Альтштадт, к югу — Форштадт. Были построены мосты через Прегель, соединяющие эти четыре района[13]. На рисунке справа показан центр Кёнигсберга на карте 1652 года с обозначениями: А — Альтштадт, Б — Кнайпхоф, В — Ломзе и Г — Форштадт.
Семь первых мостов центра Кёнигсберга, соединяющие Альтштадт, Кнайпхоф, Ломзе и Форштадт, были построены в указанные ниже годы в следующем порядке[13]. Номера мостов в порядке их постройки показаны на рисунке справа.
1. Лавочный мост (1286)
Первый мост Кёнигсберга датируется 1286 годом. Соединил Альтштадт и Кнайпхоф. Принадлежал городу Альтштадт и обеспечивал городу легкий доступ к рынкам Кнайпхофа[13].
2. Зелёный мост (1322)
Второй мост Кёнигсберга построен в 1322 году. Соединил Кнайпхоф с Форштадтом и обеспечил лёгкий доступ к удалённым районам. Мост назывался «Зелёным» из-за зелёных волн, которые служат фоном герба Кнайпхофа[13].
3. Рабочий мост (1377)
В XIV веке на востоке Форштадта была скотобойня. Чтобы облегчить транспортировку мяса, в 1377 году между Кнайпхофом и Форштадтом был построен третий мост[13].
4. Кузнечный мост (1397)
в 1397 году в северо-восточной части Кнайпхофа был построен четвёртый Кузнечный мост, который начинался недалеко от кузнечных мастерских в Альтштадте[13].
Если по этим четырём мостам нарисовать граф, то он будет эйлеровым, то есть все четыре моста можно обойти по одному разу по замкнутому маршруту, начиная с любого места. Жители могли совершать такие прогулки[13].
5. Деревянный мост (1404)
На острове Ломзе заготавливали древесину, и пятый мост между Альтштадтом и Ломзе, построенный между 1400 и 1404 годами, облегчил доставку древесины[13].
6. Высокий мост (1506)
Шестой мост был построен в 1506 году, чтобы соединить Ломзе и Форштадт[13].
7. Медовый мост (1542)
Седьмой из мостов Эйлера, соединивший оба острова, был завершен в 1542 году. Он был построен жителями Кнайпхофа для прохождения на северный берег, минуя два моста из Кнайпхофа, контролируемые Альтштадтом. Согласно легенде, Кнайпхоф передал бочку мёда Альтштадту, чтобы получить разрешение на строительство моста[13].
Итак, в 1542 году все семь мостов Кёнигсберга, рассмотренных Эйлером, были на месте. Теперь жители не могли обойти все мосты за один раз[13].
Возникновение раздела математики теория графов связано с математическими головоломками, и некоторое достаточно продолжительное время теория графов была «несерьёзна» и целиком связана с играми и развлечениями. Такая судьба теории графов повторяет судьбу теории вероятностей, также сначала находившей себе применение только в азартных играх[14].
Жители Кёнигсберга играли в своего рода игру, как пройти по всем городским мостам так, чтобы маршрут не пролегал ни по одному из них дважды[3]. «Как я слышал, — писал Леонард Эйлер, — некоторые отрицают, что это можно сделать, другие сомневаются, но никто не подтверждает такой возможности»[15].
Леонард Эйлер, выдающийся швейцарский, прусский и русский математик и механик, академик Петербургской академии наук заинтересовался этой игрой. История публикации знаменитой статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения», написанной в связи с этим, имеет следующие известные по современным публикациям этапы:
Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. P. 128—140.
В переводе[15]:
Леонард Эйлер. Решение одной задачи, связанной с геометрией положения / Труды Петербургской академии наук. 8 (1736). 1741. С. 128—140.
Поскольку выход статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения» из печати датируется 1736 годом, а также этим годом датируются оба упомянутых выше письма, этот год мировым математическим сообществом назначен датой рождения раздела математики теория графов[2].
Задача о кёнигсбергских мостах разными авторами формулируется по-разному.
1. Маршрут произвольный
В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.
— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения[15]
Для жителей Кёнигсберга существовала своего рода игра, найти такой маршрут прогулки по городу, который бы проходил через каждый из показанных на рисунке мостов ровно один раз.
— Фрич Р. и др. Избранные главы теории графов[3]
2. Маршрут должен быть замкнутым
Задача состояла в следующем, найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.
— Фрэнк Харари. Теория графов[1]
3. Замкнутые маршруты должны начинаться в каждой части города
Фактически требуется найти четыре маршрута обхода кёнигсбергских мостов, начинающиеся в четырёх частях города.
Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?
— Оре О. Графы и их применение[21]
Современное решение задачи о кёнигсбергских мостах начинается с построения графа задачи (см. рисунок справа)[22]:
Задачу о кёнигсбергских мостах можно переформулировать в терминах теории графов следующим образом[23]:
Начнём с определений, перейдём к теоремам и закончим следствиями[23]:
Следующие две теоремы впервые появились в статье Леонарда Эйлера о кёнигсбергских мостах[23]:
Из этих двух теорем можно вывести три следствия[23]:
Леонард Эйлер в своей знаменитой статье сформулировал задачу о семи кёнигсбергских мостах следующим образом[15]:
2. Эта задача, как мне сказали, довольно хорошо известна и связана вот с чем. В городе Кёнигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке. Рукава этой реки пересекают семь мостов а, b, с, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.
— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения
Леонард Эйлер сформулировал свой метод следующим образом (см. рисунок выше)[24]:
4. Весь мой метод основан на надлежащих обозначениях для отдельных прохождений мостов. Я использую заглавные буквы А, В, С, D для обозначения отдельных областей, на которые река разделяет сушу. Таким образом, если некто движется из области А в область В через мост а или b, то я обозначаю прохождение моста символом АВ.
— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения
На современном языке это означает, что схеме мостов города соответствует граф, представляющий собой:
Достаточно современное и простое решение Леонардом Эйлером задачи о кёнигсбергских мостах выглядит следующим образом (Эйлер современной терминологии не знал, термин «граф» не использовал, называл ребро «мостом», а вершину — «областью» или «буквой» и не рисовал современные изображения графов)[24].
Решая задачу в общем виде, Леонард Эйлер попутно доказал, что для любого графа число вершин с нечётным количеством рёбер чётно[25]:
В конце статьи Леонард Эйлер записал общие выводы для любого графа вполне современным языком[25]:
20. Значит в каждом возможном случае следующее правило позволяет непосредственно и без труда выяснить, можно ли осуществить прогулку по всем мостам без повторений:
Если имеется более двух областей, в которые ведет нечётное число мостов, можно заявить с уверенностью, что такая прогулка невозможна.
Если, однако, имеются только две области, в которые ведёт нечётное число мостов, то прогулка осуществима при условии, что она начинается в одной из этих двух областей.
Если, наконец, нет ни одной области, в которую ведёт нечётное число мостов, прогулка с требуемыми условиями осуществима, причём начинаться она может в любой области.
Следовательно, с помощью этого правила поставленная задача может быть полностью решена.
— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.