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

Запрос «Семь мостов Кёнигсберга» перенаправляется сюда; о самих городских мостах см. Мосты Калининграда.

Зада́ча о кёнигсбе́ргских моста́х (лат. problema Regiomontanum de septem pontibus, англ. the Königsberg bridges problem, нем. das Problem der Königsberger Brücken, das Königsberger Brückenproblem) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам центра старого Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в статье, датированной 1736 годом, математиком Леонардом Эйлером, который доказал, что это невозможно, и по ходу доказательства изобрёл эйлеровы циклы. Решение Эйлером задачи о кёнигсбергских мостах явилось первым в истории применением теории графов, но без использования термина «граф» и без рисования диаграмм графов.

Кёнигсберг в XVII—XVIII вв. Карта 1652 года с подкраской реки и мостов

ИсторияПравить

 

Центр Кёнигсберга 1652 года: А — Альтштадт, Б — Кнайпхоф, В — Ломзе и Г — Форштадт

В центре Кёнигсберга (ныне Калининград) на реке Прегель (ныне Преголя) находятся два острова: Кнайпхоф (ныне остров Иммануила Канта) и Ломзе (ныне Октябрьский остров). На берегах Прегеля к северу от острова Кнайпхоф расположен Альтштадт, к югу — Форштадт. Были построены мосты через Прегель, соединяющие эти четыре района. На рисунке справа показан центр Кёнигсберга на карте 1652 года с обозначениями: А — Альтштадт, Б — Кнайпхоф, В — Ломзе и Г — Форштадт.

История строительства мостов КёнигсбергаПравить

Основная статья: Мосты Калининграда

 

Центр Кёнигсберга с семью мостами и их номерами в порядке и постройки

Семь первых мостов центра Кёнигсберга, соединяющие Альтштадт, Кнайпхоф, Ломзе и Форштадт, были построены в указанные ниже годы в следующем порядке. Номера мостов в порядке их постройки показаны на рисунке справа.

1. Лавочный мост (1286)

Первый мост Кёнигсберга датируется 1286 годом. Соединил Альтштадт и Кнайпхоф. Принадлежал городу Альтштадт и обеспечивал городу легкий доступ к рынкам Кнайпхофа.

2. Зелёный мост (1322)

Второй мост Кёнигсберга построен в 1322 году. Соединил Кнайпхоф с Форштадтом и обеспечил легкий доступ к удалённым районам. Мост назывался Зелёным из-за зелёных волн, которые служат фоном герба Кнайпхофа.

3. Рабочий мост (1377)

В XIV веке на востоке Форштадта была скотобойня. Чтобы облегчить транспортировку мяса, в 1377 году между Кнайпхофом и Форштадтом был построен третий мост.

4. Кузнечный мост (1397)

в 1397 году в северо-восточной части Кнайпхофа был построен четвёртый Кузнечный мост, который начинался недалеко от кузнечных мастерских в Альтштадте.

Если по этим четырём мостам нарисовать граф, то он будет эйлеровым, то есть все четыре моста можно обойти по одному разу по замкнутому маршруту, начиная с любого места. Жители могли совершать такие прогулки.

5. Деревянный мост (1404)

На острове Ломзе заготавливали древесину, и пятый мост между Альтштадтом и Ломзе, построенный между 1400 и 1404 годами, облегчил доставку древесины.

6. Высокий мост (1506)

Шестой мост был построен в 1506 году, чтобы соединить Ломзе и Форштадт.

7. Медовый мост (1542)

Седьмой из мостов Эйлера, соединивший оба острова, был завершен в 1542 году. Он был построен жителями Кнайпхофа для прохождения на северный берег, минуя два моста из Кнайпхофа, контролируемые Альтштадтом. Согласно легенде, Кнайпхоф передал бочку меда Альтштадту, чтобы получить разрешение на строительство моста.

Итак, в 1542 году все семь мостов Кёнигсберга, рассмотренных Эйлером, были на месте. Теперь жители не могли обойти все мосты за один раз.

История задачиПравить

Возникновение раздела математики теория графов связано с математическими головоломками, и некоторое достаточно продолжительное время теория графов была «несерьёзна» и целиком связана с играми и развлечениями. Такая судьба теории графов повторяет судьбу теории вероятностей, также сначала находившей себе применение только в азартных играх.

Жители Кёнигсберга играли в своего рода игру: как пройти по всем городским мостам так, чтобы маршрут не пролегал ни по одному из них дважды. «Как я слышал, — писал Леонард Эйлер, — некоторые отрицают, что это можно сделать, другие сомневаются, но никто не подтверждает такой возможности.»

История публикации статьи Леонарда ЭйлераПравить

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

• сначала 26 августа (6 сентября) 1735 года Эйлер представил статью на Конференции Петербургской академии наук;
• затем в 1736 году Эйлер, в рамках своей научной переписки, отправил два следующих письма:

