Úvod — metodické poznámky k hodině

Související materiály:

• Kapitola učebnice
• Plán hodiny (k použití přímo ve výuce)

V této hodině studenti dojdou ke grafům a seznámí se se základními pojmy. Průběh je poměrně přímočarý: při řešení úloh vyplyne, že je užitečné nakreslit si schéma, a následně to schéma pojmenujeme. Zároveň ukážeme, že to, co studenti dělají, je modelování. V závěru hodiny si studenti vyzkouší grafy vytvářet na počítači.

Průběh hodiny

Na začátku studenti ve skupinkách řeší některou z předložených úloh. Řešení většiny úloh je dosti jednoduché. Studenti mají ale také za úkol je zformulovat tak, aby o správnosti přesvědčili ostatní. Zároveň je pro každou skupinku poměrně přísně omezený čas. Mnoho skupin proto použije více či méně přehledný graf (i v případě, že řešení našli jiným způsobem).

Pokud studenti kreslí na tabuli, snažíme se zorganizovat místo tak, aby na konci na tabuli zůstalo několik grafů. Jedna z možností je nechat několik skupin zároveň připravit potřebné obrázky na různé části tabule. Tím se zároveň ušetří čas, který studenti potřebují ke kreslení.

Na předvedených řešeních si všimneme jejich společného prvku: většina obsahovala nějaká nakreslená schémata z věcí spojených čarami. Úlohy přitom byly velmi rozdílné. Na základě toho se rozhodneme tato schémata blíže prozkoumat a zavést základní pojmy. Souvisejících pojmů je celá řada. S jejich případným zavedením je ale lepší počkat až do okamžiku, kdy se bez nich studenti dále neobejdou.

Zároveň studentům představíme, co už taktéž intuitivně používají, totiž modelování. Následně se k řešeným úlohám vrátíme, abychom zhodnotili, jak jsme je namodelovali. Tedy jestli jsme ze zadání opravdu vybrali právě jen podstatné informace a zorganizovali je tak, aby nám maximálně usnadnily řešení.

V závěru hodiny si studenti vyzkouší práci s nějakým editorem grafů. Nemá smysl se učit podrobně jeho jednotlivé funkce, spíše téma využíváme k procvičení schopnosti vyznat se rychle v nové aplikaci. Zároveň žáci zjistí, jaké možnosti editor nabízí, a budou po něm moci ve vhodných chvílích sáhnout.

Poznámky k jednotlivým úlohám

Uvedené úlohy nemají stejnou obtížnost, takže je lze rozdělit s ohledem na schopnosti jednotlivých pracovních skupin. Různorodost úloh jednak naznačuje šíři situací, v nichž se uplatní grafy, a jednak zvyšuje šanci, že studenty jeden z příkladů zaujme natolik, aby se mu věnovali hlouběji.

Vlaková síť Trainsylvania 

Studenti na stránce [1] hledají spojení do stanice Suburbopolis. Vlakové spoje mezi stanicemi jsou dost svérázné, tabulka nebo plánek velmi pomůžou rychlému řešení. Přitom je potřeba si uvědomit, že z každé stanice odjíždí právě dva vlakové spoje a že jsou jednosměrné. Při kreslení grafu rukou není hned zřejmé, jak se vyhnout křížení hran. Hezky pak vynikne rozdíl při použití editoru, v němž je mnohem snazší vrcholy posouvat a křížení odstranit.

Batůžkáři 

Studenti hledají nejkratší cestu. Graf je velmi malý, téměř není třeba použít žádný systematický postup. V každém případě jim ale pomůže, když si situaci nakreslí, což je také smyslem zadání úlohy. Některé správně napadne, že není nutno přepisovat celé označení míst, stačí nějaké zkrácené identifikátory. Jak se batůžkáři jmenují nebo jak prudce se kde stoupá je už jedno úplně. Dále je nutno správně odhalit, že vrtulník a lanovka neznamenají chůzi pěšky. V grafu je tak dokonce možné nástupní a výstupní vrcholy spojit. Takovéto úvahy žáci provádí, když se k řešení vrátí, aby zhodnotili, jak účelně situaci modelovali.

Strážný 

Z této úlohy vychází zájem o jednotažky v následujících kapitolách, doporučujeme ji tedy zařadit. Nalézt řešení (resp. přesvědčit se, že neexistuje) není těžké, když se použije obrázek. O to větší důraz věnujeme preciznosti vyjadřování a argumentace studentů. Opět nezáleží na tom, jak se konkrétní místnosti jmenují, ani jak přesně jsou umístěny. Záleží jen na jejich propojení. Pochopitelně není potřeba ani kreslit chodby jako chodby (s oběma stěnami) - i od toho můžeme abstrahovat.

Infrastruktura 

Tato úloha je obtížnější než ostatní, protože vyžaduje daný graf nakreslit do roviny. Co víc, požadovaný graf (resp. síť rozvodů) do roviny nakreslit nelze, což je nutno prokázat systematickým prověřením možností. Je možné, že studenti zdánlivě nic nepředvedou a jen zkonstatují, že se řešení v daném čase najít nepodařilo. Budou mít pravdu, ale jejich zjištění není příliš užitečné. Měli by zkusit zformulovat (příp. nakreslit), co přesně se nepodařilo. Taková informace pomůže na práci navázat a nakonec zjistit, že propojení s požadovanými vlastnostmi neexistuje.

Rodinka 

Tato úloha je velmi jednoduchá, téměř všichni studenti už někdy viděli nakreslený rodokmen a úlohu úspěšně vyřeší. Nestačí ale jen členy rodiny pospojovat čarami, různé druhy vztahů je třeba rozlišit.

Sněhová kalamita 

Další velmi snadná úloha, hledá se tzv. kostra jednoduchého neohodnoceného grafu. Některé studenty ale zaskočí počet možných řešení. Ne všichni také hned vidí, že všechna řešení obsahují stejný počet úseků. Otázka na kvalitu otevírá diskusi o kritériích. Ze zadání žádná neplynou, ale lze např. uvažovat, jak minimalizovat průměrnou vzdálenost mezi uzly ve vyčištěné síti, nebo jak upřednostnit uzly uprostřed, které by mohly být důležitější. Na kluzkém povrchu dává smysl upřednostnit minimalizaci zatáčení.

Výlet 

Tato úloha se vymyká tím, že modelování situace pomocí grafu není přímočaré. Matoucí je, že zachycujeme i vztahy mezi lidmi, kteří spolu nepojedou. Někteří studenti ji opravdu řeší pracněji, pomocí textových popisků. Znázornit situaci obrázkem je ovšem mnohem přehlednější a tím i přesvědčivější. Jasně např. ukáže, že vlastně řešíme dvě nezávislé skupinky.

Závěrečné poznámky

• Někteří studenti se mohou podivovat vztahu úloh (či dokonce grafů) k informatice. Odpověď je snadná: takové úlohy informatici opravdu řeší. Zde jsou značně zjednodušené jen pro účely výuky. Informatici se zabývají právě tím, jak řešit velké případy (např. s mnoha křižovatkami apod.), a jak k řešení efektivně využít počítač. Učí se to ale samozřejmě na případech malých. Dále lze uvést i „informatické“ příklady grafů, což by také mělo být dostatečně přesvědčivé (záleží hlavně na tom, co studenti od informatiky očekávají, ale najít či vymyslet příklady z dané oblasti jistě není těžké).