Kreslíme domeček jedním tahem

Dušan Polanský

Kdo by již od dětství neznal úlohu o nakreslení domečku jedním tahem? Vnučce je osm let a úlohu jsem ji vysvětlil asi před rokem. Domeček nakreslila hravě. Nedávno mi povídá: Dědo, domeček jsme kreslili o přestávce a představ si, že se dá nakreslit různě. Moje odpověď byla nematematická: Asi máš pravdu, vyzkoušíme to. A po příchodu domů a svačině jsme začali zkoušet, při nalezení 11 způsobů nás to přestalo bavit. Ovšem začalo mi vrtat hlavou, kolikaže způsoby vlastně ten zatracený domeček nakreslit. Přiznám se na rovinu, že moje znalosti o grafech (domeček je graf) jsou prabídné. Pouze jsem věděl, že grafům, které lze nakreslit jedním tahem se říká eulerovské, a že graf je eulerovský když je souvislý a každý vrchol má sudý stupeň. Nezoufejte, hned se k těmto jednoduchým pojmům vrátíme.

V Knihovně mám pouze dva tituly, kde je něco o teorii grafů. První je titul [1], který grafům věnuje z 13 kapitol kapitoly 4 až 6. Koupil jsem jej asi před deseti lety, ovšem od té doby jsem na něj nesáhl. A přiznám se, že i teď jsem si z něj přečetl jenom úvod k eulerovským grafům, tedy to, co jsem znal a následně jsem začal v knize listovat, zda tam není uveden vzoreček na určení počtu možností, kterými lze domeček nakreslit. Asi není, jednoduše jsem tam nic takového nenašel, ale budu upřímný, moc jsem se nenamáhal. Knihu jsem opět zasunul do knihovny, ale jsem si slíbil, že se k ní určitě někdy na jaře vrátím. Druhý titul je [2], autor o grafech pojednává v kapitole šestá, ovšem problematika eulerovských grafů se zde řeší vyloženě okrajově, autor věnuje pozornost jinému problémů. Takže nakonec jsem se rozhodl, že jaképak copak, raději budu rovnou kreslit!

Ovšem než se do kreslení dáme, alespoň malé vysvětlení k již zmíněným pojmům, podívejte se na obrázek č. 1. Graf je souvislý tehdy, když pro každé dva jeho vrcholy existuje cesta z jednoho do druhého vrcholu. Graf můžeme zapsat formálně jako G = G(V, E), kde V jsou jeho vrcholy a E jeho hrany. Stupeň vrcholu je počet hran grafu obsahujících daný vrchol, obvykle se značí degG(název vrcholu), přičemž G je název grafu. Již zmíněná věta říká, že graf je eulerovský, když je souvislý a každý jeho vrchol má sudý stupeň. Má to logiku, kdyby nebyl souvislý, tak bychom některé uzly nemohli spojit cestou, a když do některého vrcholu již jednou vlezeme, musíme z něho se také nějak dostat ven, tedy když jej chceme nakreslit jedním tahem. Ale bacha tohle neplatí pro koncové vrcholy, tedy tam, kde budeme kreslení začínat. V těchto uzlech může být stupeň vrcholu lichý. V případě našeho domečku, viz bod č. 4, dva spodní vrcholy mají stupeň lichý a dokonce domeček je rovinný graf, jelikož jej můžeme nakreslit tak, že žádné dvě hrany se neprotínají. Na obrázku č. 1 jsem v bodech č. 3, a 5 uvedl dva další zajímavé vztahy z teorie grafů, i když s naší úlohou až tak moc nesouvisí, protože jenom konstatují určité statické skutečnosti.

A konečně ke kreslení, viz obrázek č. 2. Vybral jsem si jeden ze dvou vrcholů, který má lichý stupeň a začal jsem vyrábět jednotlivé jednotažky. Jak jsem postupoval, mělo by být zřejmé z obrázku. Červeně jsem pokaždé vyznačil tah, kterým jsem začínal. Vidíte, že jednotažek na obrázku je 24. Pokud bych zvolil druhý vrchol lichého stupně, tak bych stejným způsobem namaloval dalších 24 jednotažek, takže to vypadá na 48 možností, protože když začnete kreslit domeček z vrcholů sudého stupně, domeček se vám jedním tahem nepovede nakreslit, což je v souladu se zmíněnou větou, protože náš graf obsahuje vrcholy lichého stupně. V každém případě na tak malý graf je to docela dost možností. A pokud by někdo vzoreček na počet možností nakreslení vykoumal, musel by vzoreček zohlednit i grafy s vrcholy lichého stupně, protože pouze z těchto vrcholů lze začít jednotažku kreslit.