• 13 (24) марта 1736 года — письмо Иоганну Якобу Маринони^[de], австрийскому астроному и математику, от 13 [24] марта 1736 года, Петербург. Это письмо целиком посвящено задаче о кёнигсбергских мостах;
• 3 (14) апреля 1736 года — письмо Карлу Леонарду Готлибу Элеру^[de], немецкому политическому деятелю и астроному, от 3 [14] апреля 1736 года, Петербург. В конце этого письма идёт речь об основных идеях статьи;

• в 1741 году в Санкт-Петербурге наконец вышла статья Эйлера на латинском языке с датой 1736 года:

Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. P. 128—140.

В переводе:

Леонард Эйлер. Решение одной задачи, связанной с геометрией положения / Труды Петербургской академии наук. 8 (1736). 1741. С. 128—140.

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

Современное решение задачиПравить

Формулировка задачиПравить

 

Центр старого Кёнигсберга с рекой и семью мостами без лишних деталей

Задача о кёнигсбергских мостах разными авторами формулируется по-разному.

1. Маршрут произвольный

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

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

Для жителей Кёнигсберга существовала своего рода игра: найти такой маршрут прогулки по городу, который бы проходил через каждый из показанных на рисунке мостов ровно один раз.

— Фрич Р. и др. Избранные главы теории графов

2. Маршрут должен быть замкнутым

Задача состояла в следующем: найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.

— Фрэнк Харари. Теория графов

3. Замкнутые маршруты должны начинаться в каждой части города

Фактически требуется найти четыре маршрута обхода кёнигсбергских мостов, начинающиеся в четырёх частях города.

Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту?

— Оре О. Графы и их применение

Построение графа задачиПравить

 

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

Современное решение задачи о кёнигсбергских мостах начинается с построения графа задачи (см. рисунок справа):

• вершины графа — это четыре части центра Кёнигсберга, на которые разделён город двумя рукавами и протокой реки;
• ребра графа — это семь мостов в центре города;
• концевые вершины рёбер — это части центра Кёнигсберга, соединённые этими мостами.

Задачу о кёнигсбергских мостах можно переформулировать в терминах теории графов следующим образом:

• существует ли в графе задачи о кёнигсбергских мостах эйлеров цикл или хотя бы эйлерова цепь?

Теоремы ЭйлераПравить

Начнём с определений, перейдём к теоремам и закончим следствиями:

• эйлерова цепь — последовательность рёбер (соседние рёбра имеют общую вершину), которая обходит все рёбра графа по одному разу;
• эйлеров цикл — замкнутая эйлерова цепь.

Следующие две теоремы впервые появились в статье Леонарда Эйлера о кёнигсбергских мостах:

• первая теорема Эйлера, 1736. Граф с двумя или более вершинами имеет эйлеров цикл тогда и только тогда, когда в каждую вершину входит чётное число рёбер;
• вторая теорема Эйлера, 1736. Граф с двумя или более вершинами имеет единственную эйлерову цепь тогда и только тогда, когда ровно в две вершины входит нечётное число рёбер.

Из этих двух теорем можно вывести три следствия:

• если граф с двумя вершинами, в которые входит нечётное число рёбер, имеет эйлерову цепь, то эти две вершины — начальная и конечная вершины цепи;
• граф с двумя или более вершинами имеет эйлерову цепь тогда и только тогда, когда либо в каждую вершину входит чётное число рёбер, либо ровно в две вершины входит нечётное число рёбер;
• задача о кёнигсбергских мостах не имеет решения, поскольку в графе этой задачи нечётную степень имеют четыре вершины.

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

Формулировка задачиПравить

Леонард Эйлер в своей знаменитой статье сформулировал задачу о семи кёнигсбергских мостах следующим образом:

2. Эта задача, как мне сказали, довольно хорошо известна и связана вот с чем. В городе Кёнигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке. Рукава этой реки пересекают семь мостов а, b, с, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.

 

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

Решение задачиПравить

Леонард Эйлер сформулировал свой метод следующим образом (см. рисунок выше):

4. Весь мой метод основан на надлежащих обозначениях для отдельных прохождений мостов. Я использую заглавные буквы А, В, С, D для обозначения отдельных областей, на которые река разделяет сушу. Таким образом, если некто движется из области А в область В через мост а или b, то я обозначаю прохождение моста символом АВ.

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

На современном языке это означает, что схеме мостов города соответствует граф, представляющий собой:

• четыре вершины $A,B,C,D$$A,B,C,D\$  по обозначениям четырёх частей центра города;
• вершины соединены семью рёбрами-мостами $a,b,c,d,e,f,g$$a,b,c,d,e,f,g\$  по обозначениям семи мостов.

