Jednotažky

Co se naučíš:

• Systematicky zkoumat a pracovat na řešení zapeklité otázky, vyvozovat logické závěry
• Poznat, kdy lze graf nakreslit jedním tahem, a kdy lze navíc skončit na počátečním místě.
• Zformulovat příslušná pravidla.
• Znát (a poznat nové, když se objeví) situace, kde lze získané znalosti uplatnit.

Návrh průběhu hodiny a metodické poznámky

• Stručný průběh a poznámky
• Podrobný plán (příprava do hodiny)

Připomeňme si úlohu se strážným.

Úloha: Strážný

V podzemním výrobním zařízení hlídá v noci strážný. Zařízení tvoří místnosti spojené různě dlouhými chodbami. Strážný musí pravidelně všechny chodby projít. Z vrátnice vede po jedné chodbě do šatny, skladu i kantýny. Mezi skladem a kantýnou je přímá chodba. Ze šatny vedou chodby do všech ostatních místností. Do dílny se lze dostat kromě šatny také ze skladu.

Najdete pro strážného takovou trasu, aby na ní prošel všechny chodby právě jednou? Lze to udělat tak, aby obchůzku skončil na stejném místě, kde ji začal? Existuje takových tras víc?

Nápověda

Zkuste si situaci nějak znázornit. Všimněte si, že úloha obsahuje více než jednu otázku. Přinejhorším lze vyzkoušet všechny možnosti. Pokud se nějakou chvíli nedaří, uvažte, jestli úloha vůbec nějaké řešení mít musí.

Řešení

Trasu najít lze, například z vrátnice přes kantýnu, a sklad znovu do vrátnice, odtud pak do šatny, skladu a dílny, znovu šatny a skončit v kantýně. Existuje i mnoho dalších možností. Pokud bychom ale chtěli, aby se strážný ještě v rámci obchůzky vrátil na místo, odkud vyšel, nepořídíme. Zdůvodnit to můžeme rozborem (a vyloučením) jednotlivých potenciálních možností s pomocí několika logických úvah.

Hotovo, další!

Až jednotažky prozkoumáme a vyřešíme, už nás nebudou bavit. Budou příliš jednoduché — podobně, jako tomu bylo u hádání myšleného čísla. V tomhle informatika pokračuje. Už dávno nešijeme a neořeme rukama — ty si šetříme na úkoly, které stroje zvládají jen obtížně. Podobným způsobem nám informatika uvolňuje mozky na úkoly, které dosud strojově řešit neumíme. Každý sám si rozmyslete, kam takový vývoj vede, a jestli se vám to líbí. Zastavit to asi přirozeně nejde, jsou v tom totiž peníze: stroj bude postupem času levnější než člověk.

S potřebou projít všechny hrany nějakého grafu se setkáváme poměrně často. Projít každou hranu jen jednou znamená, že je taková trasa nejkratší. To se hodí zejména, pokud ji procházíme pravidelně, třeba kvůli poštovnímu doručování v ulicích nebo údržbě potrubí. Není ale myslitelné, abychom takové problémy řešili pokaždé způsobem pokus-omyl tužkou a papírem. V této hodině najdeme řešení obecné: tedy způsob, jak přiměřeně snadno zjistit, jestli efektivní průchod existuje, a kde případně začít. Pokud existuje, bývá už jeho nalezení poměrně snadné.

Úloha strážného zároveň odpovídá známému rébusu: nakreslení daného grafu "jedním tahem". Pro jednoduchost tedy budeme dále mluvit o kreslení a jednotažkách.

Úloha: Na rozehřátí

Vyřešte následující cvičnou úlohu:

Nakresli graf s pěti vrcholy, z nichž všechny jsou spojeny právě se třemi dalšími vrcholy. Tedy graf na 5 vrcholech stupně 3.

Nápověda

Když se něco nedaří, je možné, že to opravdu nejde. Než to ale vzdáš, pokus se přesvědčivě ukázat, že to skutečně nejde. A také proč to nejde.

Řešení

Daný graf sestrojit nelze. Při pokusech se rychle ukáže, že jednu hranu není kam připojit. Když se zamyslíme pečlivěji, zjistíme proč: každý z pěti vrcholů máme propojit s dalšími třemi vrcholy. Celkem tedy máme 5⋅3=15 konců hran. Ovšem každá hrana má dva konce, takže pro jednu hranu se konce nedostává.

Jak řešit jednotažky?

Než se pustíme dál, hodí se zjednodušit si vyjadřování zavedením několika pojmů:

