Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Сім мостів Кеніґсберґа — видатна історична задача з математики. Доведення неможливості її розв'язання Леонардом Ейлером в 1735 призвело до створення теорії графів і передувало ідеї топології.
Місто Кеніґсберґ в Пруссії (нині Калінінград у Росії) було на берегах річки Преголя, рукави якої ділили місто на чотири частини, в тому числі й два острови — Кнайпгоф і Ломзе, що поєднувалися сімома мостами: Бакалійним, Зеленим, Гноєвим, Кузенним, Дерев'яним, Високим і Медовим.
Необхідно було знайти такий маршрут через місто, щоб пройти всі сім мостів і кожним мостом пройти рівно один раз. На острів не можна було потрапити інакше як через міст, і кожен з мостів мав бути пройденим за один раз (тобто не можна було пройти на середину мосту і повернутися назад, а потім з іншого берега пройти другу половину). Ейлер довів, що розв'язку не існує.
Контекстуалізація проблеми
Леонард Ейлер приїхав до Пруссії в 1741 році, у віці 34 років, де він прожив до 1766, перш ніж повернутися до Санкт-Петербургу. Протягом цих років він працював в Прусській академії наук, де він зробив плідну кар'єру як дослідник. Ейлер був сучасником з низкою інших відомих математиків і мислителів з цього міста, таких як Іммануїл Кант, і Крістіан Гольдбах, а Кеніґсберґ відігравав у той час роль важливого наукового центру.
Саме в цьому середовищі була сформульована проблема мостів Кеніґсберґа, що згодом набула поширення як тривіальна математична гра серед інтелігенції того часу.
Розбір Ейлера
По-перше, Ейлер осягнув, що вибір маршруту всередині кожної з ділянок суходолу (островів, або берегів ріки) не має значення. Важлива лише послідовність перетину мостів. Це дозволило йому переформулювати задачу в абстрактних термінах (які лягли в основу теорії графів), виключивши усі ознаки окрім списку ділянок суходолу і мостів, що сполучають їх. В сучасних термінах, він кожну з ділянок суходолу замінив на абстрактну «вершину», а кожен міст на абстрактне «ребро», яке слугувало лише для відображення факту сполучення пари вершин (ділянок суходолу) цим мостом. Отримана математична структура називається графом.
Через те, що важлива лише інформація про зв'язки, форма в якій граф зображений на малюнку не має значення, якщо при цьому не змінюється сам граф. Тільки існування (або відсутність) ребра між кожною парою вершин має значення. Наприклад, не має значення чи ребра намальовані як прямі або криві, або праворуч чи ліворуч від іншого зображений вузол.
Наступним спостереженням Ейлера було те, що (окрім кінцевих вершин прогулянки), коли хтось потрапляє до вершини через міст, обов'язково її покидає через міст. Інакше кажучи, впродовж кожного маршруту в графі, кількість входів в некінцеві вершини дорівнює кількості виходів з них. Тепер, якщо кожний міст пройдено рівно один раз, вірно наступне, для кожної ділянки суходолу (окрім початкової і кінцевої), кількість мостів до цієї ділянки парна (половина з них буде пройдена за напрямком до ділянки, а половина з ділянки). Однак всі чотири ділянки суходолу в початковій задачі мають непарну кількість мостів (одна 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-го мосту, червона і помаранчева точки мають непарну степінь, тож саме їхня парність має бути змінена через будівництво мосту між ними.
Сучасний стан мостів
Місто Кеніґсберґ постало внаслідок злиття докупи трьох суверенних міст — Альтштадту, Кнайпгофу, Льобеніхту та кількох сільських поселень. Для комунікації між містами вже від початку XIV століття почалося будівництво мостів. Таким чином у Кеніґсберзі на середину XVIII століття постали сім мостів: Бакалійний, Зелений, Гноєвий, Кузенний, Дерев'яний, Високий і Медовий.
Гноєвий і Кузенний мости було зруйновано під час бомбардувань Другої світової війни. Зелений і Бакалійний були пізніше зруйновані і замінені на автомагістралі. Три інші мости залишились, хоча Дерев'яний внаслідок реконструкції 1904 року отримав новий вигляд, а Високий був зруйнований і збудований знову в 1938 році. І лише Медовий, наймолодший з мостів, залишився незмінним з часів Ейлера.
Станом на 2011 в Калінінграді 8 мостів: Двоярусний, Естакадний, Другий естакадний, Медовий, Дерев'яний, Високий, Ювілейний і Берлінський.
Див. також
Примітки
- Dunham William. Euler: The Master of Us All. 1999. pp. xxiv–xxv. (англ.)
- The Euler Archive [ 11 червня 2015 у Wayback Machine.], коментарі до публікації та початковий текст на латині.
Посилання
| Вікісховище має мультимедійні дані за темою: Сім мостів Кеніґсберґа |
- Оригінальна публікація Ейлера [ 20 травня 2011 у Wayback Machine.] (лат.)
- (англ.)
Координати: 54°42′12″ пн. ш. 20°30′56″ сх. д. / 54.70333° пн. ш. 20.51556° сх. д.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Sim mostiv Kenigsberga vidatna istorichna zadacha z matematiki Dovedennya nemozhlivosti yiyi rozv yazannya Leonardom Ejlerom v 1735 prizvelo do stvorennya teoriyi grafiv i pereduvalo ideyi topologiyi Mapa Kenigsberga v chasi Ejlera iz zobrazhennyam roztashuvannya simoh mostiv pidsvicheni mosti i richka Pregolya Misto Kenigsberg v Prussiyi nini Kaliningrad u Rosiyi bulo na beregah richki Pregolya rukavi yakoyi dilili misto na chotiri chastini v tomu chisli j dva ostrovi Knajpgof i Lomze sho poyednuvalisya simoma mostami Bakalijnim Zelenim Gnoyevim Kuzennim Derev yanim Visokim i Medovim Neobhidno bulo znajti takij marshrut cherez misto shob projti vsi sim mostiv i kozhnim mostom projti rivno odin raz Na ostriv ne mozhna bulo potrapiti inakshe yak cherez mist i kozhen z mostiv mav buti projdenim za odin raz tobto ne mozhna bulo projti na seredinu mostu i povernutisya nazad a potim z inshogo berega projti drugu polovinu Ejler doviv sho rozv yazku ne isnuye Kontekstualizaciya problemiLeonard Ejler priyihav do Prussiyi v 1741 roci u vici 34 rokiv de vin prozhiv do 1766 persh nizh povernutisya do Sankt Peterburgu Protyagom cih rokiv vin pracyuvav v Prusskij akademiyi nauk de vin zrobiv plidnu kar yeru yak doslidnik Ejler buv suchasnikom z nizkoyu inshih vidomih matematikiv i misliteliv z cogo mista takih yak Immanuyil Kant i Kristian Goldbah a Kenigsberg vidigravav u toj chas rol vazhlivogo naukovogo centru Same v comu seredovishi bula sformulovana problema mostiv Kenigsberga sho zgodom nabula poshirennya yak trivialna matematichna gra sered inteligenciyi togo chasu Rozbir EjleraLeonard Ejler 1707 1783 vidomij matematik yakij rozv yazav cyu zadachu v 1736 roci sho prizvelo do viniknennya teoriyi grafiv Portret 1753 roku Po pershe Ejler osyagnuv sho vibir marshrutu vseredini kozhnoyi z dilyanok suhodolu ostroviv abo beregiv riki ne maye znachennya Vazhliva lishe poslidovnist peretinu mostiv Ce dozvolilo jomu pereformulyuvati zadachu v abstraktnih terminah yaki lyagli v osnovu teoriyi grafiv viklyuchivshi usi oznaki okrim spisku dilyanok suhodolu i mostiv sho spoluchayut yih V suchasnih terminah vin kozhnu z dilyanok suhodolu zaminiv na abstraktnu vershinu a kozhen mist na abstraktne rebro yake sluguvalo lishe dlya vidobrazhennya faktu spoluchennya pari vershin dilyanok suhodolu cim mostom Otrimana matematichna struktura nazivayetsya grafom Cherez te sho vazhliva lishe informaciya pro zv yazki forma v yakij graf zobrazhenij na malyunku ne maye znachennya yaksho pri comu ne zminyuyetsya sam graf Tilki isnuvannya abo vidsutnist rebra mizh kozhnoyu paroyu vershin maye znachennya Napriklad ne maye znachennya chi rebra namalovani yak pryami abo krivi abo pravoruch chi livoruch vid inshogo zobrazhenij vuzol Nastupnim sposterezhennyam Ejlera bulo te sho okrim kincevih vershin progulyanki koli htos potraplyaye do vershini cherez mist obov yazkovo yiyi pokidaye cherez mist Inakshe kazhuchi vprodovzh kozhnogo marshrutu v grafi kilkist vhodiv v nekincevi vershini dorivnyuye kilkosti vihodiv z nih Teper yaksho kozhnij mist projdeno rivno odin raz virno nastupne dlya kozhnoyi dilyanki suhodolu okrim pochatkovoyi i kincevoyi kilkist mostiv do ciyeyi dilyanki parna polovina z nih bude projdena za napryamkom do dilyanki a polovina z dilyanki Odnak vsi chotiri dilyanki suhodolu v pochatkovij zadachi mayut neparnu kilkist mostiv odna 5 a inshi po 3 Cherez te sho lishe dvi dilyanki mozhut sluguvati yak pochatkova i kinceva tochki jmovirnogo marshrutu zadacha projtisya usima mostami rivno po odnomu razu prizvodit do protirichchya Suchasnoyu movoyu Ejler pokazav sho mozhlivist projti cherez graf projshovshi kozhne rebro rivno odin raz zalezhit vid stepeniv vershin Stepin vershini ce kilkist reber sho torkayutsya yiyi Argumenti Ejlera pokazali sho neobhidnoyu umovoyu progulyanki bazhanogo vidu cherez graf ye zv yaznist grafu i vidsutnist abo nayavnist rivno dvoh vershin neparnogo stepenya Cya umova viyavilas i dostatnoyu sho stverdzhuvav Ejler i piznishe doviv Karl Gyeholzer Takij shlyah nazivayetsya ejleriv shlyah Dali yaksho prisutni dvi vershini neparnogo stepenya todi Ejleriv shlyah pochnetsya z odniyeyi z nih i zakinchitsya v inshij Cherez nayavnist chotiroh vershin neparnogo stepenya istorichna zadacha ne maye rozv yazku Inshim formulyuvannyam zadachi ye zapit na shlyah yakij prohodit usima rebrami i pochatkova ta kinceva tochki yakogo zbigayutsya Takij shlyah nazivayetsya ejleriv cikl Takij shlyah isnuye todi i tilki todi koli graf zv yaznij i ne mistit vershin neparnogo stepenya Vsi ejlerovi cikli ye ejlerovimi shlyahami ale ne navpaki Robota Ejlera bula predstavlena Peterburzkij Akademiyi 26 serpnya 1735 i oprilyudnena yak Solutio problematis ad geometriam situs pertinentis v chasopisi Commentarii academiae scientiarum Petropolitanae u 1741 Znachennya v istoriyi matematikiV istoriyi matematiki Ejleriv rozv yazok zadachi Kenigsberzkih mostiv vvazhayetsya pershoyu teoremoyu teoriyi grafiv suma stepeniv vsih vershin zavzhdi parna zadacha rozglyadayetsya yak vidgaluzhennya kombinatoriki Kombinatorni zadachi inshih tipiv rozglyadalis z antichnih chasiv Takozh Ejlerove rozuminnya sho klyuchova informaciya ce kilkist mostiv i spisok yih kinciv na vidminu vid yih tochnogo roztashuvannya peredbachilo rozvitok topologiyi Vidminnist mizh spravzhnoyu rozkladkoyu i shematichnim zobrazhennyam ce horoshij priklad ideyi sho topologiya ne buduyetsya z zhorstkih form ob yektiv VariaciyiKlasichne vikladennya zadachi podane vishe vikoristovuye nepoznacheni vershini taki sho voni vsi odnakovi za vinyatkom shlyahiv yakimi voni spolucheni Isnuyut varianti v yakih vikoristovuyutsya poznacheni vershini kozhnij prisvoyeni unikalni im ya ta kolir Pivnichnij bereg richki zajnyatij zamkom Sinogo Princa pivdennij Chervonogo Princa Shidnij bereg ce dim yepiskopa abo cerkva i malenkij ostriv v centri ce korchma Sered miscevih zhiteliv bulo zvichayem pislya kilkoh godin v korchmi namagatisya obijti mosti bagato z nih povertalisya v korchmu shob osvizhitisya dlya uspishnogo zavershennya zadachi Odnak zhodnomu tak i ne vdalosya povtoriti podvig do zahodu soncya 8 Sinij Princ proanalizuvav miski mosti z poziciyi teoriyi grafiv i dijshov visnovku sho obijti yih vsih po odnomu razu nemozhlivo Vin pridumav hitrij plan budivnictva vosmogo mostu tak shob vin mig zvechora pochati vid svogo zamku obijti vsi mosti i zakinchiti v korchmi de pohvalivsya b svoyeyu peremogoyu Zvisno vin hotiv shob Chervonij Princ ne mig povtoriti jogo podvig vid svogo zamku De Sinij Princ maye pobuduvati vosmij mist 9 Chervonij Princ rozgnivanij gordiyevim rozv yazkom svogo brata zahotiv zbuduvati mist sho dozvoliv bi jomu obijti vsi mosti vid jogo zamku i do korchmi shob naterti brudom oblichchya svogo brata Dodatkovoyu rodzinkoyu pomsti malo buti zniknennya mozhlivosti obhodu mostiv za starim marshrutom u jogo brata De maye pobuduvati dev yatij mist Chervonij Princ 10 Yepiskop divivsya na ce bozhevilne mostobudivnictvo iz sum yattyam Ce stvoryuvalo bezlad v misti i girshe prizvodilo do nadmirnogo sp yaninnya gromadyan Vin zabazhav pobuduvati desyatij mist yakij dozvoliv bi vsim meshkancyam projti mosti i povernutisya do vlasnih lizhok De yepiskop maye pobuduvav desyatij mist Rozv yazki Rozfarbovanij graf 8 j mist Zvedemo misto yak i ranishe do grafu Rozfarbuyemo kozhnu vershinu Yak i v klasichnij zadachi Ejlerovogo shlyahu ne isnuye farbuvannya ne vplivaye na ce Vsi chotiri vershini mayut neparnu kilkist reber 8 Ejleriv shlyah mozhlivij yaksho rivno dvi abo zhodna z vershin ne maye neparnoyi kilkosti reber Yaksho mi mayemo 2 vershini z neparnoyu kilkistyu reber obhid maye pochatisya v odnij z nih i zavershitisya v drugij V zadachi lishe chotiri vershini tozh rozv yazok ochevidnij Bazhanij shlyah maye pochinatisya v sinij vershini i zavershitisya v pomaranchevij Tozh nove rebro malyuyemo mizh inshimi dvoma vershinami zaraz voni mayut vzhe parnu kilkist reber sho zadovolnyaye nashim vimogam 9 e rebro 10 e rebro 9 Vstanoviti 9 j mist pislya 8 go tezh legko Potribno dozvoliti Chervonij zamok i zaboroniti Sinij yak pochatkovu tochku pomarancheva tochka zalishayetsya kincevoyu i bilu ne chipayemo Shob zminiti parnist chervonoyi i sinoyi tochok malyuyemo rebro mizh nimi 10 10 j mist buduyetsya z trohi inshih mirkuvan Yepiskop bazhaye nadati kozhnomu meshkancyu mozhlivist povernutisya v pochatkovu tochku Ce vzhe ejleriv cikl sho vimagaye parnosti stepeniv vsih vershin Pislya pobudovi 9 go mostu chervona i pomarancheva tochki mayut neparnu stepin tozh same yihnya parnist maye buti zminena cherez budivnictvo mostu mizh nimi 8 j 9 j i 10 j mostiSuchasnij stan mostivMedovij mist sogodni Dokladnishe Misto Kenigsberg postalo vnaslidok zlittya dokupi troh suverennih mist Altshtadtu Knajpgofu Lobenihtu ta kilkoh silskih poselen Dlya komunikaciyi mizh mistami vzhe vid pochatku XIV stolittya pochalosya budivnictvo mostiv Takim chinom u Kenigsberzi na seredinu XVIII stolittya postali sim mostiv Bakalijnij Zelenij Gnoyevij Kuzennij Derev yanij Visokij i Medovij Gnoyevij i Kuzennij mosti bulo zrujnovano pid chas bombarduvan Drugoyi svitovoyi vijni Zelenij i Bakalijnij buli piznishe zrujnovani i zamineni na avtomagistrali Tri inshi mosti zalishilis hocha Derev yanij vnaslidok rekonstrukciyi 1904 roku otrimav novij viglyad a Visokij buv zrujnovanij i zbudovanij znovu v 1938 roci I lishe Medovij najmolodshij z mostiv zalishivsya nezminnim z chasiv Ejlera Stanom na 2011 v Kaliningradi 8 mostiv Dvoyarusnij Estakadnij Drugij estakadnij Medovij Derev yanij Visokij Yuvilejnij i Berlinskij Div takozhTeoriya grafiv Ejleriv shlyah Ejleriv cikl Gamiltoniv graf Zadacha pro gamiltoniv shlyah Zadacha komivoyazheraPrimitkiDunham William Euler The Master of Us All 1999 pp xxiv xxv angl The Euler Archive 11 chervnya 2015 u Wayback Machine komentari do publikaciyi ta pochatkovij tekst na latini PosilannyaVikishovishe maye multimedijni dani za temoyu Sim mostiv Kenigsberga Originalna publikaciya Ejlera 20 travnya 2011 u Wayback Machine lat angl Koordinati 54 42 12 pn sh 20 30 56 sh d 54 70333 pn sh 20 51556 sh d 54 70333 20 51556