Город Кёнигсберг был основан в 1255 году рыцарями тевтонского ордена. Они построили замок, который вместе с окрестными поселениями и стал впоследствии городом Кёнигсбергом. Можно было бы много рассказывать об истории города в целом, но мы сосредоточимся на её математической стороне. Одной из математических сторон.

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

У мостов были простые красивые названия: Зелёный, Деревянный, Кузнечный, Медовый, Потроховый, Высокий, Лавочный. К 1542 году мостов было семь. Они вели с одного берега Преголи на один остров, с острова – на другой остров или на другой берег, и так далее.

И вот в какой-то момент у жителей Кёнигсберга появилась такая игра: они пытались обойти все городские мосты, при этом не проходя ни по какому дважды. Была и модификация этой игры: когда требовалось выйти из какого-то конкретного места и вернуться в то же самое место, при этом опять же обходя все мосты и проходя по каждому ровно один раз. То есть построить замкнутый маршрут. Эта задача со временем получила название "Задача о семи Кёнигсбергских мостах" или просто "Задача о мостах Кёнигсберга". Никому не удавалось решить эту задачу ни в одном из вариантов, но неудачи одних не отнимали энтузиазма у других. Тем более что начинать маршрут можно было в любой точке. И если не получается построить нужный путь с началом в одной точке, то можно попробовать сделать это из другой.

Мы со школьных времён привыкли, что все задачи имеют решение: нам выдали условие, требуется что-то найти или построить. В данном случае задача состоит в построении маршрута. Дана карта, на которой нарисована река с островами, обозначены места расположения мостов. Что означает "решить задачу о мостах Кёнигсберга"? Один вариант решения – это построить маршрут, который удовлетворяет условию задачи: он обходит все мосты ровно один раз, проходя через каждый и ни через какой не проходя дважды. Такое решение обычно называют положительным. Второй вариант решения – доказать, что решения не существует, т.е. что построить такой маршрут невозможно. Про такой вариант говорят, что найдено отрицательное решение задачи. Первый вариант я бы назвала простым: достаточно построить один такой маршрут, и всё: задача решена. А если маршрут построить не получается? Означает ли это, что задача не имеет решения? Нет, не означает. Если вы построили маршрут, то всё: вам пятёрка, решение можно оформить в виде статьи в журнале, и любой, кто прочитает это решение, может повторить маршрут сам. Если вы не смогли построить маршрут, это ровным счётом ничего не означает. В этом случае вариантов опять два: либо задача действительно не имеет решения (и построить нужный маршрут невозможно), либо вам просто не хватило мозгов, чтобы его найти. Выражение "задача не имеет решения" очень конкретное, оно передаёт простую мысль: сколько ни ходи по мостам Кёнигсберга, построить маршрут, проходящий по каждому мосту ровно один раз, невозможно. Не просто "вот неудача – попробуем ещё раз", а "нет, невозможно, сколько ни пытайся, не трать время". И это выражение очень сильное. Чтобы можно было сказать, что задача не имеет решения, этот факт нужно доказать.

На самом деле, для случая, когда число всех возможных маршрутов конечно (я не буду на этом останавливаться, но в нашем случае это именно так), задачу можно решить перебором. Просто проверить каждый из возможных путей через мосты, отбрасывая неподходящие. В процессе либо найдётся нужный маршрут (и задача решена – положительно), либо все возможности будут проверены и признаны неподходящими (и задача снова решена – отрицательно). Если перебор проведён аккуратно (т.е. никакой из вариантов ТОЧНО не пропущен) и ни один из вариантов не подошёл, можно с уверенностью сказать, что задача о семи Кёнигсбергских мостах не имеет решения. Я честно не знаю, пытался ли кто-то в 16-м веке решать эту задачу перебором. Если пытался – история не сохранила его имя. Но я скажу вам, как математик: решать задачу перебором неинтересно, к такому способу прибегают в крайнем случае, когда красивое решение найти не получается. Понятно, что в 16-м веке это было недоступно, но в наше с вами время задачу перебора можно легко поручить компьютеру. ЕСЛИ вы сможете составить грамотный код. И ДОКАЗАТЬ, что он грамотный и действительно перебирает все решения. Ну ладно. Возвращаемся в прошлое.

Горожане "заражали" своей игрой с мостами гостей города, и примерно в 1735 году о ней узнал математик Леонард Эйлер, которому в то время было 29 лет и который на этот момент был академиком Петербургской Академии наук и профессором высшей математики. К этому моменту история семи Кёнигсберсгих мостов насчитывала уже около 200 лет. Не знаю, сколько из этих двухсот лет жители стаптывали башмаки, безуспешно пытаясь составить нужный маршрут по мостам. Надеюсь только, что они посвящали этому не слишком много времени.

