Problém siedmich mostov
Sedem mostov v Königsbergu je historicky známy matematický problém. V roku 1735 ho vyriešil Leonhard Euler. To viedlo k začiatku teórie grafov. Tá potom viedla k rozvoju topológie.
Mesto Königsberg v Prusku (dnes Kaliningrad v Rusku) sa rozprestieralo na oboch stranách rieky Pregel. Jeho súčasťou boli dva veľké ostrovy, ktoré boli navzájom a s pevninou spojené siedmimi mostmi.
Problémom bolo nájsť spôsob, ako prejsť cez mesto tak, že každý most prejdete len raz. Na ostrovy sa nedalo dostať inou cestou ako po mostoch. Každý most musel byť zakaždým kompletne prekročený. Prechádzka sa nemusela začínať a končiť na tom istom mieste. Euler dokázal, že tento problém nemá riešenie.
Mapa Königsbergu v Eulerovej dobe zobrazujúca skutočné rozmiestnenie siedmich mostov so zvýraznením rieky Pregel a mostov
Eulerova analýza
Po prvé, Euler poukázal na to, že na výbere trasy vo vnútri každej pevniny nezáleží. Jedinou dôležitou vlastnosťou trasy je poradie, v akom sa prechádzajú mosty. Zmenil teda problém na abstraktné podmienky. Tým položil základy teórie grafov. Odstránil všetky vlastnosti okrem zoznamu pevnín a mostov, ktoré ich spájajú. V jazyku teórie grafov nahradil každú masu zeme abstraktným "vrcholom" alebo uzlom. Potom nahradil každý most abstraktným spojením, "hranou". Hrana (cesta) zaznamenávala, ktoré dva vrcholy (zemské masy) boli spojené. Týmto spôsobom vytvoril graf.
→
→ 
Nakreslený graf je abstraktným obrazom problému. Hrany sa teda môžu spájať ľubovoľným spôsobom. Dôležité je len to, či sú dva body spojené alebo nie. Zmenou obrázka grafu sa samotný graf nemení.
Ďalej si Euler všimol, že (s výnimkou koncových bodov prechádzky) vždy, keď sa do vrcholu vstupuje mostom, opúšťa sa vrchol mostom. V každej prechádzke grafom sa počet vstupov do vrcholu rovná počtu výstupov z neho. Ak každý most prešiel presne raz, vyplýva z toho, že pre každú zemskú masu (okrem tých, ktoré boli vybrané pre začiatok a cieľ) musí byť počet mostov, ktoré sa dotýkajú tejto zemskej masy, párny. Je to preto, že ak existuje n mostov, prechádza sa cez ňu presne 2n-krát. Všetkých štyroch pevnín v pôvodnom probléme sa však dotýka nepárny počet mostov (jedného sa dotýka 5 mostov a každého z ostatných troch sa dotýkajú 3 mosty). Existujú najviac dve hmoty, ktoré môžu byť koncovými bodmi prechádzky. Takže tvrdenie o prechádzke, ktorá prechádza cez každý most raz, vedie k rozporu.
V modernom jazyku Euler ukázal, že to, či je možné prejsť grafom, v ktorom každá hrana prechádza raz, závisí od stupňov uzlov. Stupeň uzla je počet hrán, ktoré sa ho dotýkajú. Euler ukazuje, že nevyhnutnou podmienkou prechodu je, aby bol graf spojitý a mal presne nula alebo dva uzly nepárneho stupňa. Tento Eulerov výsledok neskôr dokázal Carl Hierholzer. Takáto prechádzka sa teraz nazýva Eulerova cesta alebo Eulerova prechádzka. Ak existujú uzly nepárneho stupňa, potom každá Eulerova cesta začína v jednom z nich a končí v druhom. Keďže graf reprezentujúci historický Königsberg má štyri uzly nepárneho stupňa, nemôže mať Eulerovu cestu.
Eulerova práca bola 26. augusta 1735 predložená Petrohradskej akadémii. Bola publikovaná ako Solutio problematis ad geometriam situs pertinentis (Riešenie problému týkajúceho sa geometrie polohy) v časopise Commentarii academiae scientiarum Petropolitanae v roku 1741. V angličtine je k dispozícii v publikácii The World of Mathematics.
Význam v dejinách matematiky
V dejinách matematiky sa Eulerovo riešenie problému Königsberského mosta považuje za prvú vetu teórie grafov. Teória grafov je v súčasnosti všeobecne považovaná za odvetvie kombinatoriky.
Súčasný stav mostov
Dva z pôvodných siedmich mostov boli zničené počas bombardovania Königsbergu počas druhej svetovej vojny. Ďalšie dva boli neskôr zbúrané. Nahradila ich moderná diaľnica. Ostatné tri mosty zostali, hoci len dva z nich pochádzajú z Eulerových čias (jeden bol prestavaný v roku 1935). V roku 2000 sa teda v Kaliningrade nachádzalo päť mostov.
Z hľadiska teórie grafov majú teraz dva z uzlov stupeň 2 a ďalšie dva majú stupeň 3. Preto je teraz možná Eulerova cesta, ale keďže musí začínať na jednom ostrove a končiť na druhom, je pre turistov nepraktická.
Súvisiace stránky
- Ikosian hra
- Hamiltonova cesta
- Voda, plyn a elektrina
- Problém obchodného cestujúceho
Otázky a odpovede
Otázka: Čo je to problém siedmich mostov v Königsbergu?
Odpoveď: Sedem mostov v Königsbergu je slávny matematický problém, ktorý spočíva v hľadaní spôsobu, ako prejsť cez mesto tak, že prejdete cez každý zo siedmich mostov len raz.
Otázka: Kto vyriešil problém siedmich mostov v Königsbergu?
Odpoveď: Leonhard Euler vyriešil problém siedmich mostov v Königsbergu v roku 1735.
Otázka: K čomu viedlo riešenie problému siedmich mostov v Königsbergu?
Odpoveď: Riešenie problému siedmich mostov v Königsbergu viedlo k začiatku teórie grafov, ktorá potom viedla k rozvoju topológie.
Otázka: Kde sa nachádza Königsberg?
Odpoveď: Königsberg sa nachádza v Prusku, ktoré je teraz súčasťou Kaliningradu v Rusku.
Otázka: Aké bolo usporiadanie Königsbergu?
Odpoveď: Königsberg bol rozložený na oboch stranách rieky Pregel a zahŕňal dva veľké ostrovy, ktoré boli navzájom a s pevninou spojené siedmimi mostmi.
Otázka: Aké boli požiadavky na riešenie problému siedmich mostov v Königsbergu?
Odpoveď: Problém vyžadoval nájsť spôsob, ako prejsť mestom tak, že každý most prejdete len raz, pričom každý most musí byť zakaždým prekonaný úplne. Na ostrovy sa nedalo dostať inou cestou ako po mostoch a prechádzka nemusela začínať a končiť na tom istom mieste.
Otázka: Dokázal Euler, že problém siedmich mostov v Königsbergu má riešenie?
Odpoveď: Nie, Euler dokázal, že problém siedmich mostov v Königsbergu nemá riešenie.
