Teorie grafů

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

Úvod

• Využití grafů
• Historie teorie grafů

Základní pojmy

• Matematická definice grafu
• Úplný graf
• Bipartitní graf
• Podgraf
• Isomorfismus
• Cesta a souvislost grafu
• Kružnice (cyklus) v grafu
• Stupně vrcholů (skóre)
• Matematická reprezentace grafu
• Reprezentace grafu v počítači
• Orientované grafy
• Vzdálenost / metrika
• Stromy
• Kostra grafu
• Jádro grafu

Vybrané problémy

• Nejkratší cesta
• Minimální kostra
• Maximální kostra
• Počty koster
• Alkany
• Jednotažky
• Barvení mapy
• Relace
• Výroky
• Rozvrh
• Převozník
• Toky v sítích
• Teorie her
• Hra NIM

Procvičování

• Základní pojmy
• Minimální kostra
• Maximální kostra
• Počty koster
• Jednotažky
• Váhy a závaží
• Přelévání mléka
• Otáčení skleniček
• Barvení mapy
• Kamarádi
• Malíř a míchání barev
• Rozvrh
• Maximální tok
• Jádro grafu
• Výhra NIMu