Odkazy na kapitoly k ověřování najdete na úvodní stránce. Tyto vzdělávací materiály jsou alfa verzí určenou k ověřování ve školním roce 2018/2019 v rámci projektu CZ.02.3.68/0.0/0.0/16_036/0005322 Podpora rozvíjení informatického myšlení.


Jednotažky

Z Informatika pro každého
Přejít na: navigace, hledání
Regulární grafy
ikona boxu
Co se naučíš:
  • Systematicky zkoumat 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.
ikona boxu
Obvyklý průběh hodiny a metodické poznámky


Informace v tomto boxu lze zobrazit samostatně (např. pro tisk).

Související materiály: Plán hodiny (k použití přímo ve výuce), TODO: [[[:Učebnice/Grafy/Jednotažky/Hodina/PRIM-PL]] Pracovní list pro studenty] ------------- vkládat podmínečně, jen pokud PL existuje TODO: vytvořený v rámci projektu PRIM. --- doplň odkaz na PRIM, vkládej jako šablonu, aby se vložil externí odkaz

TODO: RVP

Výstupy podle RVP:

TODO: Používá systémový přístup k řešení problému, Pro řešení problému sestaví model, algoritmizace (strategie)

V této hodině studenti hlouběji prozkoumají jednotažky. Nejde jen o hlavolam ze zadních stran víkendových magazínů, najít průchod grafem bez opakování hran se hodí i v praxi. Pro studentyu je to zároveň příležitost k samostatnému zkoumání, logickému vyvozování, formuování a testování hypotéz.


Na začátku hodiny zařadíme cvičnou úlohu, k jejímuž řešení se využijí podobné argumenty jako u jednotažek. Potom připomeneme úvodní úlohu se strážným, která je ve skutečnosti také úlohou na zjištění, jeslti je graf jednotažkou. Větší část hodiny studenti stráví snahou najít a zformulovat pravidlo, které by jim umožnilo poznat, kdy je graf jednotažkou. Ze zpětného pohledu je pravidlo takřka triviální, ovšem odhalit jej vyžaduje vytrvalost a u některých studentů směrování od ostatních nebo od učitele. Není nutné prozrazovat řešení, stačí pomoci pokládat správné otázky.

Na konci hodiny budeme mít jasné pravidlo (jednotažka má všechny vrcholy sudého stupně), které jasně říká, jak úlohy řešit: stačí ověřit, jestli z každého vrcholu vychází sudý počet hran (až na případný počáteční a koncový vrchol).

Společně se studenty zformulujeme důkaz, který zároveň ukáže, že najít to nakreslení jedním tahem je už snadné.

Na závěr se vrátíme k úloze se strážným, abychom ukázali, jak poznatky z hodiny prakticky využít.

Další poznámky

  • I zde studentům pomůže práce ve dvojicích. Nutí je vyslovovat myšlenky nahlas. Kromě toho je kolega zdrojem kontroly i různých nápadů. V neposlední řadě studenti stihnou prozkoumat větší počet grafů, čímž zvyšují šanci na odhalení řešení.
  • Studenti se soustředí na zkoumání jednotažek, mezitím ale pracují s několika důležitými principy, které uplatní i později: implikace jsou jednosměrné a je nutno je posuzovat zvlášť, na kvantifikátorech záleží ("všchny vrcholy", "aspoň jeden", "žádný vrchol"...) atp.
  • Místo jednotažek bychom se mohli věnovat i jinému se základních témat o grafech: např. rovinnosti, barevnosti, hledání cest nebo koster. Jednotažky se obecně osvědčily jako přiměřeně jednoduché a zároveň zajímavé.
  • V učebnici záměrně používáme různé formulace vět o jednotažkách. Není důležité pamatovat si jakékoliv doslovné znění. Studenti mají pochopit podstatu a mají být schopni sami rozpoznat, že uvedené formulace říkají totéž.
  • Pokud je potřeba hodinu přerušit a nechat studenty pracovat doma, je vhodné je nechat 1-2 hypotézy o jednotažkách napsat, spolu s komentářem, jak si s danou hypotézou poradili: Povedlo se prokázat jejich platnost? Najít podpůrné argumenty, proč by měly fungovat? Nebo se povedlo najít protipříklady, takže studenti hypotézu zavrhli a nějak přepracovali?

TODO: hodí se být po regulárních grafech — rozmluvenost, práce s hypotézou, parita v pracovní paměti... dal jsem místo toho zatím cvičnou úlohu TODO: pokud programujeme, lze úlohu zadat jako programovací. Ano, lze zkoušet všechny možnosti, ale nešlo by to nějak vylepšit? Zkusme se zamyslet, třeba dáme dohromady nějaké pravidlo...

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

ikona boxu
Ú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?

ikona boxu
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í

Strazny s resenim.svg

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.

ikona boxu
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ší 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. TODO: asi do bonusu: To je jedna z nejstarších úloh, která se zabývala grafy.

TODO: pozn.: uvažujme tady jen souvislé grafy! jinak by to ani nemělo smysl

ikona boxu
Ú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. TODO: doplnit řešení

