Sedm mostů města Královce. Jak Euler dokázal, že turistický problém nemá řešení

Začalo to jako nenápadný vtípek na Twitteru. Z akce #KaliningradIsCzechia se ale stává jedna z největších internetových rošťáren, které v našich končinách vznikly. Aktivní jsou Češi, Poláci, o Královci coby nové české exklávě u Baltského moře tweetují už i oficiální účty.

Královec, Královec… vždyť o něm je ta slavná Eulerova hádanka. Pojďme si ji připomenout.

Královec – dnes Kaliningrad, před tím Königsberg – leží na řece Pregole. Vytváří dva ostrovy, které byly v 18. století s okolním městem spojeny sedmi mosty. Nyní z původních mostů zbyly už jen dva, další byly vybudovány.

Klepněte pro větší obrázek
Sedm mostů města Královce. Zdroj: Bogdan GiuşcăCC-BY-SA-3.0

Úkolem bylo najít cestu městem tak, abyste při ní přešli všechny mosty, ale každý jen jednou. A k tomu bylo potřeba vrátit se do počátečního místa cesty. Euler v roce 1735 dokázal, že to není možné. Že u této topologie nelze použít tzv. eulerovský tah, který byl po něm později pojmenován – tedy postup, který obsahuje každou hranu grafu právě jednou.

Klepněte pro větší obrázek
Schematické znázornění královeckého problému. Zdroj: Pitel at cs.wikipediaCC-BY-SA-3.0

Euler poukázal na to, že nezáleží na volbě trasy uvnitř každé pevniny. Důležitá je pouze posloupnost překračovaných mostů. To mu umožnilo přeformulovat problém do abstraktní roviny a vytvořit základy teorie grafů.

V ní každou pevninu nahradíme abstraktním vrcholem (uzlem) a každý most hranou, která slouží k zaznamenání, která dvojice vrcholů (pevnin) je tímto mostem spojena. Výslednou matematickou strukturou je graf.

Klepněte pro větší obrázek
Královecké mosty v grafu Zdroj: BooyabazookaCC-BY-SA-3.0

Protože důležitá je pouze informace o spojení, může být tvar znázornění grafu libovolný. Na charakter samotného grafu to nemá vliv, protože u něj je podstatná pouze existence (nebo absence) hrany mezi jednotlivými dvojicemi uzlů. Nezáleží například na tom, zda jsou nakreslené hrany rovné nebo zakřivené, nebo zda je jeden uzel nalevo či napravo od druhého.

Euler vypozoroval, že během libovolné procházky grafem se počet vstupů do nekoncového vrcholu rovná počtu výstupů z něj. Jestliže se má každý most projít přesně jednou, vyplývá z toho, že pro každou pevninu musí být počet mostů, které se této pevniny dotýkají, sudý. Polovina z nich bude při konkrétní procházce procházena směrem k pevnině; druhá polovina směrem od ní.  Neplatí to jen pro vrchol, který byl vybrán pro začátek a konec cesty.

Všech čtyř pevnin v královeckém problému se však dotýká lichý počet mostů. Jedné se dotýká pět mostů a každé ze zbývajících tří pevnin tři mosty. Problém tak nemá řešení.

Euler svoji práci předložil 26. srpna 1735 Petrohradské akademii. Pod názvem Solutio problematis ad geometriam situs pertinentis (Řešení problému týkajícího se geometrie polohy) byla v roce 1741 publikována v časopise Commentarii academiae scientiarum Petropolitanae.

Další informace na Wikipedii:

Diskuze (7) Další článek: Asteroid, který zahubil dinosaury, vyvolal monstrózní vlny tsunami vysoké téměř pět kilometrů

Témata článku: Twitter, Wikipedia, Matematika, Hádanky, Bogdan, Polák, Euler, Kaliningrad, Most, Hrana, Graf, Vrchol, Pevnina



Vypadá jako iPhone 14 Pro Max, ale zdání klame. Čínská kopie však stojí jen dvacetinu toho, co originál

Vypadá jako iPhone 14 Pro Max, ale zdání klame. Čínská kopie však stojí jen dvacetinu toho, co originál

** Kopii iPhonu 14 Pro Max dnes pořídíte o 90% levněji, než originál ** Krabička je stejná, telefon má samozřejmě jiný hardware i výkon ** I přesto máte pocit, že držíte skutečný iPhone

Martin Chroust
ČínaKopie
Na povrchu Měsíce je tolik kyslíku, že by stačil pro lidstvo na 100 tisíc let

Na povrchu Měsíce je tolik kyslíku, že by stačil pro lidstvo na 100 tisíc let

** Lidstvo se připravuje na kolonizaci Měsíce ** Jednou ze základních surovin, bez nichž se na naší přirozené družici neobejdeme, je nepochybně kyslík ** Kde ho vzít?

Stanislav Mihulka
KolonizaceMěsícO2
Konec českého poskytovatele internetu v přímém přenosu. Připomíná to krachující energetické firmy
Lukáš Václavík
CETINPoskytovatelé internetuPřipojení k internetu