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

(перенаправлено с «Проблема семи мостов Кёнигсберга»)

Зада́ча о кёнигсбе́ргских моста́х[1][2][3] (лат. Problema Regiomontanum de septem pontibus[4], англ. the Königsberg Bridges problem[5], нем. Das Königsberger Brückenproblem[6]) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена официально в 1736 году[2][7] математиком Леонардом Эйлером, доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В переводе[10]:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оре О. Графы и их применение[15]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • четыре вершины   по обозначениям четырёх частей центра города;
  • вершины соединены семью рёбрами-мостами   по обозначениям семи мостов.

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

  • «Таким образом, становится очевидным, что если можно пройти по семи мостам, причём по каждому из них ровно по одному разу, то этот маршрут будет изображаться восемью буквами»;
  • «…я разработал правило, по которому можно легко решить — как для этой задачи, так и для всех подобных задач, — может ли быть осуществлено такое расположение букв.
8. Чтобы вывести подобное правило, я рассматриваю некоторую конкретную область  , в которую может вести произвольное число мостов   и т. д. Из этих мостов сначала я рассмотрю конкретный мост  , ведущий в область  . Если путешественник пройдёт по этому мосту, то он либо находился в области   до того, как прошёл по этому мосту, либо окажется в области   после этого. Поэтому чтобы обозначить этот проход по мосту, как описано выше, необходимо, чтобы один раз возникла буква  »;
  • «Если в область   ведут три моста, например  , и путешественник проходит по всем трём мостам, то буква   будет встречаться в описании его движения по мостам дважды независимо от того, начинался его маршрут из   или нет. Точно так же, если в область   ведут пять мостов, то буква   должна встретиться при описании его движения три раза. И когда количество мостов — произвольное нечётное число, то если увеличить его на единицу, половина полученного числа показывает, сколько раз должна встретиться буква  »;
  • «9. Следовательно, в случае с кёнигсбергскими мостами, поскольку на остров   ведут пять мостов  , необходимо, чтобы буква   встретилась в описании движения по этим мостам трижды. Кроме того, дважды должна встретиться буква  , так как в область   ведут три моста, и буквы   должны встретиться по два раза каждая. Поэтому в последовательности из восьми букв, с помощью которой описывается рассматриваемый маршрут, проходящий через семь мостов, буква   должна встретиться три раза, а каждая из букв   — по два раза. Такого, однако, в последовательности из восьми букв быть не может. Таким образом, ясно, что подобная прогулка по семи мостам Кёнигсберга невозможна.»

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

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

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

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

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

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

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

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

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

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

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

ПримечанияПравить

  1. 1 2 Харари Фрэнк. Теория графов, 2003, с. 13.
  2. 1 2 3 4 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 11.
  3. 1 2 3 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 1.
  4. Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 17.
  5. Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. vii.
  6. Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. ix.
  7. Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 151.
  8. 1 2 3 4 5 6 7 8 9 10 11 Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg, 2007.
  9. Оре О. Графы и их применение, 1965, с. 6.
  10. 1 2 3 4 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 26.
  11. 1 2 3 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 15.
  12. Письма к ученым, 1963, с. 152—158.
  13. Письма к ученым, 1963, с. 330—353.
  14. Eulero, 1741.
  15. Оре О. Графы и их применение, 1965, с. 33.
  16. Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 4.
  17. 1 2 3 4 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 8—12.
  18. 1 2 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 27—28.
  19. 1 2 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 31—32.

ИсточникиПравить

  • Оре О. Графы и их применение / Пер. с англ. Л. И. Головиной. Под ред. И. М. Яглома. М.: Мир, 1965. 174 с.: ил.
  • Харари Фрэнк. Теория графов / Пер. с англ. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд-е 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. Содержит оригинальный латинский текст писем и перевод на русский язык Ю. Х. Копелевич (письмо к Маринони) и Т. А. Лукиной (письмо к Элеру).
  • Leonh. Eulero. Solutio Problematis ad Geometriam Situs pertinentis (лат.) // Commentarii Academiae Scientiarum Imperialis Petropolitanae. Tomus VIII. Ad annum MDCCXXXVI. — Petropoli, 1741. — P. 128—140.
  • Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg–A Historical Perspective // Networks. 2007. 49(3):199–203.

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