Первый лист статьи Л. Эйлера на латыни

Эйлер заинтересовался этой задачей, решил её и изложил её решение в статье под названием "Решение одной задачи, связанной с геометрией положения", которую он в августе 1735 года представил Петербургской академии наук. Интересно, что статья вышла только в 1741 году (спустя шесть лет), сначала на латинском языке, а потом – в переводе на русский. Справедливости ради стоит заметить, что, хотя статья была опубликована в 1741 году, выход статьи из печати, тем не менее, был датирован 1736-м годом.

Вот теперь самое интересное. Во-первых, я сказала, что "Эйлер решил эту задачу". На самом деле, он решил её отрицательно. То есть Эйлер доказал, что эта задача не имеет решения. Это означает, что не существует маршрута, который обходил бы все семь мостов Кёнигсберга, проходя по каждому из них ровно один раз. Не существует ни замкнутого маршрута (начало и конец которого совпадают), ни маршрута, ведущего из одной точки Кёнигсберга в другую. Во-вторых, Эйлер не просто решил эту конкретную задачу. Он привёл решение для всех подобных задач: не важно, сколько у вас частей суши и сколько между ними мостов. Он объяснил, при каком расположении мостов и участков суши нужный маршрут будет или не будет существовать. В-третьих, решением этой задачи Эйлер положил начало новой математической дисциплине, которая стала называться "теорией графов". Граф – это просто множество точек (они обычно называются вершинами графа), соединённых между собой дугами (они обычно называются рёбрами графа).

В нашей задаче вершин у графа четыре: это четыре части города Кёнигсберга (один берег Преголи, второй её берег и два острова посреди реки). Рёбер у графа семь, это семь мостов, которые соединяют наши части города. Если есть мост, который соединяет два берега реки, то на схеме мы рисуем дугу, которая соединяет вершину, соответствующую одному берегу, с вершиной, соответствующей другому берегу. Во времена Эйлера ещё не существовало всех этих терминов, они появились позднее, он называл рёбра мостами, а вершины графа – областями или буквами, потому что именно четырьмя буквами, $A, B, C$ и $D$, он обозначил части города Кёнигсберга, соединённые мостами. Произвольный маршрут по мостам (не обязательно удовлетворяющий условию нашей задачи) он записывал последовательностью этих букв. Например, $ABCA$ означает, что мы начали в области $A$, перешли по какому-то мосту в область $B$, затем – в $C$ и, наконец, вернулись в $A$.

Дальше я просто приведу цитаты из работы Эйлера, которые объясняют рассуждения и приводят к решению задачи. Если до этого вы слушали эту историю фоном, то сейчас, если вы хотите понять ход рассуждений, нужно будет немножко сосредоточиться. Сложно не будет, обещаю. Итак, решение задачи от лица Эйлера.

Первый этап рассуждений такой: "Очевидно, что если можно пройти по семи мостам, причём по каждому из них ровно по одному разу, то этот маршрут будет изображаться восемью буквами". Это понятно, да? Мы начинаем в какой-то области, последовательно проходим по семи мостам, заканчиваем в какой-то области. То есть маршрут у нас такой: буква–мост–буква–мост и т.д., заканчиваем буквой. Поскольку мостов между буквами семь, то букв – восемь. Итак, нужный нам маршрут обозначается восемью буквами.

Второй этап: (начало цитаты) "Я рассматриваю некоторую конкретную область $A$, в которую может вести произвольное число мостов: первый, второй, третий и т. д. Из этих мостов сначала я рассмотрю конкретный мост, например, номер 1, ведущий в область $A$. Если путешественник пройдёт по этому мосту, то он либо находился в области A до того, как прошёл по этому мосту, либо окажется в области $A$ после этого. Поэтому чтобы обозначить этот проход по мосту, как описано выше, необходимо, чтобы один раз возникла буква $A$." (конец цитаты) Это тоже понятно: если наш мост под номером 1 ведёт из буквы $А$ в букву, например $B$, то, если мы шли из $A$ в $B$, эта часть маршрута обозначается последовательностью букв $AB$, а если шли в обратную сторону, то последовательность букв будет $BA$, но в любом случае $A$ встретится один раз.

