Teorie grafů

Vybrané problémy z teorie grafů ve výuce na střední škole

Vítejte na webových stránkách poskytující základní úvod do teorie grafů. 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 VŠ. Důraz je však kladen spíše na co nejjednodušší popis "principu fungování" než na matematické důkazy správnosti algoritmů apod.

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

3. Vybrané problémy

Hledání nejkratší cesty v grafu, hledání minimální kostry, počty koster v grafu, alkany, jednotažky (eulerovské grafy), barvení mapy

4. Procvičování

Základní pojmy, hledání minimální kostry, počty koster v grafu, jednotažky (eulerovské grafy), barvení mapy, kamarádi