Teorie grafů

Teorie grafů ve výuce na střední škole

Vítejte na webových stránkách poskytujících základní úvod do teorie grafů. Jejich primárním cílem je poskytnout všechny základní informace a popisy algoritmů pro využití např. na matematickém semináři nebo ve výuce programování na středních školách, užitečné mohou být ale i pro studenty vysokých škol. Důraz je kladen převážně na co nejjednodušší popis "principu fungování" a na představení širokých možností využití teorie grafů s ohledem na úroveň znalostí studentů gymnázií.

1. Úvod

Využití grafů, historie teorie grafů

2. Základní pojmy

Co je to graf matematicky?, pojmy: úplný, bipartitní, podgraf, isomorfismus, cesta, souvislost, kružnice (cyklus), stupně vrcholů, skóre grafu, matematická reprezentace grafu, reprezentace grafu v počítači, orientované grafy, vzdálenost, metrika, stromy, kostra grafu, jádro grafu

3. Vybrané problémy

Hledání nejkratší cesty v grafu, hledání minimální kostry, maximální kostra, počty koster v grafu, alkany, jednotažky (eulerovské grafy), barvení mapy, relace, výroky, rozvrh, převozník, toky v sítích, teorie her, hra NIM (odebírání sirek)

4. Procvičování

Základní pojmy, hledání minimální kostry, hledání maximální kostry, počty koster v grafu, jednotažky (eulerovské grafy), barvení mapy, kamarádi, váhy a závaží, přelevání mléka, otáčení skleniček, malíř a míchání barev, rozvrh, hledání maximálního toku, nalezení jádra grafu, výhra NIMu (teorie her)