Průvody – 2. – 7. mosty Königsbergu
Toto je mapa Königsbergu, která zobrazuje řeku, která jím protéká, ostrov uprostřed řeky a sedm mostů, které se přes řeku klenou. Obyvatelé Königsbergu chtěli uspořádat průvod, který by vedl přes každý z jejich mostů právě jednou. Zdálo se, že nenašli trasu průvodu, která by vedla přes všech sedm mostů.

VÝZVA
Pokud můžete, najděte trasu průvodu, která protne každý z jejich mostů právě jednou. Pokud ne, uveďte důvod, proč to není možné.

PRŮZKUM
Pokud přidáte další most přes řeku, usnadní to nebo ztíží problém?
Poznámky
VÝZVA
Začněme tím, že tento problém přeložíme na problém s hranami, kterými musíme projít. V dřívějším hádankovém příkladu týdne „Parades“ jsme viděli, že je zásadní mít maximálně dva uzly, kde se objevuje lichý počet stran.
Protože všechny čtyři uzly mají lichý počet hran, které do nich vstupují, bude nemožné najít trasu pro průvod!

PRŮZKUM
Pokud přidáte ještě jeden most přes řeku kdekoli, bude to velmi snadné vyřešit.
tento problém. Je to proto, že dva ze čtyř uzlů pak budou mít sudý počet hran, které do nich vstupují,
a zbydou tak pouze dva uzly s lichým počtem hran, které do nich vstupují.