Семь мостов Кенигсберга - Seven Bridges of Königsberg

Эта статья посвящена абстрактной проблеме. Историческую группу мостов в городе, когда-то известном как Кенигсберг, и тех из них, которые существуют до сих пор, см. § Современное состояние мостов.

Карта Кенигсберга времен Эйлера, показывающая фактическое расположение семи мостов с выделением реки Прегель и мостов.

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

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

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

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

явно неприемлемы.

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

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

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

Кенигсбергские мосты.png →7 bridges.svg →Кенигсберг graph.svg

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

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

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

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

Работа Эйлера была представлена ​​Петербургской Академии 26 августа 1735 г. и опубликована как Решение проблемы с геометрией situs pertinentis (Решение задачи по геометрии позиции) в журнале Commentarii academiae scientiarum Petropolitanae в 1741 г.[3] Он доступен в английском переводе в Мир математики к Джеймс Р. Ньюман.

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

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

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

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

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

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

Современная карта Калининграда. Расположение оставшихся мостов выделено зеленым цветом, а разрушенные - красным.

Два из семи оригинальных мостов не пережили бомбардировка Кенигсберга во время Второй мировой войны. Два других позже были снесены и заменены современным шоссе. Остались еще три моста, хотя только два из них относятся к временам Эйлера (один был перестроен в 1935 году).[6] Таким образом, по состоянию на 2000 г., пять мостов существуют на тех же участках, которые были задействованы в проблеме Эйлера.

С точки зрения теории графов, два узла теперь имеют степень 2, а два других - степень 3. Следовательно, теперь возможен эйлеров путь, но он должен начинаться на одном острове и заканчиваться на другом.[7]

В Кентерберийский университет в Крайстчерч включил модель мостов в лужайку между старой библиотекой физических наук и зданием Эрскин, в котором размещаются факультеты математики, статистики и информатики.[8] Реки заменены невысокими кустарниками, а центральный остров украшен камнем. tōrō. Рочестерский технологический институт встроил головоломку в тротуар перед Центр Джина Полиссени, хоккейная арена, открывшаяся в 2014 году.[9]

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

Смотрите также

Рекомендации

  1. ^ Эйлер, Леонард (1736). "Solutio problematis ad geometriam situs pertinentis". Комментарий. Акад. Sci. У. Петроп 8, 128–40.
  2. ^ Шилдс, Роб (декабрь 2012 г.). «Культурная топология: семь мостов Кенигсбурга 1736 года». Теория, культура и общество. 29 (4–5): 43–57. Дои:10.1177/0263276412451161. Шилдс обсуждает социальную значимость участия Эйлера в решении этой популярной проблемы и ее значение в качестве примера (прото) топологического понимания, применимого к повседневной жизни.
  3. ^ Эйлеров архив, комментарий к публикации и оригинальный текст на латыни.
  4. ^ Ньюман, М. Э. Дж. Структура и функции сложных сетей (PDF). Департамент физики Мичиганского университета.
  5. ^ Дж. Франклин, Аристотелевская реалистическая философия математики, Palgrave Macmillan, Basingstoke, 2014, стр. 48–9, 96, 215, 225; Дж. Франклин, Формальные науки открывают философский камень, Исследования по истории и философии науки 25 (4) (1994), стр. 513–533.
  6. ^ Тейлор, Питер (декабрь 2000 г.). "Что Когда-либо Что случилось с этими мостами? ". Австралийский математический фонд. Архивировано из оригинал 19 марта 2012 г.. Получено 11 ноября 2006.
  7. ^ Столлманн, Маттиас (июль 2006 г.). «Мосты 7/5 Кенигсберга / Калининграда». Получено 11 ноября 2006.
  8. ^ «О нас - Математика и статистика - Кентерберийский университет». math.canterbury.ac.nz. Архивировано из оригинал 28 ноября 2016 г.. Получено 4 ноября 2010.
  9. ^ RIT Womens Hockey [@RITWHKY] (19 августа 2014 г.). "@OnlyAtRIT, мы кладем математическую задачу 7 мостов в цемент перед новой хоккейной ареной @PolisseniCenter #ROC" (Твитнуть) - через Twitter.

внешняя ссылка

Координаты: 54 ° 42′12 ″ с.ш. 20 ° 30′56 ″ в.д. / 54,70333 ° с. Ш. 20,51556 ° в. / 54.70333; 20.51556