Sedm mostů města Královce
Sedm královéhradeckých mostů je historicky známý matematický problém. Leonhard Euler jej vyřešil v roce 1735. To vedlo k počátkům teorie grafů. Ta pak vedla k rozvoji topologie.
Město Königsberg v Prusku (dnes Kaliningrad v Rusku) se rozkládalo na obou březích řeky Pregel. Zahrnovalo dva velké ostrovy, které byly navzájem a s pevninou spojeny sedmi mosty.
Problémem bylo najít způsob, jak projít městem tak, aby každý most přešel jen jednou. Na ostrovy se nedalo dostat jinou cestou než po mostech. Každý most musel být pokaždé kompletně přejit. Procházka nemusela začínat a končit na stejném místě. Euler dokázal, že tento problém nemá řešení.
Mapa Königsbergu v Eulerově době s vyznačením skutečného rozložení sedmi mostů, se zvýrazněním řeky Pregel a mostů.
Eulerova analýza
Euler nejprve upozornil, že na volbě trasy uvnitř každé pevniny nezáleží. Jedinou důležitou vlastností trasy je pořadí, v jakém jsou překračovány mosty. Změnil tedy problém na abstraktní pojmy. Tím položil základy teorie grafů. Odstranil všechny vlastnosti kromě seznamu zemských masivů a mostů, které je spojují. V jazyce teorie grafů nahradil každé zemské těleso abstraktním "vrcholem" neboli uzlem. Každý most pak nahradil abstraktním spojením, "hranou". Hrana (silnice) zaznamenávala, které dva vrcholy (zemské masy) byly spojeny. Tímto způsobem vytvořil graf.
→
→ 
Nakreslený graf je abstraktním obrazem problému. Hrany lze tedy spojovat libovolným způsobem. Důležité je pouze to, zda jsou dva body spojeny, nebo ne. Změnou obrázku grafu se samotný graf nemění.
Dále si Euler všiml, že (s výjimkou koncových bodů procházky), kdykoli do vrcholu vstoupíme mostem, mostem vrchol opustíme. V každé procházce grafem se počet vstupů do vrcholu rovná počtu výstupů z něj. Jestliže každý most byl překročen přesně jednou, vyplývá z toho, že pro každou zemskou masu (kromě těch, které byly vybrány pro začátek a cíl) musí být počet mostů, které se této zemské masy dotýkají, sudý. Je to proto, že pokud existuje n mostů, přechází se přes něj přesně 2nkrát. Všech čtyř pevninských masivů v původním problému se však dotýká lichý počet mostů (jednoho se dotýká 5 mostů a každého z dalších tří se dotýkají 3 mosty). Existují nejvýše dvě tělesa, která mohou být koncovými body procházky. Věta o procházce, která každý most překročí jednou, tedy vede k rozporu.
V moderním jazyce Euler ukázal, že to, zda je možné projít grafem, který každou hranu protíná jednou, závisí na stupních uzlů. Stupeň uzlu je počet hran, které se ho dotýkají. Euler ukazuje, že nutnou podmínkou pro procházku je, aby byl graf spojitý a měl přesně nula nebo dva uzly lichého stupně. Tento Eulerův výsledek později dokázal Carl Hierholzer. Taková procházka se nyní nazývá Eulerova cesta nebo Eulerova procházka. Pokud existují uzly lichého stupně, pak každá Eulerova cesta začíná v jednom z nich a končí v druhém. Protože graf představující historický Königsberg má čtyři uzly lichého stupně, nemůže mít Eulerovu cestu.
Eulerova práce byla 26. srpna 1735 předána Petrohradské akademii. Byla publikována pod názvem Solutio problematis ad geometriam situs pertinentis (Řešení problému týkajícího se geometrie polohy) v časopise Commentarii academiae scientiarum Petropolitanae v roce 1741. V angličtině je k dispozici v knize The World of Mathematics.
Význam v dějinách matematiky
V dějinách matematiky je Eulerovo řešení problému Königsberského mostu považováno za první větu teorie grafů. Teorie grafů je dnes obecně považována za obor kombinatoriky.
Současný stav mostů
Dva z původních sedmi mostů byly zničeny během bombardování Königsbergu za druhé světové války. Další dva byly později zbourány. Na jejich místě byla postavena moderní dálnice. Zbylé tři mosty zůstaly zachovány, i když pouze dva z nich pocházejí z Eulerovy doby (jeden byl přestavěn v roce 1935). V roce 2000 tak bylo v Kaliningradu pět mostů.
Z hlediska teorie grafů mají nyní dva z uzlů stupeň 2 a další dva stupeň 3. Eulerova cesta je tedy nyní možná, ale protože musí začínat na jednom ostrově a končit na druhém, je pro turisty nepraktická.
Související stránky
- Ikosijská hra
- Hamiltonova cesta
- Voda, plyn a elektřina
- Problém obchodního cestujícího
Otázky a odpovědi
Otázka: Co je to problém Sedmi mostů u Königsbergu?
Odpověď: Sedm mostů v Königsbergu je slavný matematický problém, který spočívá v nalezení způsobu, jak projít městem tak, že každý ze sedmi mostů přejdete jednou a pouze jednou.
Otázka: Kdo vyřešil problém Sedmi královéhradeckých mostů?
Odpověď: Problém sedmi mostů v Königsbergu vyřešil v roce 1735 Leonhard Euler.
Otázka: K čemu vedlo řešení problému sedmi královéhradeckých mostů?
Odpověď: Řešení problému Sedmi královéhradeckých mostů vedlo k počátkům teorie grafů, která pak vedla k rozvoji topologie.
Otázka: Kde se nachází Königsberg?
Odpověď: Königsberg se nachází v Prusku, které je nyní součástí ruského Kaliningradu.
Otázka: Jaké bylo uspořádání Königsbergu?
Odpověď: Königsberg byl rozložen po obou stranách řeky Pregel a zahrnoval dva velké ostrovy, které byly navzájem a s pevninou spojeny sedmi mosty.
Otázka: Jaké byly požadavky na řešení problému sedmi mostů v Königsbergu?
Odpověď: Problém vyžadoval najít způsob, jak projít městem tak, že každý most přejdete pouze jednou, přičemž každý most musí být pokaždé kompletně přejet. Na ostrovy se nedalo dostat jinou cestou než po mostech a procházka nemusela začínat a končit na stejném místě.
Otázka: Dokázal Euler, že problém sedmi mostů v Königsbergu má řešení?
Odpověď: Ne, Euler dokázal, že problém Sedmi mostů v Königsbergu nemá řešení.
