Семь мостов Кёнигсберга
Классическая задача теории графов

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

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

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

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

  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]

Сравнение графов головоломки «Семь мостов Кёнигсберга» (вверху) и «Пять комнат » (внизу). Числа обозначают количество ребер, соединенных с каждым узлом. Узлы с нечетным количеством ребер закрашены оранжевым цветом.

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

Ссылки

  1. ^ Эйлер, Леонард (1741). «Решение проблемы и относящаяся к месту геометрия». Commentarii Academiae Scientiarum Petropolitanae : 128–140 . Проверено 21 сентября 2024 г.Перевод на английский язык доступен по адресу https://www.cantab.net/users/michael.behrend/repubs/maze_maths/pages/euler.html
  2. ^ Шилдс, Роб (декабрь 2012 г.). «Культурная топология: семь мостов Кёнигсбурга 1736 года». Теория, культура и общество . 29 ( 4–5 ): 43–57 . doi :10.1177/0263276412451161. S2CID  146875675.Шилдс рассматривает социальную значимость работы Эйлера над этой популярной проблемой и ее значение как примера (прото)топологического понимания, применяемого в повседневной жизни.
  3. ↑ Архив Эйлера, комментарий к публикации и оригинальный текст на латыни.
  4. ^ Ньюман, MEJ Структура и функции сложных сетей (PDF) . Физический факультет Мичиганского университета.
  5. ^ Франклин, Джеймс (2014). Аристотелевская реалистическая философия математики. Basingstoke: Palgrave Macmillan. стр. 48-49, 96, 215, 225. ISBN 9781349486182.
  6. ^ Франклин, Джеймс (1994). «Формальные науки открывают философский камень» (PDF) . Исследования по истории и философии науки . 25 (4): 513– 533. Bibcode :1994SHPSA..25..513F. doi :10.1016/0039-3681(94)90045-0 . Получено 30 июня 2021 г. .
  7. ^ Räz, Tim (2018). «Эйлеров Кенигсберг: объяснительная сила математики». European Journal for Philosophy of Science . 8 (3): 331– 346. doi :10.1007/s13194-017-0189-x. S2CID  125194454. Получено 30 июня 2021 г.
  8. ^ Тейлор, Питер (декабрь 2000 г.). «Что случилось с этими мостами?». Australian Mathematics Trust. Архивировано из оригинала 19 марта 2012 г. Получено 11 ноября 2006 г.
  9. ^ Штальманн, Маттиас (июль 2006 г.). "7/5 мостов Кёнигсберга/Калининграда" . Получено 11 ноября 2006 г.
  10. ^ "About – Mathematics and Statistics – University of Canterbury". math.canterbury.ac.nz . Архивировано из оригинала 28 ноября 2016 года . Получено 4 ноября 2010 года .
  11. ^ RIT Womens Hockey [@RITWHKY] (19 августа 2014 г.). «@OnlyAtRIT мы помещаем математическую задачу о 7 мостах в цемент перед новой хоккейной ареной @PolisseniCenter #ROC» ( твит ) – через Twitter .
  12. ^ "Семь мостов Кёнигсберга". Georgia Tech . Получено 24 марта 2022 г.
  13. ^ Тило Гросс (2014, 1 июля) «Решение проблемы Бристольского моста» В: Сэм Парк (ред.) «50 видений математики», Oxford University Press , Оксфорд, ISBN 978-0198701811 
  14. ^ AllTrails, Прогулка по мостам Бристоля, Получено: 2023-11-22
  15. ^ Джефф Лукас и Тило Гросс (2019, 6 июня) «От Брайгстоу до Бристоля за 45 мостов», Bristol Books, Бристоль. ISBN 978-1909446182 . 
  16. ↑ Дэвид Кленси (2013, 1–3 марта) «42 перекрестка Бристоля — не слишком далекий мост для асов математики», Bristol Post , стр. 28–29.
  17. ↑ Памела Паркс (2015, 3 февраля) «Принимая вызов Бристольских мостов». Bristol24/7 , опубликовано онлайн, получено: 22.11.2023.
  18. ↑ Эндрю МакКуорри (2 октября 2019 г.) «Вот почему на следующей неделе люди будут платить 1 фунт стерлингов за проезд по мостам в Бристоле», Bristol Post , стр. 22–23.
На Викискладе есть медиафайлы по теме « Семь мостов Кёнигсберга» .
  • Калининград и проблема Кенигсбергского моста на Convergence
  • Оригинальная публикация Эйлера (на латыни)
  • Мосты Кёнигсберга
  • Как мосты Кенигсберга помогают понять мозг
  • Задача Эйлера о мостах Кенигсберга на кафедре математики в колледже Контра Коста
  • Pregel – графический инструмент Google, названный в честь этой проблемы.
  • [1] Современная проблема графа
  • Ли, Венда. Задача о Кенигсбергском мосте и теорема о дружбе (Формальное доказательство развития в Isabelle/HOL, Архив формальных доказательств)
Взято с "https://en.wikipedia.org/w/index.php?title=Семь_мостов_Кёнигсберга&oldid=1269420146"