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

 

Семь мостов Кенигсберга - исторически известная проблема в математике. Его отрицательное решение Леонардом Эйлером в 1736 году заложило основы теории графов и предвосхитило идею топологии.

Город Кенигсберг в Пруссии (ныне Калининград, Россия) располагался по обеим сторонам реки Прегель и включал в себя два больших острова — Кнайпхоф и Ломзе, которые были связаны друг с другом и с двумя материковыми частями города, семь мостов. Проблема заключалась в том, чтобы придумать маршрут прогулки по городу, при котором каждый из этих мостов пересекался бы один и только один раз.

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

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

 

Анализ Эйлера

Эйлер, который никогда не жил в Кенигсберге, первым указал, что выбор маршрута внутри каждого массива суши не имеет значения. Единственной важной особенностью маршрута является последовательность пересекаемых мостов. Это позволило ему переформулировать задачу в абстрактных терминах (заложив основы теории графов), исключив все признаки, кроме перечня массивов суши и соединяющих их мостов. Говоря современным языком, каждый массив суши заменяется абстрактной «вершиной» или узлом, а каждый мост заменяется абстрактным соединением, «ребром», которое служит только для записи того, какая пара вершин (массивов суши) соединена этим мостом. Полученная математическая структура представляет собой граф.

Поскольку имеет значение только информация о соединении, форма графического представления графа может быть искажена любым образом без изменения самого графа. Важно только наличие (или отсутствие) ребра между каждой парой узлов. Например, не имеет значения, являются ли нарисованные ребра прямыми или изогнутыми, или находится ли один узел слева или справа от другого.

Затем Эйлер заметил, что (за исключением конечных точек обхода), всякий раз, когда кто-то входит в вершину по мосту, он покидает вершину по мосту. Другими словами, во время любого обхода графа количество входов в неконечную вершину равно количеству выходов из нее. Теперь, если каждый мост был пройден ровно один раз, из этого следует, что для каждого массива суши (кроме тех, которые выбраны для начала и окончания) число мостов, касающихся этого массива земли, должно быть четным (половина из них, в определенный путь будет пройден «в сторону» суши, а другая половина — «в сторону» от нее). Однако все четыре массива суши в исходной задаче соприкасаются нечетным числом мостов (один соприкасается с 5 мостами, а каждый из трех других соприкасается по 3). Поскольку конечными точками прогулки могут служить не более двух участков суши, предположение о том, что прогулка проходит по каждому мосту один раз, приводит к противоречию.

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

Альтернативная форма задачи требует пути, который пересекает все мосты, а также имеет одинаковую начальную и конечную точки. Такое блуждание называется эйлеровой схемой или эйлеровым туром. Такая схема существует тогда и только тогда, когда граф связен и все узлы имеют четную степень. Все эйлеровы схемы также являются эйлеровыми путями, но не все эйлеровы пути являются эйлеровыми цепями.

Работа Эйлера была представлена ​​в Санкт-Петербургскую академию 26 августа 1735 г. и опубликована в журнале Commentarii academiae scientiarum Petropolitanae в 1741 г. под названием «Solutio Problematis ad geometriam situs pertinentis» («Решение проблемы геометрии положения»). в английском переводе в «Мире математики» Джеймса Р. Ньюмана.

 

Значение в истории и философии математики

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

Кроме того, признание Эйлером того, что ключевой информацией является количество мостов и список их конечных точек (а не их точное положение), предвещало развитие топологии. Разница между фактической компоновкой и графической схемой — хороший пример идеи о том, что топология не связана с жесткой формой объектов.

Следовательно, как признавал Эйлер, «геометрия положения» касается не «измерений и расчетов», а чего-то более общего. Это поставило под сомнение традиционный аристотелевский взгляд на математику как на «науку о количестве». Хотя этот взгляд соответствует арифметике и евклидовой геометрии, он не подходит для топологии и более абстрактных структурных особенностей, изучаемых современной математикой.

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

Современное состояние мостов
Два из семи первоначальных мостов не пережили бомбардировки Кенигсберга во время Второй мировой войны. Две другие позже были снесены и заменены современным шоссе. Три других моста сохранились, хотя только два из них со времен Эйлера (один был перестроен в 1935 году). Таким образом, по состоянию на 2022 год пять мостов существуют на тех же сайтах, которые были задействованы в задаче Эйлера. С точки зрения теории графов два узла теперь имеют степень 2, а два других имеют степень 3. Следовательно, теперь возможен эйлеров путь, но он должен начинаться на одном острове и заканчиваться на другом.

Кентерберийский университет в Крайстчерче включил модель мостов в лужайку между старой Библиотекой физических наук и зданием Эрскин, в котором размещаются факультеты математики, статистики и компьютерных наук. Реки заменены короткими кустами, а на центральном острове есть каменный торо. Рочестерский технологический институт включил головоломку в тротуар перед Центром Джина Полиссени, хоккейной ареной, которая открылась в 2014 году, а Технологический институт Джорджии также установил ландшафтную модель семи мостов в 2018 году.