Задача семи мостов

На модерации Отложенный

Как-то раз обещался рассказать про семь мостов Кёнигсберга – эта история должна быть хорошо известна среди математиков, а также быть на слуху для любознательных калининградцев. "Проблема семи мостов" легко нагугливается в сети, и единственным минусом множества посвящённых ей упоминаний мне представляется беллетризация текстов, отсутствие в них математического и логического анализа.

Что же это за задача, как она возникла и была разрешена.

Летопись Тевтонского ордена повествует нам, что в 1255 году великий магистр Поппо фон Остернa (Poppo von Osterna) вместе с чешским королём Оттокаром II Пржемыслом (Ottokar, Přemysl Otakar), призванным на помощь в очередной крестовый поход против прусских язычников, заложили в нижнем течении реки Прегель замок, орденскую крепость, получившую название в честь Оттокара - Королевская гора – Кёнигсберг - Königsberg. В 1257 году замок и будущий Альтштадт (Altstadt, Старый город) были обнесены рвом, в 1262 году после осады замка восставшими пруссами начинается кладка каменных стен. Почти сразу же по соседству появляются поселения - Альтштадт, Кнайпхоф (Kneiphof) и Лёбенихт (Löbenicht), каждое из которых получило права города в конце XIII – начале XIV века. Каждый из городов имел свой герб, у каждого были своё городское управление, свой суд и т.п., объединились они лишь в 1724 году, но обобщающее название Кёнигсберг закрепилось за ними со времени основания.

13 февраля 1511 года гроссмейстером ордена на собрании высших чинов и епископов был избран 20-летний Альбрехт Бранденбургский (Albrecht von Brandenburg-Ansbach) - по отцовской линии - из династии Гогенцоллернов, а по материнской - правнук Ягайло. После знакомства в Виттенберге с Мартином Лютером (Лютер посоветовал ему секуляризировать, т.е. конфисковать, собственность Тевтонского ордена и жениться), Альбрехт отказался от клятв, принесённых при вступлении в орден, и от католического вероисповедания, и при нём орденское церковное государство становится светским - наследственным герцогством Прусским.

Вклад герцога в развитие прусского государства был настолько значителен, что ещё при жизни его называли Великим, в дальнейшем же время его правления стали именовать Золотым веком Пруссии. В мае 1891 года у одной из башен замка Альбрехту был установлен памятник работы Иоганна Фридриха Ройша (Johann Friedrich Reusch), после войны бронзовая скульптура была отправлена на переплавку, а на постаменте долгое время стояла скульптура фельдмаршала Михаила Кутузова. К 750-летию города по сохранившейся копии монумента был изготовлен новый памятник герцогу (смотрим фото), который занял место в северо-восточной части острова Канта (бывший Кнайпхоф), там, где первоначально располагалась основанная им герцогская гимназия, преобразованная в университет – Альбертина (Collegium Albertinum).

Одной из самых значимых построек при Альбрехте явился новый мост (смотрим трофейную карту XVII века) между островами Кнайпхоф (K) и Ломзе (L) - "Медовый" (№ 7, Honigbrücke), который стал седьмым по счёту мостом через Прегель.

                                          Медовый мост, довоенное фото

Самым старым мостом был "Лавочный" (№ 1, Krämerbrücke, 1286 год), который соединял A, город Альтштадт (и Королевский замок) с островом Кнайпхоф.

                                               Лавочный мост до войны

Следующий - "Зелёный" мост (№ 2, Grünebrücke, 1322 год), соединил Кнайпхоф с его пригородом Форштадт (Vorstadt - V).

                                                     Зелёный мост, 1935 год

В 1377 году выше по течению был построен вспомогательный мост - "Рабочий", или "Потроховый" (№ 3, Köttelbrücke).

                                                         Рабочий мост, 1904 год

В 1397 году выстроен "дублёр" "Лавочного" моста, "Кузнечный" (№ 4, Schmiedebrücke).

                                                Кузнечный мост, довоенное фото