Tah 

Posloupnost hran, které na sebe navazují koncovými vrcholy. Hrany se v tahu neopakují, vrcholy se opakovat mohou. Tah tedy představuje ono "kreslení jedním tahem" — tah je ale vhodnější, protože jak už víme z předchozí kapitoly, na nakreslení jako takovém nám nezáleží. A taky je to kratší slovo.

Uzavřený tah 

Končí tam, kde začal, na poslední hranu tedy navazuje první.

Otevřený tah 

Ten naopak končí jinde, než začal.

Jednotažka 

Graf, který obsahuje uzavřený tah a žádné jiné hrany. Jednotažky nazýváme také eulerovskými grafy. Obojí je pouze kratší vyjádření pro "graf, který lze nakreslit jedním tahem a vrátit se na začátek". Eulerovskými se tyto grafy nazývají na počest L. Eulera, který se tímto problémem zabýval jako první. Graf, který je jen otevřeným tahem, nazveme otevřenou jednotažkou, resp. otevřeným eulerovským grafem.

Dále už není co vysvětlovat. Budete muset prozkoumat množství grafů, které jdou a které nejdou nakreslit jedním tahem, a zjistit, proč tomu tak je.

Úloha: Řešení jednotažek

Hlavní otázky jsou dvě:

1. Lze daný graf nakreslit jedním tahem?
2. Lze přitom skončit tam, kde jsme začali?

Vaším úkolem je najít pravidla, podle kterých lze pro libovolný graf na dané otázky odpovědět (aniž bychom museli např. vyzkoušet všechny možné tahy a případně zjistit, že to není jednotažka).

Nápověda

Jak na to: Kresli spoustu příkladů, a všímej si, co se děje. Zaznamenej si u každého pokusu výsledek (jde/nejde) a případné další důležité informace, např. kde se hledání tahu zastavilo, proč to nešlo. Může pomoct pracovat ve dvojici a snažit se záměrně vytvářet jednak jednotažky a jednak grafy, které jednotažkami nejsou.

• Co mají jednotažky společného? Co mají společného "nejednotažky"?
• Zaznamenávejte svůj průchod například šipkami na hrany. Kudy přicházím do kterého vrcholu, kudy odcházím? Kolik šipek vede do vrcholu, a kolik jich vede ven?
• Když to nejde, co to kazí? Na kterých vrcholech tahy končí? Výrazně si je označte. Co mají společného? Kolik je kterých v jednotažkách, kolik v nejednotažkách?
• Jak vytvářím příklad grafu jednotažky? Jak příklad nejednotažky? Jak si "pojistím", že graf nakreslit půjde, a jak, že nepůjde?
• Když to jedním tahem jde, kolik je různých způsobů?
• Kde všude můžu začít, kde skončit?

Od speciálních případů se jejich postupným zobecňováním dostanete až k výslednému pozorování. Nezapomeňte vaše hypotézy průběžně testovat. Je celkem jedno, jak hodně špatné hypotézy za začátku jsou. Postupně se informatik dostává k lepším a lepším. Samozřejmě, čím lepší hypotézy nachází, tím dříve je hotov.

Nápověda

Na stupních vrcholů záleží. Jaké jsou stupně "průchozích" vrcholů? Jaké jsou stupně "koncových" vrcholů?

Nápověda

Když do vrcholu někudy přijdu, musím taky někudy jinudy odejít. Jak to ovlivní stupeň vrcholu?

Řešení

• Souvislý graf lze "nakreslit jedním tahem a vrátit se do výchozího vrcholu" právě tehdy, když mají všechny jeho vrcholy sudý stupeň.
• Souvislý graf lze "nakreslit jedním tahem bez návratu do výchozího vrcholu" právě tehdy, když mají právě dva jeho vrcholy lichý stupeň.

Neboli v nových pojmech:

• Souvislý graf je jednotažka (eulerovský) právě tehdy, když mají všechny jeho vrcholy sudý stupeň.
• Souvislý graf je otevřená jednotažka (otevřený eulerovský) právě tehdy, když mají právě dva jeho vrcholy lichý stupeň.

Zamysli se a odpověz:

Kontrolní otázka: Co když má graf právě jeden vrchol lichého stupně? Půjde nakreslit jedním tahem?

