Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


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)


Co jsou grafy?

Grafy jsou matematické objekty popisující různé úlohy z reálného života pomocí bodů (tzv. vrcholů), které jsou pospojovány tzv. hranami.

Příklady grafů

typická využití grafů, matematická definice


Tyto stránky vznikly jako diplomová práce Matematicko-fyzikální fakultě Univerzity Karlovy v roce 2008-2010, studijní program Matematika, obor matematika zaměřená na vzdělávání.
Vedoucí: RNDr. Pavla Pavlíková, Ph.D.
Řešitel: Lukáš Jirovský (kontakt)
Informace o práci, PDF verze
Poslední aktualizace: 23. 9. 2010
Práce obhájena (Bc. část): 10. 9. 2008
Práce obhájena (Dipl. část): 16. 9. 2010

Osobní web autora, další projekty: tv program, sledování tv online, tv program (SK), zprávy z Prahy