Teorie grafů

Garant předmětu:

Lucie Kárná

Přednášející:

Lucie Kárná

Cvičící:

Lucie Kárná

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

Základní grafové pojmy, formalizace popisu grafů, způsoby reprezentace grafu. Úlohy teorie grafů, instance, zadání. Prohledávání grafu, minimální kostra grafu, stromy, nejkratší dráha, Eulerovské tahy, párování v bipartitních grafech, toky v sítích, cirkulace, kritická cesta, úloha obchodního cestujícího. Algoritmy řešení existenčních a optimalizačních úloh. Výpočetní složitost, přístup k řešení NP-těžkých úloh, heuristické postupy.

Požadavky:

Znalost základních pojmů z teorie grafů.

Osnova přednášek:

Osnova cvičení:

Cíle studia:

Student prohloubí své znalosti z teorie grafů. Seznámí se se základními pojmy a problémy z oblasti algoritmizace úloh. Setká se s klasickými úlohami teorie grafů a algoritmy pro jejich řešení. Nahlédne do problematiky časové náročnosti a efektivity algoritmů.

Studijní materiály:

Demel, J: Grafy a jejich aplikace, Praha, Academia, 2002

Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Praha, Karolinum, 2009

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. TET-LOG prezenční od 2022/23 (povinně volitelný předmět)
• Bc. TET-DOS prezenční od 2022/23 (povinně volitelný předmět)
• Bc. TET-ITS prezenční od 2022/23 (povinně volitelný předmět)
• Bc. TET-LED prezenční od 2022/23 (povinně volitelný předmět)
• Bc. TET-DOS prezenční od 2023/24 (povinně volitelný předmět)
• Bc. TET-LOG prezenční od 2023/24 (povinně volitelný předmět)
• Bc. TET-ITS prezenční od 2023/24 (povinně volitelný předmět)
• Bc. TET-LED prezenční od 2023/24 (povinně volitelný předmět)
• Bc. TET-DOS prezenční od 2024/25 (povinně volitelný předmět)
• Bc. TET-ITS prezenční od 2024/25 (povinně volitelný předmět)
• Bc. TET-LED prezenční od 2024/25 (povinně volitelný předmět)
• Bc. TET-LOG prezenční od 2024/25 (povinně volitelný předmět)