Задача о семи кёнигсбергских мостах
Зада́ча о кёнигсбе́ргских моста́х[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].
История публикации статьи Леонарда Эйлера
[править | править код]Леонард Эйлер, выдающийся швейцарский, прусский и русский математик и механик, академик Петербургской академии наук заинтересовался этой игрой. История публикации знаменитой статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения», написанной в связи с этим, имеет следующие известные по современным публикациям этапы:
- сначала 26 августа (6 сентября) 1735 года[16] Эйлер представил статью на Конференции Петербургской академии наук[2];
- затем в 1736 году Эйлер, в рамках своей научной переписки, отправил два следующих письма:
- 13 (24) марта 1736 года — письмо Иоганну Якобу Маринони[нем.], австрийскому астроному и математику, от 13 [24] марта 1736 года, Петербург. Это письмо целиком посвящено задаче о кёнигсбергских мостах[17][18];
- 3 (14) апреля 1736 года — письмо Карлу Леонарду Готлибу Элеру[нем.], немецкому политическому деятелю и астроному, от 3 [14] апреля 1736 года, Петербург. В конце этого письма идёт речь об основных идеях статьи[17][19];
- в 1741 году в Санкт-Петербурге наконец вышла статья Эйлера на латинском языке с датой 1736 года[17][20]:
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]:
- первая теорема Эйлера, 1736. Граф с двумя или более вершинами имеет эйлеров цикл тогда и только тогда, когда в каждую вершину входит чётное число рёбер;
- вторая теорема Эйлера, 1736. Граф с двумя или более вершинами не имеет эйлерова цикла, но имеет эйлерову цепь тогда и только тогда, когда ровно в две вершины входит нечётное число рёбер.
Из этих двух теорем можно вывести три следствия[23]:
- если граф с двумя вершинами, в которые входит нечётное число рёбер, имеет эйлерову цепь, то эти две вершины — начальная и конечная вершины цепи;
- граф с двумя или более вершинами имеет эйлерову цепь тогда и только тогда, когда либо в каждую вершину входит чётное число рёбер, либо ровно в две вершины входит нечётное число рёбер;
- задача о кёнигсбергских мостах не имеет решения, поскольку в графе этой задачи нечётную степень имеют четыре вершины.
Решение задачи по Леонарду Эйлеру
[править | править код]Формулировка задачи
[править | править код]Леонард Эйлер в своей знаменитой статье сформулировал задачу о семи кёнигсбергских мостах следующим образом[15]:
2. Эта задача, как мне сказали, довольно хорошо известна и связана вот с чем. В городе Кёнигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке. Рукава этой реки пересекают семь мостов а, b, с, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.
— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения
Решение задачи
[править | править код]Леонард Эйлер сформулировал свой метод следующим образом (см. рисунок выше)[24]:
4. Весь мой метод основан на надлежащих обозначениях для отдельных прохождений мостов. Я использую заглавные буквы А, В, С, D для обозначения отдельных областей, на которые река разделяет сушу. Таким образом, если некто движется из области А в область В через мост а или b, то я обозначаю прохождение моста символом АВ.
— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения
На современном языке это означает, что схеме мостов города соответствует граф, представляющий собой:
- четыре вершины по обозначениям четырёх частей центра города;
- вершины соединены семью рёбрами-мостами по обозначениям семи мостов.
Достаточно современное и простое решение Леонардом Эйлером задачи о кёнигсбергских мостах выглядит следующим образом (Эйлер современной терминологии не знал, термин «граф» не использовал, называл ребро «мостом», а вершину — «областью» или «буквой» и не рисовал современные изображения графов)[24].
- «Таким образом, становится очевидным, что если можно пройти по семи мостам, причём по каждому из них ровно по одному разу, то этот маршрут будет изображаться восемью буквами».
- «…я разработал правило, по которому можно легко решить — как для этой задачи, так и для всех подобных задач, — может ли быть осуществлено такое расположение букв.
- «8. Чтобы вывести подобное правило, я рассматриваю некоторую конкретную область , в которую может вести произвольное число мостов и т. д. Из этих мостов сначала я рассмотрю конкретный мост , ведущий в область . Если путешественник пройдёт по этому мосту, то он либо находился в области до того, как прошёл по этому мосту, либо окажется в области после этого. Поэтому чтобы обозначить этот проход по мосту, как описано выше, необходимо, чтобы один раз возникла буква .»
- «Если в область ведут три моста, например , и путешественник проходит по всем трём мостам, то буква будет встречаться в описании его движения по мостам дважды независимо от того, начинался его маршрут из или нет. Точно так же, если в область ведут пять мостов, то буква должна встретиться при описании его движения три раза. И когда количество мостов — произвольное нечётное число, то если увеличить его на единицу, половина полученного числа показывает, сколько раз должна встретиться буква .»
- «9. Следовательно, в случае с кёнигсбергскими мостами, поскольку на остров ведут пять мостов , необходимо, чтобы буква встретилась в описании движения по этим мостам трижды. Кроме того, дважды должна встретиться буква , так как в область ведут три моста, и буквы должны встретиться по два раза каждая. Поэтому в последовательности из восьми букв, с помощью которой описывается рассматриваемый маршрут, проходящий через семь мостов, буква должна встретиться три раза, а каждая из букв — по два раза. Такого, однако, в последовательности из восьми букв быть не может. Таким образом, ясно, что подобная прогулка по семи мостам Кёнигсберга невозможна».
Обобщение решения задачи
[править | править код]Решая задачу в общем виде, Леонард Эйлер попутно доказал, что для любого графа число вершин с нечётным количеством рёбер чётно[25]:
- «Вначале я отмечу, что все количества мостов», ведущих в области, «сложенные вместе, дают удвоенное число всех мостов. Причина состоит в том, что при таком подсчёте каждый мост считается дважды, с тем чтобы все мосты, ведущие в данную область, были учтены, ибо каждый мост ведёт в две области, которые он соединяет.
- 17. Из этого наблюдения вытекает, что сумма [чисел] всех мостов, ведущих в каждую область, есть чётное число, так как половина этой суммы есть в точности число мостов. Поэтому не может случиться так, чтобы среди чисел мостов, ведущих в любую область, в точности одно было нечётным; не может также случиться, чтобы нечётных чисел было три, пять и т. д. Следовательно, если «числа мостов», ведущих в области, «суть нечётные числа, их сумма чётна».
В конце статьи Леонард Эйлер записал общие выводы для любого графа вполне современным языком[25]:
20. Значит в каждом возможном случае следующее правило позволяет непосредственно и без труда выяснить, можно ли осуществить прогулку по всем мостам без повторений:
Если имеется более двух областей, в которые ведет нечётное число мостов, можно заявить с уверенностью, что такая прогулка невозможна.
Если, однако, имеются только две области, в которые ведёт нечётное число мостов, то прогулка осуществима при условии, что она начинается в одной из этих двух областей.
Если, наконец, нет ни одной области, в которую ведёт нечётное число мостов, прогулка с требуемыми условиями осуществима, причём начинаться она может в любой области.
Следовательно, с помощью этого правила поставленная задача может быть полностью решена.
— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения
См. также
[править | править код]Примечания
[править | править код]- ↑ 1 2 Харари Фрэнк. Теория графов, 2003, с. 13.
- ↑ 1 2 3 4 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 11.
- ↑ 1 2 3 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 1.
- ↑ Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 17.
- ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736, p. 129.
- ↑ Frank Harary Graph Theory, 2007, с. 1.
- ↑ Königsberg bridge problem // Britannica.
- ↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. vii.
- ↑ Dénes König. Theorie der endlichen und unendlichen Graphen, 1936, s. 24.
- ↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. ix.
- ↑ Эйлера задача, 1988.
- ↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 151.
- ↑ 1 2 3 4 5 6 7 8 9 10 11 Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg, 2007.
- ↑ Оре О. Графы и их применение, 1965, с. 6.
- ↑ 1 2 3 4 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 26.
- ↑ Протоколы заседаний Конференции Императорской Академии Наук с 1725 по 1803 года. Том I. 1725—1743, 1897, с. 220—221.
- ↑ 1 2 3 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 15.
- ↑ Письма к ученым, 1963, с. 152—158.
- ↑ Письма к ученым, 1963, с. 330—353.
- ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736.
- ↑ Оре О. Графы и их применение, 1965, с. 33.
- ↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 4.
- ↑ 1 2 3 4 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 8—12.
- ↑ 1 2 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 27—28.
- ↑ 1 2 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 31—32.
Литература
[править | править код]- Оре О. Графы и их применение / Пер. с англ. Л. И. Головиной. Под ред. И. М. Яглома. М.: Мир, 1965. 174 с.: ил.
- Протоколы заседаний Конференции Императорской Академии Наук с 1725 по 1803 года. Том I. 1725—1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Tome I. 1725—1743. С.-Петербург: Типография ИАН, 1897. 883 с.
- Харари Фрэнк. Теория графов / Пер. с англ. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд-е 2-е. М.: Едиториал УРСС, 2003. 296 с.: ил. ISBN 5-354-00301-6.
- Фляйшнер Г. Эйлеровы графы и смежные вопросы. М.: Мир, 2002. 335 с.: ил. ISBN 5-03-003115-4 (рус.). ISBN 0-444-88395-9 (англ.). [Fleischner H. Eulerian Graphs and Related Topics. P. 1, V. 1. Amsterdam: North-Holland, 1990.]
- Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов: Учебное пособие / Пер. с нем. Е. Е. Перегуда; Пол ред. С. В. Мациевского. Калининград: Изд-во РГУ им. И. Канта, 2008. 192 с.: ил. ISBN 978-5-88874-880-0.
- Леонард Эйлер. Письма к ученым / Под ред. академика В. И. Смирнова. — Москва—Ленинград: Издательство Академии наук СССР, 1963. Содержит оригинальный латинский текст писем и перевод на русский язык Ю. Х. Копелевич (письмо к Маринони) и Т. А. Лукиной (письмо к Элеру).
- Эйлера задача // Математический энциклопедический словарь / Гл. ред. Ю. В. Прохоров; Ред. Кол.: С. И. Адян, Н. С. Бахвалов, В. И. Битюцков, А. П. Ершов, Л. Д. Кудрявцев, А. Л. Онищик, А. П. Юшкевич. М.: «Советская энциклопедия», 1988. 847 с., ил. С. 641.
- Königsberg bridge problem // Britannica.
- Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Petropolitanae. 8 (1736) 1741, 128–140.
- Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg–A Historical Perspective // Networks. 2007. 49(3):199–203.
- Frank Harary Graph Theory. Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 283 p.
- Dénes König. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft M. B. H., 1936.
Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии. |
- Персоналии по алфавиту
- Учёные по алфавиту
- Математики по алфавиту
- Математики Швейцарии
- Математики Российской империи
- Математики XVIII века
- Математики Германии
- Механики по алфавиту
- Механики Швейцарии
- Механики Российской империи
- Механики XVIII века
- Механики Германии
- История математики
- Теория графов
- Занимательные задачи
- Кёнигсберг
- Математические задачи
- Открытия 1736 года