Detail předmětu
Grafové algoritmy
FSI-9GRA Ak. rok: 2026/2027 Celoroční semestr
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Prerekvizity
Plánované vzdělávací činnosti a výukové metody
Způsob a kritéria hodnocení
Jazyk výuky
čeština
Cíl
Cílem předmětu je seznámit studenty s teorií grafů a jejími algoritmy, které rozšiřují znalosti získané v předmětech se zaměřením na umělou inteligenci, operační výzkum, projektové řízení a počítačové sítě, a mají aplikace v technických i jiných oblastech.
Studenti získají základní znalosti z teorie grafů a grafových algoritmů. Budou tak schopni modelovat pomocí grafů různé problémy z praxe a ty pak pomocí grafových algoritmů řešit .
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Použití předmětu ve studijních plánech
Program D-APM-P: Aplikovaná matematika, doktorský
obor ---: bez specializace, 0 kredity, doporučený kurs
Typ (způsob) výuky
Přednáška
20 hod., nepovinná
Osnova
1. Definice grafu a základní pojmy.
2. Reprezentace grafu v počítači.
3. Časová a paměťová složitost algoritmů.
4. Prohledávání grafů, backtracking, metoda větví a mezí.
5. Aplikace úloh o cestách, nejkratší cesty, síťové grafy.
6. Eulerovské tahy, hamiltonovské cesty a kružnice.
7. Komponenty souvislosti, stromy a kostry.
8. Steinerovy stromy.
9. Voronoiovy diagramy, Delaunayho triangulace.
10. Barvení grafů, kliky.
11.-12. Toky v sítích.
13. Párování grafech.