Logické hádanky

Průmyslový objekt je střežen soukromou agenturou. Hlídač má za úkol každý den projít celý objekt a pozamykat všechny dveře. Byla to pro něj hrozná otrava, a tak si to chtěl trochu oživit. Rozhodl se, že postupně projde všemi dveřmi a po projití je ihned za sebou zamkne (tzn. každými dveřmi projde právě jednou).
Půdorys domu je na následujícím obrázku. Proškrknutí zdí značí dveře ven nebo do sousední místnosti.

Jakou cestu zvolil, aby se mu to podařilo?
Poznámka: Po zamčení všech dveří nemusel nutně skončit vně objektu. Šlo mu jen o to si to vyzkoušet.

Ukázat/skrýt řešení:

Hlídač nemá šanci vysněný úkol splnit.
Půjdeme na to přes teorii grafů. Jednotlivé místnosti označme vrcholy a spojíme je mezi sebou hranou právě tehdy, když mezi nimi vedou dveře. Dveře vedoucí ven z budovy budeme směřovat do jednoho venkovního uzlu. Abychom postihli dvoje dveře vedoucí ven a zachovali definici grafu (mezi každými dvěma vrcholy nejvýše jedna hrana), přidáme meziuzel pro druhou cestu ven. Každý vrchol je popsán číslem, kolik do něj vede hran (tzv. stupeň vrcholu). Výsledný graf viz obrázek.
Nalezení řešení znamená, že graf se dá nakreslit jedním tahem, přičemž nemusíme nutně začínat a končit ve stejném uzlu (tzv. otevřený Eulerův tah). V teorii grafů pak platí věta:
Graf je otevřeně Eulerovský (dá se nakreslit otevřeným Eulerovým tahem) právě tehdy, když je souvislý a má právě 2 vrcholy lichého stupně.
Důkaz této věty není nijak složitý. Náš graf má 4 vrcholy lichého stupně, a proto se nedá nakreslit otevřeným Eulerovým tahem.

» Galerie » Logické hádanky