Detail předmětu

Grafové algoritmy

FSI-9GRA Ak. rok: 2024/2025 Celoroční semestr

Předmět se zaměřuje na teorii grafů a seznamuje studenty s jejími základními pojmy a algoritmy. Zabývá se následujícími tématy: Reprezentace grafu v počítači. Časová složitost algoritmů. Datové struktury pro grafové algoritmy (binární halda, disjunktní množiny, ...).
Eulerovské tahy, hamiltonovské cesty. Prohledávání grafů (do šířky, do hloubky), backtracking, metoda větví a mezí. Souvislost a dosažitelnost. Nejkratší cesty.
Síťové grafy. Stromy a kostry. Steinerovy stromy. Základy počítačové geometrie – grafy viditelnosti, Voroného diagramy a Delaunayho triangulace. Toky v sítích. Barvení grafů. Párování v grafech.

Jazyk výuky

čeština

Vstupní znalosti

Ke studiu grafových algoritmů postačují základní znalosti z teorie množin, kombinatoriky a operačního výzkumu.

Pravidla hodnocení a ukončení předmětu

Podmínkou pro absolvování předmětu je textové zpracování nebo implementace netriviálního grafového algoritmu na počítači. Zkouška má písemnou formu. Studenti v ní prokazují znalosti pojmů a základních algoritmů.

Učební cíle

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 řešit pomocí grafových algoritmů.

Použití předmětu ve studijních plánech

Program D-APM-P: Aplikovaná matematika, doktorský, doporučený kurs

Program D-APM-K: Aplikovaná matematika, doktorský, 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.