В 1404 году между Альтштадтом и островом Ломзе построен мост, который получил название "Деревянный" (№5, Holzbrücke), и наконец, в 1520 году "Высокий" (№6, Hohebrücke) мост соединил район Форштадт и остров Ломзе.

                                        Деревянный мост, 1907 год

                                                   Высокий мост, 1916 год

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

Итак, мостов стало семь, а возможных маршрутов - тысячи, и некоторые горожане стали задаваться вопросом, возможно ли найти такой маршрут, позволявший перейти все семь мостов, не ступив ни на один из них дважды.  Существовало даже поверье, согласно которому у проложившего такой маршрут должно исполниться загаданное желание. Отыскать ответ на этот вопрос пробовали и теоретически (трудность заключалась в том, что эта задача не кажется геометрической, поскольку не содержит ни одной известной фигуры или каких-либо величин) и практически. Было понятно, что просто сформулированная и раздражающе неуловимая проблема семи мостов содержит некое математическое ядро, однако формализовать её в рамках имеющегося на то время математического аппарата не удавалось: Готфрид Лейбниц в переписке 1679 года с Христианом Гюйгенсом и Христианом фон Вольфом обсуждал задачу о существовании маршрута обхода всех кёнигсбергских мостов и высказывал мнение о том, что она представляет собой новый тип геометрических задач, связанных не с размерами объектов, а только с их взаимным расположением (у Лейбница - geometriam situs, сегодня такие задачи называются топологическими), и что поэтому для её решения нужно использовать качественно новые методы.

Liesez Euler, Liesez Euler, c'est notre maоtre а tous… 
Пьер-Симон де Лаплас 

 

        

                     Леонард Эйлер. Портрет 1753 года работы Эмануэля Хандманна

Решить задачу о Кёнигсбергских мостах удалось лишь в 1736 году, когда проблемой заинтересовался академик Санкт-Петербургской Академии, профессор высшей математики Леонард Эйлер (Leonhard Euler), фактически положивший начало новому разделу математики – теории графов. Интерес Эйлера к задаче был, вероятно, инициирован его перепиской с математиком и астрономом, будущим бургомистром Данцига (и почти однофамильцем) Карлом Элером (Carl Leonhard Gottlieb Ehler). На рисунке ниже – схема задачи из письма Элера – Эйлеру от 9 марта 1736 года.

                                                   

Уже 13 марта 1736 года Эйлер в письме к придворному астроному австрийских Габсбургов Джованни Маринони (Giovanni Jacobo Marinoni) сообщил, что "…нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершён такой обход через какое угодно число и как угодно расположенных мостов или не может", и изложил итальянцу это правило.

                                                     

                                                        Письмо Эйлера Маринони

Авторы многих популярных статей, посвящённых семи мостам, не удосужившись заглянуть в оригинальную работу Эйлера "Solutio problematis ad geometriam situs pertinentis" ("Решение вопроса, связанного с геометрией положения"), датированную 1736 годом, и опубликованную в 1741 году в (первом русском) научном журнале-сборнике "Комментарии Петербургской Академии наук", сообщают, что тот абстрагировался от формы всех составляющих схемы и заменил их тем, что сегодня принято называть графом (рисунком в виде сети, что-то вроде того, что размещён чуть ниже) так, чтобы точки на суше стали вершинами, а мосты - дугами.

   

В действительности, никаких графов Эйлер не чертил - они появятся во второй половине ХIX века, а собственно граф Кёнигсбергской задачи – в первом издании работы W. W. Rouse Ball, Mathematical Recreations and Problems of Past and Present Times, Macmillan, London, 1892.

Сам же термин "граф" будет введён только в 1936 году Денешем Кёнигом (Denes König).

                      

                                                 Схема задачи из статьи Эйлера

Эйлер предложил строгое аналитическое решение на основе следующих соображений.