Zjištěný výsledek nám dává jednoduchý návod, jak zjistit, jestli je možné daný graf nakreslit jedním tahem. Jestli jste pracovali pečlivě a jednotažky podrobně zkoumali, je pro vás výsledek patrně dosti přesvědčivý. Navíc dává smysl: z každého vrcholu, do kterého jsem přišel, musím také odejít, až na vrchol počáteční (a koncový), kde to může být jinak. To je správná úvaha, jako důkaz ale nestačí. Informatik se chce být zcela jistý.

Důkaz

Jak dokázat, že je náš výsledek opravdu správně? Mluvíme tady o skutečném důkazu. Nejde jen o to, abychom se navzájem dostatečně přesvědčili, že náš výsledek funguje. Jde o to, abychom ze základních předpokladů logicky správně vyvodili náš výsledek. Ten pak nezáleží na tom, kdo má jaký názor. Takto dokázaný výsledek platí vždy (když platí základní předpoklady).

Budeme uvažovat případ, kdy se vracíme do výchozího vrcholu (uzavřená jednotažka) a graf je souvislý (jinak není o čem mluvit, jednotažka to určitě není). Druhý případ ("vrátit" se nelze) funguje velmi podobně, až na počáteční a koncový vrchol. Dokazovaná věta je ve formě ekvivalence (všimněte si spojení "právě když"). Ekvivalenci (⇔) většinou při dokazování rozdělujeme na dvě implikace (⇐ a ⇒) a obě dokazujeme postupně zvlášť. Jde tedy vlastně o dvě věty:

1. (⇒) Pokud je graf jednotažkou, mají všechny jeho vrcholy sudý stupeň. Nebo stručněji: všechny vrcholy jednotažky mají sudý stupeň.
2. (⇐) Graf je jednotažkou, pokud jsou všechny jeho vrcholy sudého stupně. Nebo stručněji: Graf se samými sudými stupni je jednotažkou.

Dobře si rozmyslete, čím se obě věty liší. V jedné víme, že máme jednotažku, tedy že existuje nakreslení jedním tahem, a tvrdíme, že v takovém případě budou vrcholy sudého stupně. Druhá věta se velmi liší: zkontrolovali jsme, že jsou všechny vrcholy sudého stupně, a nezávisle na čemkoliv dalším (ani na konkrétním propojení hranami!) tvrdíme, že existuje nakreslení jedním tahem.

Jestli chcete, zkuste si oba důkazy zformulovat nejdřív samostatně. Dokázat tu první větu je snazší, než dokázat tu druhou.

Důkaz může vypadat následujícím způsobem. Čtěte pomalu a pozorně.

1. (⇒) Pokud je graf jednotažkou, mají všechny jeho vrcholy sudý stupeň (všechny vrcholy jednotažky mají sudý stupeň). Jednotažku lze nakreslit jedním tahem. Při průchodu vrcholem tah "spotřebuje" dvě hrany: po jedné přijde, po druhé odejde. Zvláštním případem je výchozí (a zároveň koncový) vrchol. Tah jím může několikrát projít, na začátku jej ale musel opustit, a nakonec se do něj vrátí. Spotřebuje při tom opět dvě hrany. Když je tah dokončen, žádná nepoužitá hrana nezbývá (máme nakreslený celý graf). Počet hran vrcholu (jeho stupeň) tedy musí být nějakým násobkem dvou (příchod + odchod), tedy sudý. Toto přitom platí pro každý vrchol grafu. Dokázali jsme, že všechny vrcholy libovolné jednotažky jsou sudého stupně.
2. (⇐) Graf je jednotažkou, pokud jsou všechny jeho vrcholy sudého stupně (graf se samými sudými stupni je jednotažkou). Abychom tohle prokázali, musíme vlastně ukázat, že pro úplně libovolný graf (který splňuje dané vlastnosti, tedy všechny vrcholy mají sudý stupeň) umíme najít tah, který obsahuje všechny hrany. Graf může být libovolně zamotaný, ošklivý, veliký, ale jakmile je souvislý a se sudými stupni, má to být jednotažka, a my to musíme prokázat.

Představme si, že jsme zkusili nakreslit co největší část grafu. Jestli se se to povedlo a graf je celý, jsme hotovi. Co když je ale posloupnost kratší, a nějaké hrany nám ještě chybí?

