Sedm mostů města Královec

Lidé žijící v 18. století ve městě Královci dlouhou dobu řešili jednu hádanku: městem protéká řeka Pregola, která vytváří dva ostrovy. Přes tuto řeku vede na ostrovy celkem sedm mostů. Je možné během jedné nedělní procházky přejít všechny mosty, ale každý právě jednou? Podívejme se na to, jakým způsobem stály mosty přes řeku:

Je možné, abychom začali naši procházku v nějakém místě a prošli všechny mosty právě jednou? Můžeme to zkusit, začneme vlevo dole a budeme postupovat nahoru a pak postupně doprava, takto:

Vidíme, že jsme prošli šest ze sedmi mostů, jeden z mostů jsme minuli. Můžeme zkusit jinou cestu…

Zase jsme prošli pouze šest ze sedmi mostů našeho Královce. Skoro to vypadá, že není možné jednou procházkou přejít každý most právě jednou. Jednoho dne na tento problém narazil známý matematik Leonhard Euler. Co známý — Euler byl hotová legenda matematiky, po kterém je dokonce pojmenováno Eulerovo číslo. Euler si řekl, že tuto hádanku rozlouskne. Začal tím, že si označil jednotlivé ostrovy či části města, do kterých a ze kterých vedly mosty:

Euler nyní provedl následující úvahu: pokud na nějaký ostrov vede sudý počet mostů, můžeme tyto mosty projít během jedné procházky, ať už začneme kdekoliv. Zkrátka, jedním mostem na ostrov přijdeme, druhým odejdeme — počet mostů, které už nemůžeme projít, se snížil o dva. Abychom mohli přijít jedním mostem na ostrov a odejít druhým, potřebujeme dva mosty. Pokud na ostrov vede šest mostů, navštívíme ostrov třikrát. Například, představme si, že by na ostrov B vedly čtyři mosty takto:

Pak můžeme jednou nedělní procházkou projít všechny mosty, ať začneme kdekoliv. Zkuste si to! Na obrázku jsem vyznačil jednu cestu. Představme si, že by ale na ostrov B vedl ještě jeden most z ostrova D:

Vidíme, že cesta, kterou jsme zvolili, nám neumožní projít všechny mosty právě jednou. Museli bychom se některým mostem vrátit na ostrov B a pak projít na ostrov D. Ale my můžeme zvolit jinou cestu. Můžeme začít naší procházku na ostrově B a pak jsme schopni projít všechny mosty právě jednou:

Naší procházku jsme začali na ostrově B, šli jsme nahoru na území A, pak mostem zpět na B, na území C, pak zpět na ostrov B a nakonec na ostrov D. Pokud tak začneme na mostě, který má lichý počet mostů, jsme schopni přejít všechny jeho mosty právě jednou. Nebo můžeme jít úplně naopak — můžeme začít na ostrově D a na ostrově B skončit.

Euler si tak všiml, že aby bylo možné projít všechny mosty právě jednou, musí platit, že buď musí mít všechny ostrovy sudý počet mostů nebo tam mohou být dva ostrovy, které mají lichý počet mostů — na jednom ostrově s lichým počet mostů začneme a na druhém skončíme. Všechny ostatní ostrovy musí mít sudý počet mostů. Pokud se podíváme na původních sedm mostů v Královci:

tak vidíme, že každý ostrov má lichý počet mostů! Ostrov A má 3, B má 5, V má 3 a D má také 3. Proto hádanka nemá řešení — není možné, abychom prošli všech sedm mostů právě jednou na jedné nedělní procházce. Pokud bychom zbourali kterýkoliv z mostů, najednou by hádanka měla řešení. Zbourejme, například, jeden z mostů mezi ostrovy B a C:

Vidíme, že rázem má ostrov B 4 mosty a ostrov C dva mosty. Ostrovům A a D se počet mostů nezměnil. Máme najednou dva ostrovy se sudým počtem mostů a dva ostrovy s lichým počtem mostů. Pokud začneme naší procházku na jednom z ostrovů, které mají lichý počet mostů, dokážeme přejít všechny mosty právě jednou. Na obrázku jsme začali na ostrově A a skončili jsme na ostrově D.

Leonhard Euler tedy vyřešil další slavný matematický problém a více méně položil základy tomu, čemu v současné době říkáme teorie grafů a na jeho počet se „procházka, při které přejdeme všechny mosty právě jednou“ nazývá v řeči teorii grafů Eulerovský graf.