Úvodní slovo pro učitele

Možná si říkáte, proč vznikla tato sada materiálů k výuce teorie grafů? Vždyť dnes existuje celá řada online zdrojů a dokonce i dvě pěkné české online učebnice! To je sice pravda, ale narážel jsem v praxi při použití těchto zdrojů na zásadní překážky. Především mi chyběl formát ucelených, metodicky promyšlených lekcí, které by na sebe logicky navazovaly a které by učitel mohl rovnou vzít a použít v hodině. Stávající materiály navíc často oscilují mezi dvěma extrémy – buď se utápějí v těžké vysokoškolské matematice, nebo naopak matematický a algoritmický základ opomíjejí.

Mým cílem proto bylo najít „stravitelný kompromis“, který by byl ideální pro věkovou skupinu žáků druhých ročníků gymnázia. Snažil jsem se také najít silnější a explicitní přesah do jiných oborů, než jsou doprava a počítačové sítě, především do přírodních věd (biologie, chemie, farmacie, medicína, …).

Zvolený koncept – tedy vždy jen krátký teoretický úvod doplněný o praktické úlohy s autorským klíčem – se mi v reálné výuce velmi osvědčil. Žákům umožňuje pracovat do velké míry samostatně a vlastním tempem. Tím nejdůležitějším efektem ale bylo přesunutí těžiště hodiny z pouhého „řešení příkladů“ k hlubší společné diskusi nad výsledky. Žáci oceňovali jak již zmiňované mezioborové přesahy, tak nutnost neustále zapojovat kritické myšlení – brzy totiž zjistili, že ani v předloženém klíči nemusí být vše správně, anebo že těch „správných“ možností může být více.

Tyto lekce jsou primárně určeny žákům na gymnáziu (druhý ročník/sexta). V rámci zadání žákovských úloh a následujícího klíče k jejich řešení jsou v některých případech záměrně uvedeny zavádějící či nejednoznačné informace a někdy též chyby. Pokud se v dané lekci taková chyba vyskytuje, mají ji pozorní žáci odhalit. To dává žákům možnost pracovat s chybou a kriticky zhodnotit, jestli výsledek vůbec dává smysl.

Součástí pracovního listu by vždy měla být reflexe žáka k jednotlivým úlohám a celkové hodnocení své práce. Zde by měl žák pracovat se svojí chybou a diskutovat, proč k ní došlo a zda při porovnání s klíčem byla chyba odhalena a pochopeno správné řešení (které ale někdy nemusí být správné, nebo jediné správné). Jednou z možností technického uspořádání lekcí je zadávat práci v běžném LMS (např. MS Teams, Google Classroom, Moodle) a jako součást odevzdané práce požadovat samostatný dokument s reflexí k jednotlivým úlohám a celkové zhodnocení práce.

Doporučené rozvržení výuky (jedna lekce = 2 × 45 min)

1. (Společná reflexe k předchozí lekci. Odhalení chyb a nejednoznačných/problematických míst v rámci zadání i klíče k řešení.) – cca 15 min
2. Teoretický úvod nové lekce – cca 10 min
3. Představení jednotlivých úkolů – cca 5 min
4. Samostatná práce na úkolech (některé vyžadují diskusi ve dvojici, či ve skupině) – cca 50 min
5. Sepsání reflexe a hodnocení – 10 min

• Lekce 1: Úvod do modelování a grafů (Mermaid)
  • Úloha 1: Brainstorming – Hledání grafů a sítí v běžném životě (sítě, rodokmeny, doprava).
  • Úloha 2: První kroky v Mermaid – Kódování jednoduchých chemických modelů (voda a methan).
  • Úloha 3: Záhada Königsberských mostů – Abstrahování historické mapy Královce do uzlů/hran a Eulerův tah.
  • Úloha 4: DofE expedice na Vysočině – Hledání optimální trasy přes skalní vrcholy (topologie vs. geometrie).
• Lekce 2: Typy grafů a jejich využití
  • Úloha 1: Matice – Převod z matice na graf s chytákem v klíči (odhalení dokonale symetrické matice = neorientovaný graf).
  • Úloha 2: Krebsův cyklus – Kódování orientovaného cyklického grafu a řešení abstrakce (vedlejší produkty jako uzly vs. vlastnosti hran).
  • Úloha 3: Optimalizace výroby (CPM) – Kreslení orientovaného acyklického grafu (DAG), hledání kritické cesty a práce s časovou rezervou (dynamika sítě).
  • Úloha 4: Laboratorní rotace – Bipartitní graf a hledání optimálního párování (studenti vs. přístroje).
• Lekce 3: Stromy a rozhodovací procesy
  • Úloha 1: Naše zoologická zahrada – Tvorba taxonomického stromu zvířat a počítání evolučních vzdáleností (zjednodušený model vs. odborný strom).
  • Úloha 2: Duel (První polovina / druhá polovina) – Fyzická ukázka hrubé síly (lineární hledání) vs. efektivního algoritmu (binární vyhledávání).
  • Úloha 3: Fylogeneze virů – Aglomerativní shlukování (UPGMA) zdola nahoru podle matice mutací.
  • Úloha 4: Třídění (Triage) na urgentním příjmu – Záchranářský rozhodovací strom, formální syntaxe a prevence vizuálního křížení uzlů.
