Введение

Классическая задача в теории графов

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

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

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

Современное состояние мостов

Два из семи первоначальных мостов не пережили бомбардировки Кёнигсберга во время Второй мировой войны. Два других моста были позднее снесены и заменены автомагистралью. Три оставшихся моста сохранились, хотя только два из них относятся ко времени Эйлера (один был перестроен в 1935 году). Таким образом, по состоянию на 2023 год пять мостов существуют на тех же местах, которые были вовлечены в проблему Эйлера. С точки зрения теории графов, два узла теперь имеют степень 2, а два других – степень 3. Следовательно, эйлеров путь теперь возможен, но он должен начинаться на одном острове и заканчиваться на другом. Университет Кентербери в Крайстчерче включил модель мостов в травяную зону между старой библиотекой естественных наук и зданием Эрскина, где располагаются кафедры математики, статистики и компьютерных наук. Реки заменены невысокими кустарниками, а на центральном острове установлен каменный торо. Рочестерский технологический институт включил эту головоломку в мощение перед Центром Джина Полиссени, ледовой ареной, открытой в 2014 году, а Технологический институт Джорджии также установил ландшафтную модель семи мостов в 2018 году. Популярным вариантом головоломки является "Прогулка по мостам Бристоля". Как и исторический Кёнигсберг, Бристоль расположен на двух берегах реки и двух речных островах. Однако конфигурация 45 основных мостов в Бристоле такова, что существует эйлеров цикл. Этот цикл был популяризирован книгой и представлен на различных благотворительных мероприятиях.