Семь мостов Кёнигсберга — исторически значимая задача в математике. Её отрицательное решение Леонардом Эйлером в 1736 году [1] заложило основы теории графов и предвосхитило идею топологии . [2]
Город Кёнигсберг в Пруссии (ныне Калининград , Россия ) был расположен по обе стороны реки Прегель и включал два больших острова — Кнайпхоф и Ломзе , — которые были соединены друг с другом и с двумя материковыми частями города семью мостами. Проблема состояла в том, чтобы придумать прогулку по городу, которая пересекала бы каждый из этих мостов один и только один раз.
Путем однозначного определения логической задачи возможны решения, включающие либо
являются явно неприемлемыми.
Эйлер доказал, что проблема не имеет решения. Трудность, с которой он столкнулся, заключалась в разработке подходящей техники анализа и последующих испытаний, которые установили бы это утверждение с математической строгостью.
Эйлер первым указал на то, что выбор маршрута внутри каждого массива суши не имеет значения и что единственной важной характеристикой маршрута является последовательность пересеченных мостов. Это позволило ему переформулировать задачу в абстрактных терминах (заложив основы теории графов ), исключив все характеристики, кроме списка массивов суши и соединяющих их мостов. В современных терминах каждый массив суши заменяется абстрактной « вершиной » или узлом, а каждый мост — абстрактной связью, « ребром », которое служит только для записи того, какая пара вершин (массивов суши) соединена этим мостом. Полученная математическая структура представляет собой граф .
→
→
Поскольку важна только информация о соединении, форма графических представлений графа может быть искажена любым образом, без изменения самого графа. Важно только количество ребер (возможно, нулевое) между каждой парой узлов. Например, не имеет значения, являются ли нарисованные ребра прямыми или изогнутыми, или находится ли один узел слева или справа от другого.
Далее Эйлер заметил, что (за исключением конечных точек маршрута), всякий раз, когда кто-то входит в вершину по мосту, он покидает вершину по мосту. Другими словами, во время любого маршрута по графу количество входов в нетерминальную вершину равно количеству выходов из нее. Теперь, если каждый мост был пройден ровно один раз, то из этого следует, что для каждого массива суши (за исключением выбранных для начала и конца) количество мостов, касающихся этого массива суши, должно быть четным (половина из них, в конкретном маршруте, будет пройдена «по направлению» к массиву суши; другая половина — «от» него). Однако все четыре массива суши в исходной задаче соприкасаются нечетным числом мостов (один соприкасается с 5 мостами, а каждый из трех других соприкасается с 3). Поскольку конечными точками прогулки могут служить максимум два участка суши, предположение о том, что прогулка проходит через каждый мост один раз, приводит к противоречию.
На современном языке Эйлер показывает, что возможность обхода графа, проходящего по каждому ребру ровно один раз, зависит от степеней узлов. Степень узла — это количество ребер, его касающихся. Аргумент Эйлера показывает, что необходимым условием для обхода желаемого вида является то, что граф должен быть связным и иметь ровно ноль или два узла нечетной степени. Это условие оказывается также достаточным — результат, сформулированный Эйлером и позже доказанный Карлом Хирхольцером . Такой обход теперь называется эйлеровым путем или эйлеровым путем в его честь. Кроме того, если есть узлы нечетной степени, то любой эйлеров путь будет начинаться в одном из них и заканчиваться в другом. Поскольку граф, соответствующий историческому Кёнигсбергу, имеет четыре узла нечетной степени, он не может иметь эйлерова пути.
Альтернативная форма задачи требует путь, который проходит через все мосты и также имеет одну и ту же начальную и конечную точку. Такой путь называется эйлеровым контуром или эйлеровым туром . Такой контур существует тогда и только тогда, когда граф связен и все узлы имеют четную степень. Все эйлеровы контуры также являются эйлеровыми путями, но не все эйлеровы пути являются эйлеровыми контурами.
Работа Эйлера была представлена Петербургской академии 26 августа 1735 года и опубликована под названием Solutio problematis ad geometriam situs pertinentis (Решение задачи, относящейся к геометрии положения) в журнале Commentarii academiae scientiarum Petropolitanae в 1741 году. [3] Она доступна в английском переводе в книге Джеймса Р. Ньюмена «Мир математики» .
В истории математики решение Эйлера задачи о мосте в Кенигсберге считается первой теоремой теории графов и первым истинным доказательством в теории сетей [4] , которая в настоящее время обычно рассматривается как раздел комбинаторики . Комбинаторные задачи других типов, такие как перечисление перестановок и сочетаний, рассматривались со времен античности.
Осознание Эйлером того, что ключевой информацией является количество мостов и список их конечных точек (а не их точное положение), предвещало развитие топологии . Разница между фактической компоновкой и схемой графа является хорошим примером идеи о том, что топология не имеет отношения к жесткой форме объектов.
Следовательно, как признавал Эйлер, «геометрия положения» не касается «измерений и вычислений», а чего-то более общего. Это поставило под вопрос традиционный взгляд Аристотеля на то, что математика — это «наука о количестве ». Хотя этот взгляд соответствует арифметике и евклидовой геометрии, он не соответствует топологии и более абстрактным структурным особенностям, изучаемым в современной математике. [5]
Философы отметили, что доказательство Эйлера не касается абстракции или модели реальности, а напрямую касается реального расположения мостов. Следовательно, уверенность математического доказательства может быть применена непосредственно к реальности. [6] Доказательство также является объяснительным, давая представление о том, почему результат должен быть истинным. [7]
Два из семи первоначальных мостов не пережили бомбардировку Кёнигсберга во время Второй мировой войны . Два других были позже снесены и заменены шоссе. Три других моста сохранились, хотя только два из них относятся к временам Эйлера (один был восстановлен в 1935 году). [8] Эти изменения оставляют пять мостов, существующих на тех же местах, которые были задействованы в задаче Эйлера. С точки зрения теории графов, два из узлов теперь имеют степень 2, а два других — степень 3. Следовательно, теперь возможен эйлеров путь, но он должен начинаться на одном острове и заканчиваться на другом. [9]
Университет Кентербери в Крайстчерче включил модель мостов в травяную зону между старой Библиотекой физических наук и зданием Эрскина, где размещаются факультеты математики, статистики и компьютерных наук. [10] Реки заменены короткими кустами, а на центральном острове красуется каменный tōrō . Рочестерский технологический институт включил головоломку в тротуар перед Центром Джина Полиссени , хоккейной ареной, которая открылась в 2014 году, [11] а Технологический институт Джорджии также установил модель ландшафтного искусства из семи мостов в 2018 году. [12]
Популярный вариант головоломки — Bristol Bridges Walk . [13] Как и исторический Кёнигсберг, Бристоль занимает два речных берега и два речных острова. [14] Однако конфигурация 45 главных мостов в Бристоле такова, что существует эйлеров цикл. [15] Этот цикл был популяризирован книгой [15] и новостными репортажами [16] [17] и был представлен на различных благотворительных мероприятиях. [18]