Дальше: (начало цитаты) "Если в область ${\displaystyle A\ }$ ведут три моста, например, первый, второй и третий и путешественник проходит по всем трём мостам, то буква ${\displaystyle A\ }$будет встречаться в описании его движения по мостам дважды независимо от того, начинался его маршрут из ${\displaystyle A\ }$или нет." (конце цитаты) Это чуть сложнее, но рассуждения станут понятнее, если вы нарисуете себе картинку: кружочек – это ваша область A, к кружочку ведут, скажем, три моста. Попробуйте прогуляться с помощью карандаша по этим мостам: каким бы маршрутом вы ни гуляли, в области А вы окажетесь дважды. Рассуждаем дальше (начало цитаты) "Точно так же, если в область ${\displaystyle A\ }$ ведут пять мостов, то буква ${\displaystyle A\ }$должна встретиться при описании его движения три раза. И когда количество мостов — произвольное нечётное число, то если увеличить его на единицу, половина полученного числа показывает, сколько раз должна встретиться буква ${\displaystyle A\ }$." (конец цитаты) Для любого нечётного количества мостов рассуждения аналогичные: чтобы посчитать, сколько раз встретится буква А, если к ней ведёт любое нечётное число мостов, нужно к этому числу прибавить единицу, и результат разделить пополам: для трёх мостов это три плюс один пополам – два, для пяти – пять плюс один пополам – это три, для семи – четыре, и т.д.

Ну и, наконец, третий этап – это наши конкретные мосты города Кёнигсберга: (начало цитаты) "Следовательно, в случае с кёнигсбергскими мостами, поскольку на остров ${\displaystyle A\ }$ ведут пять мостов, необходимо, чтобы буква ${\displaystyle A\ }$встретилась в описании движения по этим мостам трижды. Кроме того, дважды должна встретиться буква ${\displaystyle B\ }$, так как в область ${\displaystyle B\ }$ведут три моста, и буквы ${\displaystyle D,C\ }$должны встретиться по два раза каждая (потому что туда тоже ведут по три моста).

Поэтому в последовательности из восьми букв, с помощью которой описывается рассматриваемый маршрут, проходящий через семь мостов, буква ${\displaystyle A\ }$должна встретиться три раза, а каждая из букв ${\displaystyle B,C,D\ }$ — по два раза. Такого, однако, в последовательности из восьми букв быть не может. Таким образом, ясно, что подобная прогулка по семи мостам Кёнигсберга невозможна." (конец цитаты) Вот и всё решение. Несложно, правда? И что они там мучились двести лет?

Все эти мосты наложили неизгладимый отпечаток на историю Кёнигсберга, сделав его не только знаменитым, но и одним из красивейших городов северной Европы. Несмотря на то, что задача была решена, жители города продолжали в шутку загадывать эту загадку гостям Кёнигсберга, и однажды – по преданию – это привело к своего рода курьёзу. История эта связана с последним императором Пруссии Вильгельмом II, который был известен как нетерпеливый и энергичный правитель, исполненный решимости выполнять свою волю, всегда отдававший предпочтение самому крайнему варианту действий. Однажды на светском рауте над императором решили подшутить учёные мужи, предложив ему эту самую задачу о мостах Кёнигсберга, которая, как нам уже известно, не имеет положительного решения. Но император не растерялся и спокойно сказал, что решит эту задачу за одну минуту: для этого ему нужны всего лишь перо и карта города.

Карта Кёнигсберга с восемью мостами

Император взял перо и нарисовал ещё один мост, соединяющий берег с одним из островов, сказав: «Повелеваю построить здесь восьмой мост города» и спокойно удалился, оставив учёных в лёгком недоумении. Конечно, это только легенда, но красивая же! Мост, между прочим, действительно был построен (в 1905 году), он был назван Императорским.

Сейчас из тех самых мостов Кёнигсберга сохранилось только три, причём два из них – в реконструированном виде. В 1882 году на месте старого Медового моста был сооружен из металла новый мост. В 1937 году был разобран старый Высокий мост, а чуть восточнее сооружён новый из стали и бетона. При штурме Кёнигсберга в 1945 году были повреждены Деревянный, Кузнечный, Потроховый и Императорский мосты. При строительстве Эстакадного моста в 1972 году Лавочный, Зелёный, Потроховый и Кузнечный мосты были снесены. В середине 80-х XX века был также окончательно разобран Императорский мост. Единственный уцелевший в почти первозданном виде мост – это Деревянный мост. Правда, его разводная часть при ремонте была заменена той же частью разобранного Потрохового моста, но сам мост на месте. Кёнигсберг превратился в Калининград, один из островов посреди Преголи стал называться Октябрьским островом, второй – островом Иммануила Канта. И при современном расположении мостов старая задача о мостах Кёнигсберга имеет решение. Теперь прогулка по всем мостам Калининграда, проходящая по каждому ровно один раз, возможна.

Вот так. А вы говорите – "кому нужна твоя математика"? А математика – она такая, она везде. Её в дверь гонишь, а она через мост лезет.

До свиданья. До следующей встречи.