Сім мостів Кеніґсберґа

Леонард Ейлер приїхав до Пруссії в 1741 році, у віці 34 років, де він прожив ​​до 1766, перш ніж повернутися до Санкт-Петербургу. Протягом цих років він працював в Прусській академії наук, де він зробив плідну кар'єру як дослідник[1]. Ейлер був сучасником з низкою інших відомих математиків і мислителів з ​​цього міста, таких як Іммануїл Кант, Йоганн Георг Гаманн і Крістіан Гольдбах, а Кеніґсберґ відігравав у той час роль важливого наукового центру.

Саме в цьому середовищі була сформульована проблема мостів Кеніґсберґа, що згодом набула поширення як тривіальна математична гра серед інтелігенції того часу.

Леонард Ейлер (1707–1783), відомий математик, який розв'язав цю задачу в 1736 році, що призвело до виникнення теорії графів. Портрет 1753 року.

По-перше, Ейлер осягнув, що вибір маршруту всередині кожної з ділянок суходолу (островів, або берегів ріки) не має значення. Важлива лише послідовність перетину мостів. Це дозволило йому переформулювати задачу в абстрактних термінах (які лягли в основу теорії графів), виключивши усі ознаки окрім списку ділянок суходолу і мостів, що сполучають їх. В сучасних термінах, він кожну з ділянок суходолу замінив на абстрактну «вершину», а кожен міст на абстрактне «ребро», яке слугувало лише для відображення факту сполучення пари вершин (ділянок суходолу) цим мостом. Отримана математична структура називається графом.

Через те, що важлива лише інформація про зв'язки, форма в якій граф зображений на малюнку не має значення, якщо при цьому не змінюється сам граф. Тільки існування (або відсутність) ребра між кожною парою вершин має значення. Наприклад, не має значення чи ребра намальовані як прямі або криві, або праворуч чи ліворуч від іншого зображений вузол.

Наступним спостереженням Ейлера було те, що (окрім кінцевих вершин прогулянки), коли хтось потрапляє до вершини через міст, обов'язково її покидає через міст. Інакше кажучи, впродовж кожного маршруту в графі, кількість входів в некінцеві вершини дорівнює кількості виходів з них. Тепер, якщо кожний міст пройдено рівно один раз, вірно наступне, для кожної ділянки суходолу (окрім початкової і кінцевої), кількість мостів до цієї ділянки парна (половина з них буде пройдена за напрямком до ділянки, а половина з ділянки). Однак всі чотири ділянки суходолу в початковій задачі мають непарну кількість мостів (одна 5, а інші по 3). Через те, що лише дві ділянки можуть слугувати як початкова і кінцева точки ймовірного маршруту, задача пройтися усіма мостами рівно по одному разу призводить до протиріччя.

→ →

Сучасною мовою, Ейлер показав, що можливість пройти через граф, пройшовши кожне ребро рівно один раз, залежить від степенів вершин. Степінь вершини це кількість ребер, що торкаються її. Аргументи Ейлера показали, що необхідною умовою прогулянки бажаного виду через граф є зв'язність графу і відсутність або наявність рівно двох вершин непарного степеня. Ця умова виявилась і достатньою, що стверджував Ейлер і пізніше довів Карл Гьєхолзер. Такий шлях називається ейлерів шлях. Далі, якщо присутні дві вершини непарного степеня, тоді Ейлерів шлях почнеться з однієї з них і закінчиться в іншій. Через наявність чотирьох вершин непарного степеня, історична задача не має розв'язку.

Іншим формулюванням задачі є запит на шлях, який проходить усіма ребрами і початкова та кінцева точки якого збігаються. Такий шлях називаєть ейлерів цикл. Такий шлях існує тоді і тільки тоді, коли граф зв'язний і не містить вершин непарного степеня. Всі ейлерові цикли є ейлеровими шляхами, але не навпаки.

Робота Ейлера була представлена Петербурзькій Академії 26 серпня 1735 і оприлюднена як Solutio problematis ad geometriam situs pertinentis в часописі Commentarii academiae scientiarum Petropolitanae у 1741.[2]

В історії математики, Ейлерів розв'язок задачі Кеніґсберзьких мостів вважається першою теоремою теорії графів (сума степенів всіх вершин завжди парна), задача розглядається як відгалуження комбінаторики. Комбінаторні задачі інших типів розглядались з античних часів.

Також, Ейлерове розуміння, що ключова інформація це кількість мостів і список їх кінців (на відміну від їх точного розташування) передбачило розвиток топології. Відмінність між справжньою розкладкою і схематичним зображенням це хороший приклад ідеї, що топологія не будується з жорстких форм об'єктів.

