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

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

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

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

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

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

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

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

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

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

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

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

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