1. Předně si uvědomíme, že je náš tah uzavřený. Proč? Protože kdyby nebyl, šel by snadno prodloužit: Jestli je otevřený, použil z počátečního i koncového vrcholu jen lichý počet hran. Protože je ale stupeň každého vrcholu podle předpokladů sudý, musí tam nějaká volná hrana zbývat. O tu hranu náš tah prodloužíme.
2. Dále: jestliže náš uzavřený tah ještě neobsahuje celý graf, je věkde volná (nenakreslená) hrana. Nějaká taková hrana se musí v některém vrcholu našeho tahu dotýkat (protože graf je souvislý — "nenakreslené" hrany nemohou ležet "jinde"). V tom případě ale můžeme tah opět snadno prodloužit! V daném vrcholu jej "rozpojíme", a volnou hranu připojíme k jednomu z konců. Tak jsme získali zase o něco delší tah v našem grafu.

Celkově se tedy ukazuje, že každý tah v našem grafu, který neobsahuje celý graf, lze prodlužovat (střídavě jedním nebo druhým způsobem), dokud ho obsahovat nebude. A až ten tah náležitě prodloužíme, budeme mít hledané "nakreslení jedním tahem" (nemůžeme prodlužovat donekonečna, protože graf má konečný počet vrcholů i hran). Tím je důkaz hotov.

Úloha: Kontrola důkazu

Zkontrolujte postup důkazu ne některém z vašich větších testovacích grafů. Nakreslete částečný tah a zkontrolujte, že jej lze stále prodlužovat, dokud není nakreslený celý graf.

Úloha: Důkaz pro otevřené jednotažky

Dokažte tvrzení o otevřených jednotažkách:

Souvislý graf je otevřená jednotažka (otevřený eulerovský) právě tehdy, když má právě dva vrcholy lichého stupně.

Nápověda

Využijte jako předlohu důkaz pro jednotažky uzavřené: využijte stejný postup, rozložte tvrzení na dvě části atd. Uvědomte si, čím se otevřené a uzavřené jednotažky liší. Z toho rozdílu plyne i rozdíl ve tvrzeních a tím i rozdíl jejich v důkazech.

Použití

Vrátíme se naposledy k úloze se strážným.

Úloha: Strážný

V podzemním výrobním zařízení hlídá v noci strážný. Zařízení tvoří místnosti spojené různě dlouhými chodbami. Strážný musí pravidelně všechny chodby projít. Z vrátnice vede po jedné chodbě do šatny, skladu i kantýny. Mezi skladem a kantýnou je přímá chodba. Ze šatny vedou chodby do všech ostatních místností. Do dílny se lze dostat kromě šatny také ze skladu.

Jak k jejímu řešení využít naše nové poznatky?

Nápověda

Víme, že záleží jen na počtu hran jednotlivých vrcholů. Vůbec nebudeme kreslit graf!

Nápověda

Stačí při čtení zadání sledovat, jaké existují místnosti, a s kolika dalšími jsou propojeny. Postupně vznikne třeba takovýto záznam:

• vrátnice: x x x
• šatna: x x x x
• sklad: x x x x
• kantýna: x x x
• dílna: x x

Jen je potřeba dávat pozor, abychom správně započetli oba konce každé chodby a žádný nevynechali. Spočtením značek už vidíme, že mají všechny vrcholy sudé stupně, kromě vrátnice a kantýny. Strážný tedy může projít každou chodbu právě jednou, ale nemůže skončit, kde začal. Koncovými místy budou kantýna a vrátnice.

Možná mu to ale nemusí vadit. Kontrolovat musí pravidelně, tak bude na další obchůzku střídavě čekat v kantýně a na vrátnici.

Úloha:

• Kreslíme-li graf, který není jednotažkou a nechceme opakovat hrany, budeme muset tužku zvednout. Jak pro daný graf zjistit, kolikrát nejméně bude tužku potřeba zvednout?
• Graf nemusí být zadaný obrázkem. Jak snadno rozhodovat o grafech v různých kódováních? Která způsob zápisu grafu je pro určování jednotažek nejvhodnější?

• Skóre není dostatečný popis grafu pro jeho nakreslení. Stačí ale k rozhodnutí o tom, jestli je graf jednotažkou?
• Vyhledejte letecké nebo satelitní snímky parku, hřbitova, tržiště apod. - jeden, který bez opakování projít nelze, jeden, který ano, a jeden, ve kterém se dokonce můžeme vrátit na výchozí místo.

Shrnutí

• Souvislý graf lze nakreslit jedním tahem a skončit na začátku, právě když má všechny vrcholy sudého stupně.
• Souvislý graf lze nakreslit jedním tahem, právě když má nanejvýš dva vrcholy lichého stupně.
• Pokud lze graf nakreslit jedním tahem, lze nakreslení sestavit postupně: každý částečný tah lze prodloužit, ať už na koncích, nebo někde uprostřed.