Класичне викладення задачі, подане вище, використовує непозначені вершини — такі, що вони всі однакові за винятком шляхів якими вони сполучені. Існують варіанти, в яких використовуються позначені вершини — кожній присвоєні унікальні ім'я та колір.

Північний берег річки зайнятий замком Синього Принца, південний — Червоного Принца. Східний берег це дім єпископа, або церква; і маленький острів в центрі це корчма.

Серед місцевих жителів було звичаєм, після кількох годин в корчмі, намагатися обійти мости, багато з них поверталися в корчму, щоб освіжитися для успішного завершення задачі. Однак, жодному так і не вдалося повторити подвиг до заходу сонця.

8: Синій Принц проаналізував міські мости з позиції теорії графів і дійшов висновку, що обійти їх всіх по одному разу неможливо. Він придумав хитрий план будівництва восьмого мосту так, щоб він міг звечора почати від свого замку, обійти всі мости і закінчити в корчмі, де похвалився б своєю перемогою. Звісно, він хотів, щоб Червоний Принц не міг повторити його подвиг від свого замку. Де Синій Принц має побудувати восьмий міст?

9: Червоний Принц, розгніваний гордієвим розв'язком свого брата, захотів збудувати міст, що дозволив би йому обійти всі мости від його замку і до корчми, щоб натерти брудом обличчя свого брата. Додатковою родзинкою помсти мало бути зникнення можливості обходу мостів за старим маршрутом у його брата. Де має побудувати дев'ятий міст Червоний Принц?

10: Єпископ дивився на це божевільне мостобудівництво із сум'яттям. Це створювало безлад в місті і, гірше, призводило до надмірного сп'яніння громадян. Він забажав побудувати десятий міст, який дозволив би всім мешканцям пройти мости і повернутися до власних ліжок. Де єпископ має побудував десятий міст?

Розв'язки

Розфарбований граф

8-й міст

Зведемо місто, як і раніше, до графу. Розфарбуємо кожну вершину. Як і в класичній задачі Ейлерового шляху не існує; фарбування не впливає на це. Всі чотири вершини мають непарну кількість ребер.

8: Ейлерів шлях можливий, якщо рівно дві або жодна з вершин не має непарної кількості ребер. Якщо ми маємо 2 вершини з непарною кількістю ребер, обхід має початися в одній з них і завершитися в другій. В задачі лише чотири вершини, тож розв'язок очевидний. Бажаний шлях має починатися в синій вершині і завершитися в помаранчевій. Тож нове ребро малюємо між іншими двома вершинами, зараз вони мають вже парну кількість ребер, що задовольняє нашим вимогам.

9-е ребро

10-е ребро

9: Встановити 9-й міст після 8-го теж легко. Потрібно дозволити Червоний замок і заборонити Синій як початкову точку; помаранчева точка залишається кінцевою і білу не чіпаємо. Щоб змінити парність червоної і синьої точок малюємо ребро між ними.

10: 10-й міст будується з трохи інших міркувань. Єпископ бажає надати кожному мешканцю можливість повернутися в початкову точку. Це вже ейлерів цикл, що вимагає парності степенів всіх вершин. Після побудови 9-го мосту, червона і помаранчева точки мають непарну степінь, тож саме їхня парність має бути змінена через будівництво мосту між ними.

8-й, 9-й, і 10-й мости

Медовий міст сьогодні

Місто Кеніґсберґ постало внаслідок злиття докупи трьох суверенних міст — Альтштадту, Кнайпгофу, Льобеніхту та кількох сільських поселень. Для комунікації між містами вже від початку XIV століття почалося будівництво мостів. Таким чином у Кеніґсберзі на середину XVIII століття постали сім мостів: Бакалійний, Зелений, Гноєвий, Кузенний, Дерев'яний, Високий і Медовий.

Гноєвий і Кузенний мости було зруйновано під час бомбардувань Другої світової війни. Зелений і Бакалійний були пізніше зруйновані і замінені на автомагістралі. Три інші мости залишились, хоча Дерев'яний внаслідок реконструкції 1904 року отримав новий вигляд, а Високий був зруйнований і збудований знову в 1938 році. І лише Медовий, наймолодший з мостів, залишився незмінним з часів Ейлера.

Станом на 2011 в Калінінграді 8 мостів: Двоярусний, Естакадний, Другий естакадний, Медовий, Дерев'яний, Високий, Ювілейний і Берлінський.

• Теорія графів
• Ейлерів шлях
• Ейлерів цикл
• Гамільтонів граф
• Задача про гамільтонів шлях
• Задача комівояжера

• Оригінальна публікація Ейлера (лат.)
• Задача мостів Кеніґсберґа (англ.)