Маршрут прохода по мостам можно представить последовательностью A-B-D-C… Число символов (вершин) в маршруте, который проходит по каждому мосту один раз, на 1 больше числа мостов в маршруте, поскольку каждая пара соседних вершин-символов соответствует переходу по одному мосту.

Основное соображение Эйлера заключалось в том, что если вершина (к примеру, А) не является концевой точкой маршрута, то она соответствует проходу по двум мостам, соединяющим вершину А с другими вершинами. А если вершина является концевой точкой – то проходу по одному мосту.

Отсюда следует, что если маршрут проходит по N мостам, соединяющим вершину А с другими вершинами, то символ А появляется в записи маршрута (N+1)/2 раз, если N нечётное (и при этом один раз А является концевой точкой маршрута), а если Nчётное – то либо N/2, либо N/2+1 раз (в последнем случае маршрут начинается и заканчивается символом А). Эйлер отмечает, что у каждого моста-дуги – два конца и что поэтому сумма чисел мостов, соединяющих каждую из вершин с остальными, вдвое превосходит общее число мостов и поэтому должна быть чётной; но тогда число вершин, в которых заканчивается нечётное число мостов, тоже должно быть чётным. Из этих соображений Эйлер выводит, что если общее число дуг-мостов в задаче равно M, а число вершин с нечётным числом мостов равно 2m, то запись маршрута, проходящего по всем мостам, должна содержать M+m символов, что больше M+1, если m>1.

В современной теории графов путь, проходящий по одному разу по всем дугам графа, называют эйлеровым путём, а замкнутый эйлеров путь – эйлеровым циклом. Условия существования таких путей очень просты:

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

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

3. Сеть, имеющую больше двух нечётных вершин, нельзя полностью обойти одним маршрутом.

Кёнигсбергская сеть имеет 4 вершины, в каждой из которых сходится нечётное число дуг-мостов: все вершины – нечётные (N для них равны 3,3,3 и 5), следовательно, требуемого маршрута – не существует.

Долгое время – свыше ста лет - статья Эйлера была единственной в своей области, и лишь во второй половине XIX века интерес к подобным задачам возродился в связи со знаменитой "проблемой четырёх красок", поставленной в 1852 году перед математиками Огастесом Де Морганом (Augustus de Morgan), а позже - с исследованиями электрических и логистических сетей, моделей кристаллов и молекулярных структур.

Эйлер в письме к Маринони указал, что достаточно построить ещё один мост через Прегель, и задача обхода одним маршрутом восьми мостов, каждого по одному разу, становится разрешимой. (В современных терминах это не будет эйлеров цикл, а будет эйлеров путь - по причине того, что две вершины останутся нечётными, и стартовать придётся в одной из них, а заканчивать обход всех восьми мостов – в другой.) В этой связи весьма популярной является легенда о появлении на карте Кёнигсберга восьмого моста, связывающего остров Ломзе с Форштадтом. Якобы на одном из приёмов приглашённые гости вздумали подшутить над кайзером Вильгельмом II, предложив тому решить задачу о мостах.  Вильгельм, к всеобщему удивлению, заявил, что он решит задачу в считанные минуты, а на поданном листе бумаги написал: "Приказываю построить восьмой мост на остров Ломзе". Этот возведённый в 1905 году мост назвали "Императорским" (Kaiserbrücke).

   

                                          Императорский мост, 1905 год

П.С. Коль уж я затронул тему мостов, вкратце об их судьбе. Все восемь мостов серьёзно пострадали во время Второй мировой, некоторые из них к моменту взятия города находились в разведённом положении (таким образом наци надеялись задержать продвижение штурмовых групп Красной армии), на сегодняшний день сохранились лишь три из них. 

Лавочный и Зелёный мосты были снесены в 1972 году во время строительства эстакадного моста. Рабочий мост перестраивали в 1886 году, во время войны сооружение было разрушено, и мост был разобран на камень, опоры демонтировали в 70-х годах. Такая же участь постигла и Кузнечный мост.

