Po zvážení tohoto problému Euler v roce 1736 dokázal, že to není možné, a uvažoval o obecnějším problému: které oblasti, oddělené říčními rameny a propojené mosty, lze obejít tak, že navštívíte každý most právě jednou, a které jsou nemožné.
Königsbergské mosty">
Pojďme si problém trochu upravit. Každou z uvažovaných oblastí, oddělenou řekou, označíme bodem a mosty spojující je úsečkou (ne nutně přímkou). Pak místo plánu budeme jednoduše pracovat s určitým obrazcem složeným z úseků křivek a přímek. V moderní matematice se takovým obrazcům říká grafy, segmenty se nazývají hrany a body, které spojují hrany, se nazývají vrcholy. Pak je původní problém ekvivalentní následujícímu: je možné nakreslit daný graf bez zvednutí tužky z papíru, tedy tak, že každá jeho hrana projede právě jednou?
Takové grafy, které lze nakreslit bez zvednutí tužky z papíru, se nazývají jednokurzální (z latinského unus cursus - jedna cesta), nebo eulerovské. Problém je tedy postaven takto: za jakých podmínek je graf jednokurzální? Je jasné, že jednokurzální graf nepřestane být jednokurzovým, změní-li se délka nebo tvar jeho hran, stejně jako se změní umístění vrcholů - pokud se nezmění spojení vrcholů hranami (v smysl, že pokud jsou dva vrcholy spojeny, měly by zůstat spojené, a pokud jsou odděleny – pak rozpojeny).
Je-li graf jednokurzální, pak bude i topologicky ekvivalentní graf jednokurzální. Unicursity je tedy topologická vlastnost grafu.
Nejprve musíme rozlišit spojené grafy od nespojených. Propojené obrazce jsou takové, že libovolné dva body mohou být spojeny nějakou cestou patřící tomuto obrazci. Například většina písmen ruské abecedy je spojena, ale písmeno Y není: není možné se pohybovat z jeho levé poloviny doprava podél bodů patřících tomuto písmenu. Propojenost je topologická vlastnost: nemění se, když je obrazec transformován bez přerušení nebo slepení. Je jasné, že pokud je graf jednokurzální, pak musí být propojen.
Za druhé, zvažte vrcholy grafu. Indexem vrcholu budeme říkat počet hran nalezených v tomto vrcholu. Nyní si položme otázku: čemu se mohou rovnat indexy vrcholů jednokurzálního grafu?
Zde mohou nastat dva případy: čára vykreslující graf může začínat a končit ve stejném bodě (říkejme tomu „uzavřená cesta“) nebo možná v různých bodech (říkejme tomu „otevřená cesta“). Pokuste se nakreslit takové čáry sami - s jakýmikoli sebeprůniky, které chcete - dvojité, trojité atd. (pro přehlednost je lepší, aby nebylo více než 15 hran).
Je snadné vidět, že v uzavřené cestě mají všechny vrcholy sudý index a v otevřené cestě mají právě dva lichý index (toto je začátek a konec cesty). Faktem je, že pokud vrchol není počátečním nebo konečným vrcholem, poté, co k němu dorazíte, musíte jej opustit - takže tolik hran do něj vstoupí, stejný počet z něj vystoupí a celkový počet příchozích a odchozích okraje budou rovné. Pokud se počáteční vrchol shoduje s konečným vrcholem, pak je jeho index také sudý: počet hran, které z něj vyšly, stejný počet, který vstoupil. A pokud se počáteční bod neshoduje s koncovým bodem, pak jsou jejich indexy liché: musíte jednou opustit počáteční bod, a pak, pokud se k němu vrátíme, pak znovu odejít, pokud se vrátíme znovu, znovu odejít atd. .; ale potřebujeme přijít na konečnou, a když ji pak opustíme, tak se zase musíme vrátit atd.
Aby tedy byl graf jednokurzální, je nutné, aby všechny jeho vrcholy měly sudý index nebo aby počet vrcholů s lichým indexem byl roven dvěma.
 |