• Lekce 4: Vážené grafy a minimální kostra
  • Úloha 1: Čtení vážené matice – Převod matice vzdáleností (města K, L, M, N) na graf a hledání minimální kostry „od oka“.
  • Úloha 2: Angiogeneze (Růst cév) – Propojování tkáně (Kruskalův hladový algoritmus) a práce s biologickou miskoncepcí (difúze).
  • Úloha 3: Fragment-Based Drug Design – Návrh léku aplikací algoritmu čistě na čísla v matici bez nutnosti nakresleného obrázku (čistá abstrakce).
  • Úloha 4: Odolnost vs. cena sítě – Úprava molekuly (nebo IT sítě) pro přidání redundance (malý kruh vs. absolutně odolný velký kruh F3-F4).
• Lekce 5: Analýza sítí a centrality
  • Úloha 1: Hledání „hubů“ v ekologii – Potravní síť louky, výpočet Degree Centrality a diskuse o dopadu vyhynutí myši.
  • Úloha 2: Mosty a metabolické dráhy – Hledání slabého místa (Betweenness Centrality) pro cílený lék proti parazitovi.
  • Úloha 3: Epidemiologická strategie – Očkování v nejednoznačné síti třídy (Cílená vakcinace hubů) a diskuse o způsobu šíření chřipky.
  • Úloha 4: Matice osudu – Násobení matice sousednosti sama se sebou pro predikci šíření virálních informací ve dvou krocích.
• Lekce 6: Expertní sítě (Gephi Lite)
  • Úloha 1: Bídníci z pohledu datového vědce – Analýza literárního díla bez čtení (Digital Humanities), komunity a centralita hlavních hrdinů.
  • Úloha 2: Letecké sítě – Práce s obřími daty, vizualizační algoritmus ForceAtlas2 a pochopení rozdílu mezi topologií sítě a reálnou geografií.

V průběhu lekcí budeme používat především aplikaci Mermaid.live. V závěrečné lekci pak sáhneme po aplikaci Gephi Lite. Obě tyto aplikace jsou k dispozici online a v době tvorby těchto lekcí zdarma.

Obr.1: Online aplikace Mermaid.live je intuitivní se spoustou příkladů a pěknou online dokumentací.

Obr.2: Online aplikace Gephi Lite je použita v závěrečné 6. lekci k analýze dvou datových souborů - postavy z románu Bídnící a data z leteckého provozu.

Jsem si plně vědom, že teorie grafů a komplexních sítí je obrovská a hluboká disciplína. Aby tento kurz zůstal pro žáky 2. ročníků a sext stravitelný a abychom si vystačili s běžnou hodinovou dotací, museli jsme vytyčit jasné hranice a některé – byť nesmírně zajímavé – okruhy vědomě vynechat. V této sadě lekcí se proto záměrně nevěnujeme například:

• Tokům v sítích (Network Flows): Úlohy zaměřené na maximální propustnost sítě (např. výpočet toho, kolik aut maximálně projede silniční sítí města nebo kolik dat reálně proteče optickým kabelem).
• Barvení grafů (Graph Coloring): Zajímavá a vysoce praktická oblast využívaná při sestavování školních rozvrhů, přidělování frekvencí mobilním operátorům nebo při řešení slavného problému čtyř barev na mapě.
• Formálním algoritmům pro nejkratší cestu: Ačkoliv se v lekcích dotýkáme problému obchodního cestujícího a heuristiky, detailní implementaci Dijkstrova algoritmu nebo procházení grafu do šířky/hloubky (BFS/DFS) jsme přenechali pokročilejším kurzům :-).
• Pokročilé topologii a teorii her: Vynechali jsme například detailní rozklad sítí (hledání jádra grafu) či aplikace strategického rozhodování (teorie her) uvnitř síťových struktur.

Tyto vynechané oblasti však mohou vytvářet vynikající odrazový můstek pro rozšiřující studium nadanějších žáků (např. v rámci SOČ) nebo mohou posloužit jako nosná témata pro navazující volitelné informatické či matematické semináře.

• https://teorie-grafu.cz
• https://popelka.ms.mff.cuni.cz/~lessner/mw/index.php/Učebnice/Grafy
• https://www.umimeinformatiku.cz/cviceni-modelovani-grafy
• https://www.ibobr.cz/ucebnice
• https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf (Jiří Demel: Grafy a jejich aplikace, 2019)
• https://www.radekpelanek.cz/dokumenty/ms-web.pdf (Radek Pelánek: Modelování a simulace komplexních systémů, 2011)
• Série videí (YouTube)
• Kurz Model Thinking (YouTube) / Coursera