Zapisování grafů — metodické poznámky k hodině

Z Základy informatiky pro střední školy
Přejít na: navigace, hledání

Související materiály:



V této hodině se studenti seznámí se dvěma základními grafovými notacemi, se seznamem hran a maticí sousednosti. Nejde přitom nutně o to, aby následně řešení grafových úloh programovali. Kódování grafů je příležitost ke zkoumání a porovnávání různých reprezentací téže skutečnosti, k lepšímu porozumění grafům a kódování vůbec. Navíc si žáci připomenou, že i strukturu, kterou dosud chápali velmi vizuálně, lze zapsat pomocí "jedniček a nul".

Průběh hodiny

Hodinu zahájíme aktivitou, jejíž princip si studenti pravděpodobně pamatují: Mají za úkol vytvořit reprodukci (tentokrát grafu) pouze pomocí popisu. Tentokrát se ale spíš než na proces komunikace zaměříme na stanovení pravidel, která umožní graf "přenést" efektivně. Studenti pracují ve skupinkách za stále těžších a těžších podmínek, až dojdou k nějakému způsobu kódování grafů. Omezujeme především samotný přenos, nikoliv předchozí domluvu studentů ve skupině. O získanou zkušenost se můžeme opřít při zkoumání konkrétních notací v další části hodiny.

S pomocí online appletu žáci odhalí fungování seznamu hran a matice sousednosti. Samotné notace jsou vcelku triviální. Studenti by se nad nimi ale měli zamyslet hlouběji, zhodnotit je a porovnat. Zaměřujeme se zajména na jednoznačnost a efektivitu.

Studenti zkoumají, jestli je pro daný graf práve jedno zakódování, a naopak, jestli zakódování jednoznačně určuje graf. A pokud ne, čím se zakódování nebo grafy liší. Znovu si tak připomínají, že u grafu nezáleží na konkrétním nakreselní, ale skutečně jen na struktuře propojení vrcholů. Dále si všimnou, že použité notace nijak neurčují označení a pořadí vrcholů a hran. Kvůli tomu např. nestačí jen jednoduše srovnat dva zápisy, když chceme zjistit, jestli patří stejnému grafu.

Otázka efektivity se týká především délky zápisu. Pozor na srovnávání jablek s hruškami: seznam hran je sice na pohled kratší, využívá ale rozsáhlejší abecedu. Jedničky a nuly v matici sousednosti sice také zobrazujeme jako plnohodnotné znaky, vnitřně v počítači bychom ale pro velké grafy patrně kódovali po jednotlivých bitech. Studenti také mohou pracovat s dalšími kritérii pro efektivitu. Různé úkoly se s různými notacemi řeší různě snadno. Graf daný seznamem hran bývá snazší systematicky projít (a např. v něm najít cestu mezi dvěma vrcholy), špatně se v něm ale zjišťuje, jestli jsou dva konkrétní vrcholy propojeny hranou. To zjistíme mnohem rychleji v matici sousednosti. Kritéria efektivity samozřejmě mohou být ještě rozmanitější. Např. pro studenta, který neudrží úhledné řádky a sloupce, nedává použití matice smysl.

Na závěr hodiny studentům představíme skóre grafu. Využíváme shody okolností: skóre grafu domečku neodpovídá žádnému jinému grafu. To dává naději, že by šlo skóre využít jako notace, která by navíc byla velmi efektivní co do délky zápisu (pro každý vrchol by se ukládalo jen jedno číslo!). O to horší by efektivita byla co do obtížnosti dekódování. Zde studenti zúročí předchozí úvahy: pokud dobře prozkoumají otázku jednoznačnosti, objeví jednoduché protipříklady a zjistí, že skóre jako notaci využít nelze.

Další poznámky

Soutěživí studenti 
Pokud jsou všichni studenti soutěživí, můžeme aktivity pojmout jako soutěž (zadat stejné grafy k přenášení, sledovat, kdo graf první přenese správně atp.). V někerých třídách to patrně pomáhá, obecně to ale není nutné.
Formální správnost zápisů a zpětná vazba 
Opět zde platí, že není důvod k nějaké pečlivé kontrole správnosti zápisů studentů. Pokud udělají chybu, graf prostě nebude správně (nebo vůbec) dekódován. Obdoba funguje pro studentské snahy ušetřit si práci: některé pokusy fungují (pracovat jen s polovinou matice sousednosti, pokud je graf neorientovaný), některé nikoliv (vynechat počet vrcholů u seznamu hran). Není důležité si to pamatovat, důležité je si toho všimnout a umět rozpoznat, co vede ke zlepšení a co k chybám.
Pořadí notací 
Není nutné se držet uvedeného pořadí, lepších výsledků dosáhneme, když se přizpůsobíme zájmu studentů. Potřebné úvahy a závěry se nijak nezmění.
Jiné notace 
Při hodině vycházíme z toho, jaké notace (resp. jejich varianty) se objevily při činnosti studentů. Nejčastěji jsou to právě seznam hran a matice sousednosti, proto na nich stavíme zde i dále v učebnici. Není ale problém úlohy převést na jiné notace, které si studenti případně oblíbili. Nabízí ještě přinejmenším matice incidence a seznam sousedů. Volitelně lze prozkoumat také formát GraphML, který ve srovnání s ostatními není vůbec úsporný, ale za to ukládá mnohem více informací poměrně srozumitelným způsobem.