Ú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 (graf, vrchol/uzel, hrana/spoj). 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. Není cílem se je všechny naučit! Pojmy mají studentům usnadnit vzájemné porozumění. Zavádíme jen ty pojmy, které jsou v dané situaci (pro řešenou úlohu, probíhající diskuzi...) právě potřeba.

Ve větších třídách bude několik skupinek řešit stejné úlohy. To u tabule nabídne ještě jedno pozorování: budou mít různé nákresy, ale se stejnou strukturou. Nemělo by to ale být důsledkem opisování, pokud je to v dané třídě potřeba, zkusíme tomu předejít např. využitím otvíracích křídel tabule.

Zároveň studentům představíme, co už taktéž intuitivně používají, totiž modelování. K řešeným úlohám se 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. Applet záměrně ukazuje jen koleje A a B (nikoliv kam vedou) v záměrně spletité síti. Řešit úlohu metodou pokus-omyl je poněkud frustrující. Právě to ale studenty přiměje hledat způsob, jak si řešení usnadnit. Obvykle si začnou vytvářet improvizovaný plánek nebo tabulku. 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.

Někteří žáci mají potíž se správným porozuměním větě „Z vrátnice vede po jedné chodbě do šatny, skladu i kantýny“, proto jsme ji v zadání ponechali.

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. Pozorní studenti si také všimnou, že úloha má více řešení, Karel mohl být dědečkem Daniely několika způsoby - přes dceru Ilonu, nebo přes jiné své dítě, o němž nevíme. Hanka a Daniela tak mohou být sestrami nebo sestřenicemi. Adam je tak buď Danieliným synovcem, nebo prostě synem její sestřenice. Pro tu druhou možnost ustálené pojmenování nemáme.

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 minimalizovat 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. Některé studenty pomohou přesvědčit „informatické“ příklady grafů (propojení v počítačových sítích, logické obvody, adresářová struktura, odkazy mezi webovými stránkami, umělé neuronové sítě, UML diagramy a řada dalších). Záleží hlavně na tom, co studenti od informatiky očekávají.
• Některým studentům je jedno, jestli grafy souvisí s informatikou, ale ptají se, k čemu je to dobré. Úvodní úlohy hodnotí (správně) jako banální. Může pomoci najít úlohy související s oborem studia nebo s jejich konkrétními zájmy. Poměrně univerzální aplikací je síť návazností úkolů (zalívám až potom, co zaseju). Uplatní se jak pro běžné každodenní pracovní úkoly, tak pro komplexní projekty.
• Dále se studenti mohou podivovat použití samotného pojmu graf, když graf je přece graf funkce v matematice, popř. vizualizace hodnot v tabulkovém kalkulátoru. Jakkoliv je to matoucí, v všech uvedených kontextech je pojem graf běžně užíván. Nemá proto smysl pojem nějak obcházet, studenti se musí naučit kontext rozpoznat. Graf a graf funkce spolu sice konceptuálně úzce souvisí (obojí je množina dvojic prvků, které jsou ve vzájemném vztahu), to je ale pro studenty příliš abstraktní a zpravidla je lepší tím situaci nezatemňovat.