ikona boxu
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í. TODO: link na nějakou historii? Graf, který je jen otevřeným tahem, nazveme otevřenou jednotažkou, resp. otevřeným eulerovským grafem.TODO: (XXX: tady je terminologie nejednotná)

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.

ikona boxu
Ú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).

ikona boxu
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.

ikona boxu
Nápověda

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


ikona boxu
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ň.

TODO: XXX uvažujeme jen souvislé grafy, ale tady mi přišlo fajn být doslovný. dej taky pozor v důkazu, nejsem důsledný, nejlepší bude na začátku upozornit, že souvislost všude předpokládáme

Otazník
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?

TODO: BonusBox: je to LOKÁLNÍ pravidlo!!! resp. používá lokální vlastnosti - přitom důsledek hovoří o celém grafu!!

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 (třeba 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.

TODO: XXX obrázek!!! TODO: XXX zdůrazni konečnost ubýváním nenakresleného, pak se na to odkážu od algoritmů

TODO: BonusBox --- Alternativně z KSP

Nebo jinými slovy (http:ksp.mff.cuni.cz/tasks/10/solution3.html):// Důkaz ⇒: Kdyby graf nebyl souvislý nebo v něm existoval vrchol lichého stupně, je zjevné, že v něm nemůže být eulerovský tah. Zbývá tedy dokázat implikaci opačným směrem…

≤: Vezměme nejdelší možný tah v našem grafu. Pokud není uzavřený, jistě má nějaký koncový vrchol, tohoto vrcholu se ovšem tento tah dotýká lichý-počet-krát (jednou na začátku a pak vždy vejde a vyjde a skončí jinde), ale tento vrchol má sudý stupeň, takže existuje nepoužitá hrana z tohoto vrcholu vedoucí a o tu můžeme tah prodloužit ⇒ nebyl nejdelší a jsme ve při. Kdyby nebyl eulerovský, existuje hrana e, která v tahu není obsažena a přitom jeden z jejích vrcholů v v tahu obsažen je (graf je souvislý – pokud existuje jediná hrana e' mimo tah, vezmeme cestu z jejího libovolného krajního vrcholu do nějakého vrcholu v' tahu a za e prohlásíme první hranu na této cestě [ve směru od v'], jež v tahu není). A ve vrcholu v můžeme náš uzavřený tah rozpojit a k libovolnému z jeho konců hranu e přidat, čímž jsme jej opět prodloužili. Spor.

ikona boxu
Ú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.

ikona boxu
Ú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ě.

TODO: doplň sem řešení, tedy ten důkaz

1) Že má jednotažka sudé stupně až na dva, které jsou liché, je vidět podobně, jako v předchozím případě. Ty dva vrcholy se sudým stupněm odpovídají právě počátečnímu a koncovému vrcholu tahu. Což je správně, z počátečního vyjdeme a pak případně procházíme, ale na dobro už se nevrátíme, obdobně je to s vrcholem koncovým. 2) Máme-li graf se správnými stupni, musí to být jednotažka. Hledáme tedy ten tah, který celý graf pokrývá a nic nevynechá. Uděláme trik: K našem grafu přidáme hranu, která spojuje ty dva vrcholy s lichým stupněm. Tím jsme dostali graf, který má všechny stupně sudé. Je to povědomé? Ano, tento nový graf musí mít uzavřený tah! Najdeme ho podle předchozího postupu (postupné prodlužování), rozpojíme na dvou vrcholech spůvodně lichým stupněm, zahodíme přidanou hranu jak z grafu, tak i z tahu, a máme, co jsme chtěli. Převod na předchozí případ a využití již hotových výsledků je v informatice velmi oblíbený způsob, jak si šetřit práci.

ikona boxu
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.

ikona boxu
Ú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?

ikona boxu
Nápověda

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

ikona boxu
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.

ikona boxu
Ú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ší?

TODO: excel, nebo programovat!!

Vytvořte sešit pro tabulkový procesor, kam se na připravené místo vloží matice sousednosti, a v nějaké předem určené buňce se objeví, jestli je graf jednotažkou. Mělo by to fungovat aspoň pro grafy s deseti vrcholy, lépe ještě více. Použijte funkce. Bude se asi hodit součet či počet, dělení se zbytkem, abyste zjistili sudost, a podmíněná funkce (IF, nebo KDYŽ, záleží na programu).

S maticí je to myslím jednodušší, ale kdo by chtěl pracovat se seznamem hran, nebráním mu. Jestli bude možno pracovat s grafy (tedy maticemi) neomezených rozměrů, je to za 15 bodů navíc. Omezení tam bude pořád, totiž maximální velikost listu v programu, ale váš návrh by neměl vytvářet žádné další. 10 bodů udělím, když bude sice výpočet nějak omezen, ale bude přiložen postup, jak přijímanou oblast pro matici jednoduše "zvětšit" v případě potřeby. Jeslti tabulka pozná a rozliší, kdy se lze vrátit na stejné místo a kdy ne, přidám 10 bodů

  • 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í

ikona boxu
  • 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.