Ono vůbec s grafy jsou jenom problémy právě kvůli bohatosti možností. Možná víte, že za jednu z nejtěžších matematických úloh se považuje problém obchodního cestujícího. Představte si, že jste obchodním cestujícím, který cestuje osobním autem. Někde bydlíte a máte postupně navštívit kupříkladu 40 míst. Je jasné, že chcete ušetřit čas a peníze, takže chcete, aby trasa, kterou urazíte z bydliště (současně je to i místo návratu) byla co nejkratší, přičemž znáte jednotlivé vzdálenosti mezi městy. V teorii grafů bychom řekli, že náš problém je popsán ohodnoceným grafem, jelikož hrany jsou ohodnoceny – v našem případě – kilometry. Vypouštíme složitosti typu, že tahle silnice je v hrozném stavu, a že raději zvolím delší, ale časově rychlejší trasu, prostě všechny silnice jsou v pořádku přesně jako v sci-fi. Z hlediska výpočtu nejde o nic složitého, stačí sečíst kilometry pro každou možnou trasu a pak jednotlivé součty porovnat. Vyhraje nejkratší trasa. Přece máme počítače, nemůže být v tom žádný zádrhel! Ale kdepak je, a parádně pořádný!

Takže kolik je možností pro volbu trasy? Představme si, viz obrázek č. 3, že máme navštívit dvě místa A a B. Možnosti jsou dvě: viz bod č. 1. Teď ať jsou místa tři, tedy A, B, C. Často se uvádí tahle matoucí úvaha, což bude asi tím, že autoři navzájem opisují: při plánování trasy mám tři možnosti, do kterého města vyrazím prvně, když tam jednání skončím, tak mám dvě možnosti, viz příklad s dvěma městy, tedy celkem je 6 možností, jelikož 3 × 2 = 6. Zkuste se ale podívat na obrázku č. 3 na bod č. 2, kde jsem vypsal více než 6 možností, třebaže úmyslně jsem zde uvedl dvě stejné trasy, možnosti č. 5 a č. 8. Z pohledu obchodního cestujícího jsou to totiž de facto stejné trasy, protože se liší jenom směrem jízdy. Zajímavá je možnost č. 3, je označena hvězdičkou, je tak dlouhá, že program by ji již ani nemusel dopočítat, jelikož délka již po čtyřech sčítancích přesahuje zatím dosaženou minimální hodnotu 24. Pokud to ale vezmeme přibližně, můžeme říct, že počet možnosti roste přibližně faktoriálně. Myslím, že výpočet faktoriálu, který značíme ! za číslem, je známý, kupříkladu 3! = 3 × 2 × 1 = 6. Při návštěvě 5 míst možností to již bude přibližně 5!, což je 120. Zkuste si ve vašem počítači zjistit hodnotu 25! Obrovské číslo! A což tak 50! Vidíme, že počet možností roste doslova šíleně, a bohužel v tom je i celý průšvih řešení problému obchodního cestujícího. Zatím nikdo nedošel na to, jak řešení problému zjednodušit. Pokud na to kápnete, přihlaste se v Clayovém matematickém ústavu a bude vám vyplacena odměna 1 milion dolarů.

I když nakonec problém obchodního cestujícího z nás laiků asi nikdo nevyřeší, mezi námi ani matematikům nedávám příliš velikou šanci, nic nám nebrání pobavit děti kreslením jednotažek. A pokud domeček zvládnou, zkuste jim vymyslet složitější eulerovský graf, ale pamatujte, že musí být souvislý a každý vrchol musí mít sudý stupeň. A pokud náhodou bude mít nějaký vrchol lichý stupeň, musí začít kreslit právě v tomto vrcholu. A uvědomte si, že matematika není jenom o výpočtu integrálů či řešení diferenciálních rovnic, ale např. i o kreslení jednotažek. A nepochybujte, že by taková matematika děti nebavila.

Literatura:

[1] Jiří Matoušek, Jaroslav Nešetřil: Kapitoly z diskrétní matematiky, Nakladatelství Karolinum, Univerzita Karlova v Praze, 2007.
[2] Kevin Devlin: Jazyk matematiky, Nakladatelství Argo a Dokořán. Praha 2002.

V Brně 18. prosince 2019.

Domů | Prolog 2001: Vesmírná odysea | Nejen básně v próze | Střípky