Prokleté mosty města Königsbergu

21. listopadu 2013 v 20:20 | Mlok |  Matematika
Kdybych mohl, přestal bych. Zastavil bych. Ale nemůžu, nesmím, nechci. Ta věc mě hryže v mozku už od chvíle, kdy jsem vstoupil na půdu tohohle proklatého města a uviděl ty mosty, od chvíle kdy mě napadla za hrůzná myšlenka. A já vím, že neodjedu, že nezastavím, dokud tu hádanku nevyřeším. Je to tak frustrující tak děsivé. Sedm mostů! Těch sedm mostů! Musí být přeci způsob, musí být cesta... Musí být v lidských silách všechny je přejít najednou, aniž bych po jednom z nich prošel dvakrát! Po kolikáté už to jen zkouším? Vždy se ocitnu ve slepé uličce, vždy na místě, odkud už volný most nevede. Jen sebrat síly a.... začít znovu. Pokračovat v cestě? Bože, už nemám sílu.
Ale já se nevzdám. Já to dokážu.
Cítím, že mě to posedlo, naprosto ovládlo. Už necítím chodidla, každý krok mě stojí tolik dechu. Ale já se přece nevzdám.


Když tě dnes ráno, kousek od nábřeží našli, už jsi nedýchal. Tři dny a tři noci v kuse jsi prochodil po městě, bez jídla a odpočinku, nejdřív s botami a pak i bez nich. Kdybych jen mohla pochopit pro co, pro co jsi jen Achime zemřel? Jaký démon tě posedl, že jsi s takovým šílenstvím v duši promrhal svůj mladý život? Nikdy jsi takový nebyl, tohle město tě teprve změnilo. Když jsem tě viděla naposledy před smrtí, to jsi odcházel z domu, sedm mostů že prý přejít musíš, jinak že nenajdeš klid v duši. A dnes? Zaschlá krev na tvých rozedraných chodidlech byla svědkem tvého nešťastného osudu, tělo zkřehklé chladem a zesláblé hladem a vyčerpáním. Tři dny a tři noci, a přece jsi nenašel odpověď. Řekni Achime, měla jsem tě zastavit?
Ne. Zvláštním způsobem ti rozumím.
Těch sedm mostů! Jak geniální, jak prosté. Stačí je přejít, nemám pravdu Achime? Udělám to, udělám to pro tebe. Dokážu že jsi měl pravdu, dokážu že je to možné. Nezemřel jsi nadarmo, já budu pokračovat, budu pokračovat!

Když tě dnes ráno, kousek od nábřeží našli, už jsi nedýchala. Tři dny a tři noci v kuse jsi prochodila po městě, bez jídla a odpočinku, nejdřív s botami a pak i bez nich. Pro co jsi to jen zemřela, Christie? Měl jsem tě snad zastavit?
Ne. Zvláštním způsobem tě chápu...


Je možné všechny mosty města Königsbergu přejít tak, aby ten, kdo se o to pokouší, vstoupil na každý most pouze jednou?


Omluvte můj krátký psycho úvod, takhle nějak si ale prostě předstvuju že tento slavný matematický problém vznikl. Königsberg, nebo také Kaliningrad leží v Rusku, na severozápadě Evropy (v malé části Ruska mezi Polskem a Litvou). Sedm mostů města Königsbergu, jak je tento problém nazýván, vznikl na základě reálné situace z tohoto města. Řeka Pregola tvoří v tomto městě zajímavou situaci, jak je vidět na tomto historickém obrázku z doby, kdy byl problém přibližně definován:


Dnes už víme, že problém Sedmi mostů města Königsbergu je neřešitelný, tedy že není možné všechny mosty přejít tímto způsobem. Absolutně to vyvrátil a hlavně doložil už Leonhard Edler (na obrázku nahoře) v roce 1736 pomocí své teorie grafů. Pojďme se tedy trochu podrobněji podívat na to, jak to vlatně z matematického hlediska funguje. Vážení, představuju vám Eulerovský tah!

Kdybysme si mapu zjednodušili so jednoduchého schématu, vypadalo by to takhle:


Vcelku máte asi tak tři možnosti, jak problém řešit: a) použijete strategii jako naši milí Achim, Christie a mnoho jejich následovníků, což bych vám ale nedoporučovala..., b) načmáráte si schéma a budete se snažit na něj matlat co nejvíc možností, což je ale dost zdlouhavé a nespolehlivé vzhledem k přehlednosti, c) použijete Eulerovu teorii grafů a pokusíte se určit, jestli se jedná o Eulerovský tah či nikoli!

Ano, ano, jistě jste si vybrali možnost c! Takže teda, co to je Eulerovský tah? Zjednodušeně jde o schopnost grafu, být nakreslen jedním tahem. To platí třeba i pro klasický domeček jedním tahem a podobné věci. Například ten domeček je tak obecně definován jako Eulerovský graf (graf se schopností elerovského tahu). Je to tedy jednoduché: je-li graf eulerovský - lze nakreslit jedním tahem.

Předně jde teda o to, nějakým způsobem z těch mostů udělat graf. Je důležité uvědomit si, že záleží hlavně na tom, jak jsou mezi sebou rozložené jednotlivé pevniny a mosty, přičemž je obzvlášť důležité, kolik mostů spojuje jednotlivé pevniny. S pomocí toho lze ze schématu nejdřív zkonstruovat graf:


Jak vidíte, naznačené jsou pouze pevniny (hnědé tečky - uzly) a mosty (černé čáry - spojnice) mezi nimi. Teď už stačí jen určit, zda je graf eulerovský nebo ne. I to je docela jednoduché. Euler totiž určil, že lze aplikovat eulerovský tah jen v případě, kdy z žádného nebo dvou z uzlů vychází lichý počet spojnic. Je celkem jednoduché spočítat, že v případě našeho milého Königsbergu tomu tak není, z jednotlivých uzlů nám vychází 3, 5, 3 a 3 spojnic. To znamená, že se nejedná o eulerovský graf, tedy je nemožné přejít všechny mosty a zároveň každý překročit jen jednou.

Pro zajímavost ještě pohled na dnešní Königsberg. Z původních sedmi mostů se bohužel dochovaly pouze dva, některé byly dostavěny a proto už dnes problém bohužel v reálu nelze vidět, Eulerovský tah už zde má naprosto jinou formu - s dnešní konstelací mostů je problém řešitelný, tedy opravdu je možné všechny mosty přejít v kuse.


Může se to zdát pomatené, malicherné nebo nedůležité. Ale věci jako je tahle pomáhaly tvořit matematiku takovou jak ji známe a milujeme (aspoň já) dnes. Lidé vždycky chtěli najít odpovědi na otázky, které nemohli zodpovědět. Některé problémy byly vyřešeny jako tento, podloženy krásnou a čistou matematikou, poodkryly nové oblasti té krásné vědy, jiné problémy známé již po staletí vyřešeny nebyly a možná ani nikdy nebudou. A to je krásné.
 


Komentáře

1 Natas Natas | Web | 21. listopadu 2013 v 20:43 | Reagovat

Jejda, neslyšela jsem až dosud. Lámala jsem si s tím hlavu, začala bláznit, nemožné, nemožné a zase nemožné. Pěkný článek.

2 verca01234 verca01234 | E-mail | 21. listopadu 2013 v 21:40 | Reagovat

Je to řešitelné prostě to přeplaveš, ne? A nebo to přepluješ,přejdeš jinudy, domyslíš si mapu a máš po problému.

3 Mlok Mlok | Web | 21. listopadu 2013 v 21:48 | Reagovat

[Smazaný komentář] Hm, až na to že v Rusku je taková kosa, že bch nedoporučovala se tam koupat, ledaže by bylo v zájmu tý akce mít zmrzlej mozek.

4 Miloš Miloš | Web | 21. listopadu 2013 v 22:28 | Reagovat

"Euler totiž určil, že lze aplikovat eulerovský tah jen v případě, kdy z žádného nebo dvou z uzlů vychází lichý počet spojnic."

To je pravda jen pro neorientované grafy (místo z žádného ... lichý je lépe říci, že ze všech sudý). Ještě by bylo vhodné zmínit, jak se tah najde.

V neorientovaném grafu existuje eulerovský tah právě tehdy, když:
1. Všechny vrcholy mají sudý stupeň (= počet hran, které jsou s nimi incidentní = jsou k nim připojeny je sudý) - v tomto případě je lze začít v kterémkoliv vrcholu, díky sudosti se musíme po určitém kroku di vrcholu vrátit; jestliže tah neobsahuje všechny hrany, stačí najít vrchol, z něhož vedou neprozkoumané hrany, vrchol "rozpojit" a vydat se do neprobádaného okolí a díky sudosti se opět musíme někdy vrátit a až se tak stane, pokračujeme za místem přerušení. Takto se tah prodlužuje, až pokryje všechny hrany.
2. Právě dva vrcholy mají lichý stupeň a všechny ostatní mají sudý stupeň - v tomto případě je však tah nutné začít v jednom vrcholu s lichým stupněm a skončit v druhém vrcholu s lichým stupněm. Kdybychom začali ve vrcholu se sudým stupněm, eulerovský tah se nikdy najít nepodaří.

Případ orientovaného grafu, nutných podmínek existence eulerovského tahu a algoritmus jeho nalezení, jsou-li podmínky splněny, už nebudu rozepisovat. Koho by to také zde zajímalo?

5 Sunshine Sunshine | Web | 23. listopadu 2013 v 11:25 | Reagovat

(protože jsem na matematiku úplně tupá, budu se věnovat té pro mě "normální" části :D) Každopádně je to zajímavá úvaha a nedalo mi to a strávila jsem snad deset minut tím, že jsem po obrázku jezdila prstem a zkoušela různé možnosti - bez výsledku.
A zase se mi hrozně líbí ten - jak píšeš "psycho" - úvod, to je něco pro mě; dokážu si představit, jak někoho ta touha po vyřešení toho problému takhle pohltí a můžu už napsat jediné - piš dál takový "psycho" věci! :)

6 Mlok Mlok | Web | 30. listopadu 2013 v 17:42 | Reagovat

[5]: Jsem ráda že se ti můj příběh líbil :)

7 Mlok Mlok | Web | 1. prosince 2013 v 12:33 | Reagovat

[4]: Popravdě, jsem moc unavená na tohle nějak smysluplně reagovat. Takže jenom díky. Díky za doplnění informací. Jak je z článku asi vidět, já jsem jenom obyčejný nadšenec, tak hluboko do toho zase nevidím.

Nový komentář

Přihlásit se
  Ještě nemáte vlastní web? Můžete si jej zdarma založit na Blog.cz.