Некогда самый красивый из кёнигсбергских мостов, Деревянный мост, был заново отстроен в камне в 1903-1904 годах, а сегодня незамысловато именуется "Мост №1". К сожалению, послевоенный ремонт лишил его большинства декоративных элементов.

   

                                                             Деревянный мост сегодня

Медовый мост – был перестроен в 1879-1882 годах, сегодня используется как пешеходный между островами Канта (Кнайпхоф) и Октябрьским (Ломзе). Проплывая под ним на прогулочном кораблике, можно увидеть элементы гидравлического разводного механизма, который ныне, конечно, не работает. Сплошь увешан символами вечной любви: на мой взгляд, довольно сомнительный бонус к декору. 

  

  

                                                           Медовый мост и его механизмы

Императорский мост был частично разрушен во время войны, но две опоры и центральный разводной пролёт простояли на реке до 80-х годов. 1 июля 2005 года, к 750-летию города на быках-опорах был выстроен новый мост, Юбилейный, внешне напоминающий Императорский. Также, как и у Медового, ограды моста скрыты под панцирем из замкόв.

    

                                                                          Юбилейный мост

Высокий мост в 1882 году перестроили, добавив к нему в 1899 году домик смотрителя со смотровой башней, в которой находились механизмы для разводки моста. В 1938 году мост снесли, а в нескольких десятках метров выстроили новый Высокий мост, который функционирует и сегодня.

  

                                                        Новый Высокий мост и домик смотрителя

Забавно, что уцелевший (и отреставрированный в 2000 году) домик смотрителя в наши дни вовсю эксплуатируется как экскурсионный объект: существует легенда о том, как барон Карл Фридрих Иероним фон Мюнхгаузен изрядно выпил в трактире рядом с Высоким мостом и зашёл в гости к местному смотрителю. Тот уложил гостя спать, однако кровать была настолько мала, что ноги барона высунулись в окно, и тут-то один сапог соскользнул с его ноги и утонул в Прегеле. Скептически настроенный турист, припомнив, что годы жизни и беспримерной службы барона пришлись на XVIII век, заметит про себя, что если барону когда и случалось по пьяному делу терять свой сапог, то это никак не могло произойти в этом, по-своему замечательном памятнике архитектуры.

П.П.С. И, раз уж мы завершили восточно-прусскую тему, предлагаю обмыть это дело музычкой. Прибегнем к помощи, может, и не самого выдающегося, но, по крайней мере, самого известного вокалиста из уроженцев этой земли. Нет, что вы, не пугайтесь, это будет не Олег Газманов. Нам с вами поможет родившийся в Тильзите (ныне – Советск) Йоахим Фритц Крауледат (Joachim Fritz Krauledat), он же – Джон Кэй, основатель и фронтмен команды Steppenwolf.  


Allah is speaking us all with his mighty voice

Bowing to his power as we go down

This magic carpet ride is not a dream to us

It's really happening

(Мы слышим речь Аллаха, говорит могучим гласом он,

Спускаясь на землю, мы преклоняемся перед его силой.

Этот полёт на ковре–самолете - не сон,

Это наяву.)

Поразительно, насколько актуально могут звучать тексты поп-песенок полувековой давности. 

Удачи всем.


Список источников:

Leonhard Euler. "Solutio Problematis ad Geometriam Situs Pertinentis", Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8 (1741), 128–140 (pdf-файл можно увидеть https://math.dartmouth.edu/~euler/docs/originals/E053.pdf )

Леонард Эйлер. "Письма к учёным", Изд. АН СССР, М.-Л., 1963

Hopkins, Brian & Wilson, Robin. "The Truth about Konigsberg" The College Mathematics Journal; 35.3 (2004) 202

Oystein Ore. "Theory Of Graphs", AMS, Providence, 1962

А. М. Зубков. "Эйлер и комбинаторика", Леонард Эйлер и современная математика, Сборник докладов, Совр. пробл. матем., 11, МИАН, М., 2008, 5–18