Достаточно современное и простое решение Леонардом Эйлером задачи о кёнигсбергских мостах выглядит следующим образом. Только следует иметь в виду, что Эйлер современной терминологии не знал, термин «граф» не использовал, называл ребро «мостом», а вершину — «областью» или «буквой» и не рисовал современные изображения графов.

• «Таким образом, становится очевидным, что если можно пройти по семи мостам, причём по каждому из них ровно по одному разу, то этот маршрут будет изображаться восемью буквами».
• «…я разработал правило, по которому можно легко решить — как для этой задачи, так и для всех подобных задач, — может ли быть осуществлено такое расположение букв.

«8. Чтобы вывести подобное правило, я рассматриваю некоторую конкретную область $A$$A\$ , в которую может вести произвольное число мостов $a,b,c,d$$a,b,c,d\$  и т. д. Из этих мостов сначала я рассмотрю конкретный мост $a$$a\$ , ведущий в область $A$$A\$ . Если путешественник пройдёт по этому мосту, то он либо находился в области $A$$A\$  до того, как прошёл по этому мосту, либо окажется в области $A$$A\$  после этого. Поэтому чтобы обозначить этот проход по мосту, как описано выше, необходимо, чтобы один раз возникла буква $A$$A\$ .»

• «Если в область $A$$A\$  ведут три моста, например $a,b,c$$a,b,c\$ , и путешественник проходит по всем трём мостам, то буква $A$$A\$  будет встречаться в описании его движения по мостам дважды независимо от того, начинался его маршрут из $A$$A\$  или нет. Точно так же, если в область $A$$A\$  ведут пять мостов, то буква $A$$A\$  должна встретиться при описании его движения три раза. И когда количество мостов — произвольное нечётное число, то если увеличить его на единицу, половина полученного числа показывает, сколько раз должна встретиться буква $A$$A\$ .»
• «9. Следовательно, в случае с кёнигсбергскими мостами, поскольку на остров $A$$A\$  ведут пять мостов $a,b,c,d,e$$a,b,c,d,e\$ , необходимо, чтобы буква $A$$A\$  встретилась в описании движения по этим мостам трижды. Кроме того, дважды должна встретиться буква $B$$B\$ , так как в область $B$$B\$  ведут три моста, и буквы $D,C$$D,C\$  должны встретиться по два раза каждая. Поэтому в последовательности из восьми букв, с помощью которой описывается рассматриваемый маршрут, проходящий через семь мостов, буква $A$$A\$  должна встретиться три раза, а каждая из букв $B,C,D$$B,C,D\$  — по два раза. Такого, однако, в последовательности из восьми букв быть не может. Таким образом, ясно, что подобная прогулка по семи мостам Кёнигсберга невозможна.»

Обобщение решения задачиПравить

Решая задачу в общем виде, Леонард Эйлер попутно доказал, что для любого графа число вершин с нечётным количеством рёбер чётно:

• «Вначале я отмечу, что все количества мостов», ведущих в области, «сложенные вместе, дают удвоенное число всех мостов. Причина состоит в том, что при таком подсчёте каждый мост считается дважды, с тем чтобы все мосты, ведущие в данную область, были учтены, ибо каждый мост ведёт в две области, которые он соединяет.

17. Из этого наблюдения вытекает, что сумма [чисел] всех мостов, ведущих в каждую область, есть чётное число, так как половина этой суммы есть в точности число мостов. Поэтому не может случиться так, чтобы среди чисел мостов, ведущих в любую область, в точности одно было нечётным; не может также случиться, чтобы нечётных чисел было три, пять и т. д. Следовательно, если числа мостов», ведущих в области, «суть нечётные числа, их сумма чётна.»

В конце статьи Леонард Эйлер записал общие выводы для любого графа вполне современным языком:

20. Значит в каждом возможном случае следующее правило позволяет непосредственно и без труда выяснить, можно ли осуществить прогулку по всем мостам без повторений:

Если имеется более двух областей, в которые ведет нечётное число мостов, можно заявить с уверенностью, что такая прогулка невозможна.

Если, однако, имеются только две области, в которые ведет нечётное число мостов, то прогулка осуществима при условии, что она начинается в одной из этих двух областей.

Если, наконец, нет ни одной области, в которую ведет нечётное число мостов, прогулка с требуемыми условиями осуществима, причём начинаться она может в любой области.

Следовательно, с помощью этого правила поставленная задача может быть полностью решена.

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

См. такжеПравить

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

ЛитератураПравить

• Оре О. Графы и их применение / Пер. с англ. Л. И. Головиной. Под ред. И. М. Яглома. М.: Мир, 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. Содержит оригинальный латинский текст писем и перевод на русский язык Ю. Х. Копелевич (письмо к Маринони) и Т. А. Лукиной (письмо к Элеру).
• 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.