Семь мостов Кенигсберга исторически примечателен проблема в математике. Его отрицательное решение Леонарда Эйлера в 1736 г. [1] заложило основы теории графов и прообразило идею топологии . [2]
Город Кенигсберг в Пруссии (ныне Калининград , Россия ) был расположен по обе стороны реки Прегель и включал два больших острова - Кнайпхоф и Ломсе , - которые были связаны друг с другом или с двумя материковыми частями города посредством семь мостов. Проблема заключалась в том, чтобы придумать прогулку по городу, которая бы пересекала каждый из этих мостов только один раз.
Путем однозначной постановки логической задачи решения, предполагающие либо
- добраться до острова или материкового берега, кроме как через один из мостов, или
- доступ к любому мосту без перехода на другой его конец
явно неприемлемы.
Эйлер доказал, что проблема не имеет решения. Трудность, с которой он столкнулся, заключалась в разработке подходящей техники анализа и последующих тестов, которые с математической строгостью подтвердили это утверждение.
Анализ Эйлера
Во-первых, Эйлер указал, что выбор маршрута внутри каждого массива суши не имеет значения. Единственная важная особенность маршрута - это последовательность пересечения мостов. Это позволило ему переформулировать проблему в абстрактных терминах (заложив основы теории графов ), устранив все особенности, кроме списка массивов суши и соединяющих их мостов. Говоря современным языком, каждый наземный массив заменяется абстрактной « вершиной » или узлом, а каждый мост - абстрактным соединением, « ребром », которое служит только для записи того, какая пара вершин (наземных масс) соединена этим мостом. Полученная математическая структура представляет собой график .
→ →
Поскольку важна только информация о подключении, форма графических представлений графа может быть искажена любым способом без изменения самого графа. Важно только наличие (или отсутствие) ребра между каждой парой узлов. Например, не имеет значения, являются ли нарисованные края прямыми или изогнутыми, и находится ли один узел слева или справа от другого.
Затем Эйлер заметил, что (кроме конечных точек прогулки) всякий раз, когда кто-то входит в вершину по мосту, он выходит из вершины по мосту. Другими словами, во время любого обхода графа количество раз, когда человек входит в нетерминальную вершину, равно количеству раз, когда он выходит из нее. Теперь, если каждый мост был пересечен ровно один раз, из этого следует, что для каждого массива суши (кроме выбранных для начала и конца) количество мостов, соприкасающихся с этим массивом суши, должно быть четным (половина из них в конкретный переход, будет пройден «к» суше, а другая половина - «от нее»). Однако все четыре массива суши в исходной задаче затронуты нечетным числом мостов (одного касаются 5 мостов, а каждого из трех других - 3). Поскольку конечными точками прогулки могут служить не более двух участков суши, предложение пройти через каждый мост один раз приводит к противоречию.
Выражаясь современным языком, Эйлер показывает, что возможность обхода графа, проходящего через каждое ребро ровно один раз, зависит от степеней узлов. Степень узла - это количество соприкасающихся с ним ребер. Аргумент Эйлера показывает, что необходимое условие для перехода к желаемой форме состоит в том, чтобы граф был связным и имел ровно ноль или два узла нечетной степени. Это условие также оказывается достаточным - результат, сформулированный Эйлером, а затем доказанный Карлом Хирхольцером . Такая прогулка теперь называется эйлерами путем или Euler прогулкой в его честь. Далее, если есть узлы нечетной степени, то любой эйлеров путь будет начинаться на одном из них и заканчиваться на другом. Поскольку граф, соответствующий историческому Кенигсбергу, имеет четыре узла нечетной степени, у него не может быть эйлерова пути.
В альтернативной форме задачи предлагается путь, который пересекает все мосты и имеет одинаковую начальную и конечную точки. Такая прогулка называется эйлеровым кругом или эйлеровым туром . Такая схема существует тогда и только тогда, когда граф связен и нет узлов нечетной степени вообще. Все эйлеровы схемы также являются эйлеровыми путями, но не все эйлеровы цепи являются эйлеровыми схемами.
Работа Эйлера была представлена Петербургской академии 26 августа 1735 года и опубликована как Solutio problematis ad geometriam situs pertinentis (Решение проблемы, касающейся геометрии положения) в журнале Commentarii academiae scientiarum Petropolitanae в 1741 году [3]. Он доступен в английском переводе в книге Джеймса Р. Ньюмана «Мир математики » .
Значение в истории и философии математики
В истории математики решение Эйлера проблемы Кенигсбергского моста считается первой теоремой теории графов и первым истинным доказательством в теории сетей [4], предметом, который сейчас обычно считается разделом комбинаторики . Комбинаторные задачи других типов рассматривались с древних времен.
Кроме того, признание Эйлером того, что ключевой информацией является количество мостов и список их конечных точек (а не их точное положение), предвещало развитие топологии . Разница между фактической компоновкой и схемой графа является хорошим примером идеи о том, что топология не связана с жесткой формой объектов.
Следовательно, как признавал Эйлер, «геометрия положения» связана не с «измерениями и расчетами», а с чем-то более общим. Это поставило под сомнение традиционное аристотелевское представление о математике как о «науке о количестве ». Хотя этот взгляд соответствует арифметике и евклидовой геометрии, он не подходит для топологии и более абстрактных структурных особенностей, изучаемых современной математикой. [ необходима цитата ]
Философы отметили, что доказательство Эйлера касается не абстракции или модели реальности, а непосредственно реального расположения мостов. Следовательно, уверенность математического доказательства может применяться непосредственно к реальности. [5]
Современное состояние мостов
Два из семи оригинальных мостов не пережили бомбардировку Кенигсберга во время Второй мировой войны . Два других позже были снесены и заменены современной автомагистралью. Остались еще три моста, хотя только два из них относятся к временам Эйлера (один был перестроен в 1935 году). [6]
Таким образом, по состоянию на 2021 г.[Обновить], пять мостов существуют на тех же участках, которые были задействованы в проблеме Эйлера.
С точки зрения теории графов, два узла теперь имеют степень 2, а два других - степень 3. Следовательно, теперь возможен эйлеров путь, но он должен начинаться на одном острове и заканчиваться на другом. [7]
Кентерберийский университет в Крайстчерче включил модель мостов в области травы между старой физической БАН и Эрскин здания, жилье кафедры математики, статистики и информатики. [8] Реки заменяются невысокими кустарниками, а на центральном острове растет каменный тёро . Рочестерский технологический институт встроил головоломку в тротуар перед центром Джина Полиссени , хоккейной ареной, которая открылась в 2014 году. [9]
Смотрите также
- Эйлеров путь
- Пазл с пятью комнатами
- Глоссарий теории графов
- Гамильтонов путь
- Икозианская игра
- Вода, газ и электричество
Рекомендации
- ^ Эйлер, Леонард (1736). "Solutio problematis ad geometriam situs pertinentis". Комментарий. Акад. Sci. У. Петроп 8, 128–40.
- ↑ Шилдс, Роб (декабрь 2012 г.). «Культурная топология: семь мостов Кенигсбурга 1736 года». Теория, культура и общество . 29 (4–5): 43–57. DOI : 10.1177 / 0263276412451161 . Шилдс обсуждает социальную значимость участия Эйлера в решении этой популярной проблемы и ее значение в качестве примера (прото) топологического понимания, применимого к повседневной жизни.
- ^ Эйлера Архив , комментарий к публикации, и оригинальный текст на латыни.
- ^ Ньюман, MEJ Структура и функции сложных сетей (PDF) . Физический факультет Мичиганского университета.
- ^ Дж. Франклин, Аристотелевская реалистическая философия математики , Palgrave Macmillan, Basingstoke, 2014, стр. 48–9, 96, 215, 225; Дж. Франклин, Формальные науки открывают философский камень , Исследования по истории и философии науки 25 (4) (1994), стр. 513–533.
- ^ Тейлор, Питер (декабрь 2000 г.). «Что когда - либо случилось с теми , мосты?» . Австралийский математический фонд. Архивировано из оригинального 19 марта 2012 года . Проверено 11 ноября 2006 года .
- ^ Столлманн, Маттиас (июль 2006 г.). «Мосты 7/5 Кенигсберга / Калининграда» . Проверено 11 ноября 2006 года .
- ^ «О нас - Математика и статистика - Кентерберийский университет» . math.canterbury.ac.nz . Архивировано из оригинального 28 ноября 2016 года . Проверено 4 ноября 2010 года .
- ^ RIT Womens Hockey [@RITWHKY] (19 августа 2014 г.). «@OnlyAtRIT, мы кладем математическую задачу« 7 мостов »в цемент перед новой хоккейной ареной @PolisseniCenter #ROC» (твит) - через Twitter .
Внешние ссылки
- Калининград и Кёнигсберг мост Проблема в конвергенции
- Оригинальная публикация Эйлера (на латыни)
- Мосты Кенигсберга
- Как мосты Кенигсберга помогают понять мозг
- Проблема Кенигсбергских мостов Эйлера на математическом факультете колледжа Контра Коста
- Pregel - графический инструмент Google, названный в честь этой проблемы.
- [1] Современная проблема с графиком
Координаты : 54 ° 42′12 ″ с.ш., 20 ° 30′56 ″ в.д. / 54,70333 ° с. Ш. 20,51556 ° в. / 54,70333; 20,51556