Teorie grafů

Zkratka předmětu KMI/KTG
Název předmětu Teorie grafů
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/KTG
Název Teorie grafů
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 18 HOD/SEM
Vyučovací jazyk čeština
Nahrazovaný předmět
Vyloučené předměty
Podmiňující
Způsob zakončení Zkouška
Forma zakončení Kombinovaná
Zápočet před zkouškou Ano
Vyučovaný semestr Zimní
Cíle předmětu (anotace)

První část kurzu je zaměřena na základy teorie grafů, včetně vybraných grafových algoritmů. Dále je podána teorie
vytvořujících funkcí s aplikacemi na slovní příklady a také řešení diferenčních rovnic.

Požadavky na studenta

Aktivní účast na cvičeních, napasání dvou zápočtových testů k zápočtu.
Složení kombinované zkoušky (na více než 50%), písemná část na 80 minut, tři příklady.

Obsah

První část kurzu je zaměřena na základy teorie grafů, včetně vybraných grafových algoritmů. Dále je podána teorie vytvořujících funkcí s aplikacemi na slovní úlohy a také řešení diferenčních rovnic.
1. Definice grafu, základní příklady a typy grafů, grafový isomorfismus, representace grafů.
2. Skóre grafu, princip sudosti, věta o skóre.
3. Cestování v grafu, princip sudosti, věta o skóre.
4. Souvilost grafu.
5. Jednotažky, Eulerovské grafy.
6. Stromy, definice, charakterizace stromů, kódování stromů.
7. 8. Kostry grafů, Kruskalův a Jarníkův algoritmus.
9. Rovinné grafy, Eulerův vzorec, problém 4 barev.
10. Vytvořující funkce a jejich aplikace v kombinatorice.
11. Další příklady aplikací vytvořujících funkcí.
12. Náhodná schémata a střední složitost algoritmů.
13. Rekurentní vztahy.
14. Shrnutí.

Předpoklady - další informace k podmíněnosti studia předmětu

Student musí znát základy kalkulu a diskrétní matematiky.
Prerekvizita: KMI/DMI nebo KMI/DMIA Diskrétní matematika

Získané způsobilosti

Student je schopen kombinatoricky myslet a řešit úlohy teoritické i aplikované.

Garanti a vyučující
  • Garanti: Mgr. Tomáš Roskovec, Ph.D.
  • Přednášející: Mgr. Tomáš Roskovec, Ph.D., RNDr. Filip Soudský, Ph.D.
  • Cvičící: RNDr. Filip Soudský, Ph.D.
Literatura
  • Matoušek, J., Nešetřil, J. Kapitoly z diskrétní matematiky. Praha: Karolinum, 2007. ISBN 978-80-246-1411-3.
  • Nýdl, V. Diskrétní matematika v příkladech, díl 2. České Budějovice: PF JU, 2007.
  • Matoušek, J., Nešetřil, J. Invitation to Discrete Mathematics. New York: Oxford University Press, 2008. ISBN 978-0-19-857043-1.
Vyučovací metody

Monologická (výklad, přednáška, instruktáž), Dialogická (diskuze, rozhovor, brainstorming)

Hodnotící metody

Kombinovaná zkouška

Stáhnout jako PDF