11. cvičení: Průzkum grafů

0:00 Plán této a následující hodiny. Cca 30 minut další hodiny bude látka. Úvodní odpovědník na všechno. Možnosti pak:
- Konzultace.
- Honza připraví písemkové příklady.
- Jdeme dom.
- Něco jiného? Ať si to rozmyslí během odpovědníku.
0:01 Odpovědník.
0:08 Hlasování plán další hodiny. Výzva: dejte učení alespoň 4 hodiny jako na zkoušku. Projděte si sbírku, slidy, chápejte všechny algoritmy. Kdo je ochoten do toho jít?
0:10 Pojmy.
0:25 11.1: zápis grafu. Každý sám.
0:30 11.2: otázky. Promítnout zadání, nechat 2 minuty, po minutě dát možnosti, pak se ptát. Možnosti: $n$, $n^2$, $(n 2)$, $n-1$, $n/2$, $n-2$, $n+1$, $n!$.
0:40 11.3: otázky II. Zeptat se.
0:45 11.4a: BFS. Dát papíry do dvojic, nechat barvit vrcholy. Pak udělat společně.
1:00 11.4c: DFS. Dát papíry do dvojic, nechat psát časové známky. Pak udělat společně.
1:15 11.4defg: jednoduše se ptát.
1:25 11.5: hledání protipříkladů. Dvojice.

Další příklady ponechány na další cvičení.

Říct studentům, ať fakt jsou na příští přednášku, že je třeba, aby uměli algoritmy Bellmann-Ford a Dijkstra.

Vynecháno