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

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

Маршрут прохода по мостам можно представить последовательностью 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 году мост назвали "Императорским" (Kaiserbrucke).