Кенігсберг
Наша історія починається у
18-му столітті, в химерному місті Кенігсберзі, Пруссія на березі річки Преголя.
У 1254 році тевтонські лицарі заснували місто Кенігсберг під керівництвом
чеського короля Оттокара II після другого хрестового походу проти прусів. У
середні віки Кенігсберг став дуже важливим містом і торговим центром з його
місцем розташування стратегічно розташований на річці. Твори з вісімнадцятого
століття показують Кенігсберг як процвітаюче місто, де флотилії кораблів
заповнюють Преголя, і їх торгівля пропонує комфортний спосіб життя як місцевих
торговців і їхніх родин. Здорова економіка дозволила жителям міста побудувати
сім мостів через річку, більшість з яких з'єднана з островом Кнайпхоф; їх
розташування можна побачити на доданому малюнку.
Сім мостів були названі Бакалійним, Зеленим, Гноєвим, Кузенним, Дерев'яним, Високим і Медовим.
Згідно з переказами, жителі Кенігсберга мали звичай у неділю по обіді ходити
навколо свого прекрасного міста. Під час прогулянки жителі міста вирішили
створити гру для себе, її мета полягає в тому, щоб винайти спосіб, в якому вони
могли б ходити по місту, перетинаючи кожен з семи мостів тільки один раз.
Навіть якщо жоден з громадян Кенігсберга не міг придумати маршрут, який
дозволив би їм перетнути кожен з мостів тільки один раз, до цих пір вони не
могли довести, що це було неможливо. На щастя для них, Кенігсберг був не надто
далеко від Санкт-Петербурга, де мешкав відомий математик Леонард Ейлер.
Розбір Ейлера
По-перше, Ейлер осягнув, що вибір маршруту всередині кожної з ділянок суходолу (островів, або берегів ріки) не має значення. Важлива лише послідовність перетину мостів. Це дозволило йому переформулювати задачу в абстрактних термінах (які лягли в основу теорії графів), виключивши усі ознаки окрім списку ділянок суходолу і мостів, що сполучають їх. В сучасних термінах, він кожну з ділянок суходолу замінив на абстрактну «вершину», а кожен міст на абстрактне «ребро», яке слугувало лише для відображення факту сполучення пари вершин (ділянок суходолу) цим мостом. Отримана математична структура називається графом.
Через те, що важлива лише інформація про зв'язки, форма в якій граф зображений на малюнку не має значення, якщо при цьому не змінюється сам граф. Тільки існування (або відсутність) ребра між кожною парою вершин має значення. Наприклад, не має значення чи ребра намальовані як прямі або криві, або праворуч чи ліворуч від іншого зображений вузол.
Наступним спостереженням Ейлера було те, що (окрім кінцевих вершин прогулянки), коли хтось потрапляє до вершини через міст, обов'язково її покидає через міст. Інакше кажучи, впродовж кожного маршруту в графі, кількість входів в некінцеві вершини дорівнює кількості виходів з них. Тепер, якщо кожний міст пройден рівно один раз, вірно наступне, для кожної ділянки суходолу (окрім початкової і кінцевої), кількість мостів до цієї ділянки парна (половина з них буде пройдена за напрямком до ділянки, а половина з ділянки). Однак всі чотири ділянки суходолу в початковій задачі мають непарну кількість мостів (одна 5, а інші по 3). Через те, що лише дві ділянки можуть слугувати як початкова і кінцева точки ймовірного маршруту, задача пройтися усіма мостами рівно по одному разу призводить до протиріччя.
→ 
→ 
Сучасною мовою, Ейлер показав, що можливість пройти через граф, пройшовши кожне ребро рівно один раз, залежить від степенів вершин. Степінь вершини це кількість ребер, що торкаються її. Аргументи Ейлера показали, що необхідною умовою прогулянки бажаного виду через граф є зв'язність графа і відсутність або наявність рівно двох вершин непарного степеня. Ця умова виявилась і достатньою, що стверджував Ейлер і пізніше довів Карл Гьєхолзер. Такий шлях називається ейлерів шлях. Далі, якщо присутні дві вершини непарного степеня, тоді Ейлерів шлях почнеться з однієї з них і закінчиться в іншій. Через наявність чотирьох вершин непарного степеня, історична задача не має розв'язку.
Іншим формулюванням задачі є запит на шлях, який проходить усіма ребрами і початкова та кінцева точки якого збігаються. Такий шлях називаєть ейлерів цикл. Такий шлях існує тоді і тільки тоді, коли граф зв'язний і не містить вершин непарного степеня. Всі ейлерові цикли є ейлеровими шляхами, але не навпаки.
Робота Ейлера була представлена Петербурзькій Академії 26 серпня 1735 і оприлюднена як Solutio problematis ad geometriam situs pertinentis в часописі Commentarii academiae scientiarum Petropolitanae у 1741.
Значення в історії математики
В історії математики, Ейлерів розв'язок задачі Кеніґсберзьких мостів вважається першою теоремою теорії графів (сума степенів всіх вершин завжди парна), задача розглядається як відгалуження комбінаторики. Комбінаторні задачі інших типів розглядались з античних часів.
Також, Ейлерове розуміння, що ключова інформація це кількість мостів і список їх кінців (на відміну від їх точного розташування) передбачило розвиток топології. Відмінність між справжньою розкладкою і схематичним зображенням це хороший приклад ідеї, що топологія не будується з жорстких форм об'єктів.
Варіації
Класичне викладення задачі, подане вище, використовує непозначені вершини — такі, що вони всі однакові за винятком шляхів якими вони сполучені. Існують варіанти, в яких використовуються позначені вершини — кожній присвоєні унікальні ім'я та колір.
Північний берег річки зайнятий замком Синього Принца, південний — Червоного Принца. Східний берег це дім єпископа, або церква; і маленький острів в центрі це корчма.
Серед місцевих жителів було звичаєм, після кількох годин в корчмі, намагатися обійти мости, багато з них поверталися в корчму, щоб освіжитися для успішного завершення задачі. Однак, жодному так і не вдалося повторити подвиг до заходу сонця.
8: Синій Принц проаналізував міські мости з позиції теорії графів і дійшов висновку, що обійти їх всіх по одному разу неможливо. Він придумав хитрий план будівництва восьмого мосту так, щоб він міг звечора почати від свого замку, обійти всі мости і закінчити в корчмі, де похвалився б своєю перемогою. Звісно, він хотів, щоб Червоний Принц не міг повторити його подвиг від свого замку. Де Синій Принц має побудувати восьмий міст?
9: Червоний Принц, розгніваний гордієвим розв'язком свого брата, захотів збудувати міст, що дозволив би йому обійти всі мости від його замку і до корчми, щоб натерти брудом обличчя свого брата. Додатковою родзинкою помсти мало бути зникнення можливості обходу мостів за старим маршрутом у його брата. Де має побудувати дев'ятий міст Червоний Принц?
10: Єпископ дивився на це божевільне мостобудівництво із сум'яттям. Це створювало безлад в місті і, гірше, призводило до надмірного сп'яніння громадян. Він забажав побудувати десятий міст, який дозволив би всіммешканцям пройти мости і повернутися до власних ліжок. Де єпископ має побудував десятий міст?
Розв'язки
Зведемо місто, як і раніше, до графа. Розфарбуємо кожну вершину. Як і в класичній задачі Ейлерового шляху не існує; фарбування не впливає на це. Всі чотири вершини мають непарну кількість ребер.
8: Ейлерів шлях можливий, якщо рівно дві або жодна з вершин не має непарної кількості ребер. Якщо ми маємо 2 вершини з непарною кількістю ребер, обхід має початися в одній з них і завершитися в другій. В задачі лише чотири вершини, тож розв'язок очевидний. Бажаний шлях має починатися в синій вершині і завершитися в помаранчевій. Тож нове ребро малюємо між іншими двома вершинами, зараз вони мають вже парну кількість ребер, що задовольняє нашим вимогам.
9: Встановити 9-й міст після 8-го теж легко. Потрібно дозволити Червоний замок і заборонити Синій як початкову точку; помаранчева точка залишається кінцевою і білу не чіпаємо. Щоб змінити парність червоної і синьої точок малюємо ребро між ними.
10: 10-й міст будується з трохи інших міркувань. Єпископ бажає надати кожному мешканцю можливість повернутися в початкову точку. Це вже ейлерів цикл, що вимагає парності степенів всіх вершин. Після побудови 9-го мосту, червона і помаранчева точки мають непарну степінь, тож саме їхня парність має бути змінена через будівництво мосту між ними.
Матеріал з Вікіпедії — вільної енциклопедії.