Vypočítejte indexy jeho vrcholů a ujistěte se, že nemůže být jednokurzální. Proto jste neuspěli, když jste chtěli oběhnout všechny mosty...
Nabízí se otázka: pokud souvislý graf nemá žádné vrcholy s lichým indexem nebo přesně dva takové vrcholy, pak je graf nutně jednokurzální? Dá se jednoznačně prokázat, že ano! Jednoznačnost tedy jednoznačně souvisí s počtem vrcholů s lichým indexem.
Cvičení: postavte další most na nákresu Königsbergských mostů – kde chcete – tak, aby výsledné mosty bylo možné obejít a každý navštívil právě jednou; opravdu jít touto cestou.
Teď je tu další zajímavý fakt: Ukazuje se, že jakýkoli systém oblastí spojených mosty lze obejít, pokud potřebujete navštívit každý most přesně dvakrát! Zkuste to sami dokázat.
| NOVINKY NA FÓRU Teorie rytířů éteru | 01.10.2019 - 05:20: -> - Karim_Khaidarov. 30.09.2019 - 12:51: |
7 mostů města Kaliningrad (Koningsberg) vedlo k vytvoření tzv. teorie grafů od Leonharda Eulera.
Graf je určitý počet uzlů (vrcholů), které jsou spojeny hranami. Dva ostrovy a břehy na řece Pregel, kde stál, byly spojeny 7 mosty. Slavný filozof a vědec I. Kant, procházející se po mostech v Königsbergu, přišel s problémem, který zná každý na světě jako problém „7 Königsbergských mostů“: je možné projít všechny tyto mosty a na zároveň se vrátit do výchozího bodu trasy, abyste šli po každém mostě pouze jednou?
Mnozí se pokusili tento problém vyřešit prakticky i teoreticky. Nikomu se to ale nepodařilo. Proto se věří, že v 17. století začali obyvatelé se zvláštní tradicí: při procházce městem překračujte všechny mosty pouze jednou. Nikomu se to ale přirozeně nepodařilo.
V roce 1736 tento problém zaujal vědce Leonharda Eulera, který byl vynikajícím a slavným matematikem a členem Petrohradské akademie věd a dokázal najít pravidlo, díky kterému bylo možné tuto hádanku vyřešit. V průběhu svých úsudků dospěl Euler k následujícím závěrům: 1. počet lichých vrcholů (vrcholů, ke kterým vede lichý počet hran) grafu musí být sudý. Nemůže existovat graf, který má lichý počet lichých vrcholů. 2. Pokud jsou všechny vrcholy grafu sudé, můžete nakreslit graf, aniž byste zvedli tužku z papíru, a můžete začít od libovolného vrcholu grafu a ukončit jej ve stejném vrcholu. 3. Graf s více než 2 lichými vrcholy nelze nakreslit jedním tahem.
To vede k závěru, že není možné přejít všech sedm mostů, aniž byste jeden z nich překročili dvakrát. Následně se tato teorie grafů stala základem pro návrh komunikačních a dopravních systémů a stala se široce používána v programování, informatice, fyzice, chemii a mnoha dalších vědách a oborech.
Je pozoruhodné, že historici věří, že existuje člověk, který tento problém vyřešil, že dokázal přejít všechny mosty pouze jednou, i když teoreticky...
A bylo to tak. Kaiser (tedy císař) Wilhelm byl proslulý svou jednoduchostí myšlení, přímostí a „blízkomyslností“. Jednou se málem stal obětí vtipu, který na něj hrál naučený rozum – vtipálci ukázali císaři mapu města Königsberg a požádali ho, aby se pokusil vyřešit tento slavný problém, který byl z definice neřešitelný. Kaiser však požádal pouze o kus papíru a pero s tím, že to vyřeší za pouhých 1,5 minuty. Vědci byli ohromeni - Wilhelm napsal: "Nařizuji stavbu osmého mostu na ostrově Lomze." To je vše, problém je vyřešen... A tak se v Kaliningradu objevil nový osmý most přes řeku, pojmenovaný na počest císaře. Problém s osmi mosty dokáže vyřešit i dítě...
Věděli jste, že sedm mostů města Koeningsberg (dnes se toto město nazývá Kaliningrad) se stalo „viníky“ za vytvoření teorie grafů Leonhardem Eulerem (graf je určitý počet uzlů (vrcholů) spojených hranami) . Ale jak se to stalo?
Dva ostrovy a břehy na řece Pregel, na kterých Koeningsberg stál, byly spojeny 7 mosty. Slavný filozof a vědec Immanuel Kant, kráčející po mostech města Königsberg, nastolil problém, který každý na světě zná jako problém 7 königsberských mostů: je možné projít všechny tyto mosty a zároveň? vraťte se do výchozího bodu trasy tak, abyste každý most přejeli pouze jednou. Mnozí se pokusili tento problém vyřešit prakticky i teoreticky. Nikomu se to ale nepodařilo, ani se nepodařilo prokázat, že to není možné ani teoreticky. Proto se podle historických údajů věří, že v 17. století si obyvatelé vytvořili zvláštní tradici: při procházce městem přejděte všechny mosty pouze jednou. Ale jak víte, nikomu se to nepodařilo.
V roce 1736 tento problém zaujal vědce Leonharda Eulera, vynikajícího a slavného matematika a člena Petrohradské akademie věd. Napsal o tom v dopise svému příteli, vědci, italskému inženýrovi a matematikovi Marionimu z 13. března 1736. Našel pravidlo, pomocí kterého mohl snadno a jednoduše získat odpověď na tuto otázku, která zajímá každého. V případě města Koeningsberg a jeho mostů se to ukázalo jako nemožné.
V procesu své úvahy Euler dospěl k následujícím teoretickým závěrům:
Počet lichých vrcholů (vrcholů, ke kterým vede lichý počet hran) grafu musí být sudý. Nemůže existovat graf, který má lichý počet lichých vrcholů.
Pokud jsou všechny vrcholy grafu sudé, můžete nakreslit graf, aniž byste zvedli tužku z papíru, a můžete začít od libovolného vrcholu grafu a ukončit jej ve stejném vrcholu.
Graf s více než 2 lichými vrcholy nelze nakreslit jedním tahem 
Pokud vezmeme v úvahu toto pravidlo pro 7 mostů Koeningsbergu, pak části města na obrázku (grafu) jsou označeny vrcholy a mosty jsou označeny hranami spojujícími tyto vrcholy. Graf 7 Königsbergských mostů měl 4 liché vrcholy (to znamená, že všechny jeho vrcholy byly liché), proto není možné projít všech 7 mostů, aniž byste některým z nich dvakrát prošli.
Zdálo by se, že takový neobvyklý objev nemůže mít žádné reálné uplatnění ani praktický přínos. Ale využití se našlo a ještě něco navíc. Teorie grafů, kterou vytvořil Leonhard Euler, tvořila základ pro návrh komunikačních a dopravních systémů, používá se v programování a informatice, fyzice, chemii a mnoha dalších vědách a oborech.
Nejzajímavější ale je, že historici věří, že existuje člověk, který tento problém vyřešil, všechny mosty dokázal přejít pouze jednou, i když teoreticky, ale řešení existovalo... A takhle se to stalo...
Kaiser (císař) Wilhelm byl proslulý svou jednoduchostí myšlení, přímostí a vojenskou „úzkostlivostí“. Jednoho dne se na společenské akci málem stal obětí vtipu, který se na něj učené mozky přítomné na recepci rozhodly zahrát. Ukázali císaři mapu města Königsberg a požádali ho, aby se pokusil vyřešit tento slavný problém, který byl z definice prostě neřešitelný. Kaiser k překvapení všech požádal o kus papíru a pero a zároveň upřesnil, že tento problém vyřeší za minutu a půl. Ohromení vědci nevěřili svým uším, ale inkoust a papír se pro něj rychle našly. Císař položil kus papíru na stůl, vzal pero a napsal: "Nařizuji stavbu osmého mostu na ostrově Lomze." A celý problém je vyřešen.....
Tak se ve městě Königsberg objevil nový 8. most přes řeku, který dostal název Kaiserův most. A nyní i dítě může vyřešit problém s 8 mosty .
Netradiční řešení problému
Kaiserovo "řešení"
Na mapě starého Königsbergu byl ještě jeden most, který se objevil o něco později a spojoval ostrov Lomse s jižní stranou. Tento most vděčí za svůj vzhled samotnému problému Euler-Kant. Stalo se tak za následujících okolností.
Císař Wilhelm byl známý svou přímočarostí, jednoduchostí myšlení a vojenskou „úzkostlivostí“. Jednoho dne se na společenské akci málem stal obětí vtipu, který se na něj učené mozky přítomné na recepci rozhodly zahrát. Ukázali císaři mapu Königsbergu a požádali ho, aby se pokusil vyřešit tento slavný problém, který byl z definice neřešitelný. Kaiser k překvapení všech požádal o tužku a papír s tím, že problém vyřeší za minutu a půl. Ohromený německý establishment nevěřil svým uším, ale papír a inkoust se rychle našly.
Císař položil kus papíru na stůl, vzal pero a napsal: "Nařizuji stavbu osmého mostu na ostrově Lomze." Tak to vypadalo v Königsbergu nový most, kterému se říkalo „Kaiserův most“. A nyní by problém s osmi mosty mohlo vyřešit i dítě.
viz také
Literatura
Nadace Wikimedia. 2010.
Město Königsberg, které vzniklo ve 13. století, se formálně skládalo ze tří nezávislých městských sídel, několika osad a měst. Nacházely se na březích a ostrovech řeky Pregel, která rozdělovala město na čtyři hlavní části: Altstadt a Löbenicht, Kneiphof, Lomse, Fortstadt. Pro komunikaci a obchod mezi městskými sídly se ve 14. století začaly stavět mosty.
Kvůli neustálému vojenskému nebezpečí z Polska a Litvy byl před každým z mostů postaven obranný neboli tzv. most. Rozhledna s uzamykatelnými horními nebo dvouramennými branami z dubu s kovaným železným ostěním. A samotné mosty získaly charakter obranných staveb.
Mosty byly dějištěm procesí, náboženských a slavnostních akcí a procesí a v letech tzv. „V první ruské éře“ (1758 - 1762), kdy se Koenigsberg během sedmileté války stal součástí Ruské říše, se přes mosty konaly pravoslavné náboženské procesí. Kdysi byl takový náboženský průvod zasvěcen pravoslavnému svátku Požehnání vody řeky Pregel, což vzbudilo skutečný zájem domorodých obyvatel Koenigsbergu.
Na začátku 20. století bylo všech sedm mostů rýsovatelných, ale kvůli oslabení a poklesu plavby po řece Pregel jsou tři mosty, které se dochovaly dodnes, rýsovatelné.
Obchodní most, Krämerbrücke
Nejstarší ze sedmi mostů v Königsbergu je Lavochny most(Krämerbrücke), která spojovala město Altstadt (Královský zámek) a ostrov Kneiphof.
Postaven v roce 1286, v roce 1900 byl na místě starého dřevěného mostu postaven nový kovový most. Název mostu naznačuje, že on sám a přilehlé území řeky Pregolya byly koncentrací obchodu.
U vstupu na most byla instalována socha Hanse Zagana, syna kneiphofského ševce. Podle legendy Hans během bitvy mezi vojsky Řádu německých rytířů a Litvinů u Rudau (obec Melnikovo, Zelenogradská oblast) vyzvedl řádový prapor z rukou zraněného rytíře. Nacisté, kteří se v Německu dostali k moci v roce 1933, z ideologických a morálních důvodů pomník Zaganovi strhli, protože byl Žid.
V roce 1972 byl zbořen kvůli stavbě Estakadného mostu.
Lavochny most. V pozadí jsou sklady a nakládací plocha lodí - Lastadie
Lavochny most s přístavními sklady-stodolami Speicher (Speicher) na pravém nábřeží řeky Pregel. Okresy Laak a Hundegatt. Vlevo je ostrov Kneiphof
Zelený most, GrüneBrücke
Druhý nejstarší most v Königsbergu je Zelený most. Postaven v roce 1322. Most v roce 1582 vyhořel, do roku 1590 byl přestavěn a v dřevěné podobě existoval až do roku 1907, kdy byl nahrazen mostem kovovým.
Spojila ostrov Kneiphof a oblast Fortstadt přes staré rameno řeky Pregolya pro cestování z Královský hrad na předměstí Ponart. Samotný název mostu pochází z barvy nátěru, kterým byly natřeny rozpětí a podpěry mostu.
V 17. století byla Zelený most zazněly dopisy přijíždějící do Königsbergu. Čekání na poštu Zelený most Obchodníci města se shromáždili a při čekání na korespondenci diskutovali o svých záležitostech. V roce 1623 přesně kolem Zelený most Byla postavena Koenigsberg Trade Exchange.
V roce 1972 padl Zelený most, stejně jako most Lavochný, za oběť Kozlovému mostu.
Zelený most. Pohled z ostrova Kneiphof
Pohled na Zelený most a obchodní burzu
Giblet (pracovní) most, Koettel brücke
V roce 1377, po Lavochném a Zeleném mostě, proti proudu starého koryta řeky Pregel, Droby nebo Pracovník most, který také spojoval ostrov Kneiphof a oblast Forstadt.
Obě možnosti překladu nejsou ideální, protože... Německý název mostu pochází ze Saska a v ruské verzi znamená zhruba „pomocný, pracovní, určený k přepravě odpadků“. Za svůj název s největší pravděpodobností vděčí nedalekým jatkám.
V roce 1886 byl dřevěný přestavěn na železný.
Během druhé světové války Gibletův most byla zničena a nikdy nebyla obnovena.
Gibletův most. Pohled na obchodní burzu z ostrova Kneiphof
Gibletův most. Pohled ze Zeleného mostu
Forge Bridge, Schmitderbrüke
V roce 1397 byl v Königsbergu, proti proudu nového koryta řeky Pregel, postaven Forge Bridge, který stejně jako Lavochny most spojoval město Altstadt a ostrov Kneiphof.
V blízkosti tohoto mostu na břehu řeky Pregel se tradičně nacházeli kováři.
V roce 1787 byl most velmi opotřebovaný a zchátralý a byl nahrazen mostem novým, ale také dřevěným. V roce 1896 byl na místě starého dřevěného mostu postaven nový kovový most.
Forge Bridge byl zničen během druhé světové války a nebyl nikdy obnoven.
Forge most s vyhlídkovou věží
Kuznechny most
Dřevěný most, Holzbrücke
V roce 1404 byl mezi Altstatem a ostrovem Lomze postaven čtyřnásobný most, kterému se říkalo Dřevěný.
Na Dřevěném mostě tam bylo pamětní deska s úryvky z pruské kroniky. Samotné desetisvazkové dílo Albrechta Lukhela Davida vyprávělo o starověkém pohanském Prusku a historii Řádu německých rytířů až do roku 1410.
V roce 1904 byl na místě starého dřevěného mostu postaven nový kovový most, ale název mostu zůstal stejný. V této podobě se Dřevěný most dochoval dodnes.
Dřevěný most. Pohled na ostrov Kneiphof
Vysoký most, Hohebrücke
Postaven v Königsbergu v roce 1520, aby spojil ostrov Lomse a region Forstadt.
V roce 1882 byl rekonstruován, jeho dřevěné části byly nahrazeny kovovými. V témže roce vedle Vysoký most V oblasti Forstadt byl postaven mostní dům. Tato krásná malá stavba v novogotickém stylu se dochovala dodnes.
V roce 1937 byl starý demontován a poblíž byl postaven nový kovový s betonovými podpěrami. Ze starých Vysoký most Betonovo-cihelné podpěry zůstaly zachovány.
Vysoký most. Pohled na ostrov Lomse
Vysoký most. Pohled z ostrova Lomse do čtvrti Forstadt
Medový most, Honigbrücke
Nejmladší ze sedmi mostů v Königsbergu spojoval ostrov Lomse a ostrov Kneiphof.
Existuje několik verzí o původu jména Medový most. Podle jednoho z nich zaplatil Besenrode, člen kneiphofské radnice, stavbu mostu sudy s medem, jiným způsobem se z medu platila stavba obchodní stanice u mostu. Ale tyto verze jsou pravděpodobně jen městské legendy.
Název mostu s největší pravděpodobností pochází ze slova „hon“, což znamená výsměch (výsměch). Postavením tohoto mostu získali obyvatelé ostrova Kneiphof nejkratší cestu na ostrov Lomse, obcházející Vysoký most, který patřil Altstadtu. Stal se tak jakoby výsměchem hlavnímu z königsberských měst – Altshadtu. Za to Altstadtové přezdívali Kneiphofiti – medolízači.
v roce 1882 byl na místě starého Medového mostu postaven nový kovový most.
Medový most. Pohled na ostrov Kneiphof a katedrálu
Dochoval se dodnes a používá se především jako most pro chodce, protože v současnosti se na ostrově Kneiphof nachází pouze katedrála - hlavní atrakce města Kaliningrad. V dnešní době novomanželé věší na zábradlí visací zámky se svými jmény a datem svatby. Medový most, a klíče od zámků jsou rozbity a vhozeny do řeky Pregel.
Problém sedmi mostů Königsberg, Leonhard Euler a teorie grafů
Obyvatelé Königsbergu se od pradávna potýkali s hádankou: Je možné přejít všechny mosty a projít po každém pouze jednou? Tento problém byl vyřešen jak teoreticky, na papíře, tak i v praxi na procházkách - procházení právě po těchto mostech. Nikdo nebyl schopen dokázat, že to bylo nemožné, ale nikdo nemohl udělat tak „tajemnou“ procházku po mostech.
V roce 1736 se slavný matematik, člen petrohradské akademie věd Leonhard Euler, zavázal vyřešit problém sedmi mostů. Ve stejném roce o tom napsal inženýrovi a matematikovi Marionimu. Euler napsal, že našel pravidlo, podle kterého není těžké spočítat, zda je možné přejít všechny mosty, aniž by některý z nich přešel dvakrát. To na sedmi mostech Königsbergu není možné.
Na městském diagramu (grafu) odpovídají okraje grafu mostům a vrcholy grafu (body, ve kterých se spojují čáry) odpovídají částem města. Při úvahách o problému Euler dospěl k následujícím závěrům:
vrcholy grafu mohou být sudé nebo liché- jedním tahem pera můžete nakreslit graf, jehož všechny vrcholy jsou sudé, můžete začít v libovolném vrcholu grafu a skončit stejným vrcholem
- počet lichých vrcholů (těch, ke kterým vede lichý počet hran) musí být lichý, graf se sudým počtem lichých vrcholů neexistuje
- Je nemožné nakreslit graf s více než dvěma lichými vrcholy jedním tahem.
Graf Königsbergských mostů má čtyři liché vrcholy, tedy všechno. Není tedy možné přejít všechny mosty, aniž byste jeden projeli dvakrát.
NOVINKY NA FÓRU  Teorie rytířů éteru | 23.02.2020 - 19:17: -> - Karim_Khaidarov. 23.02.2020 - 19:14: |
