FPF:UIINK14 Teorie grafů - Informace o předmětu
UIINK14 Teorie grafů
Filozoficko-přírodovědecká fakulta v Opavězima 2024
- Rozsah
- 12/0/0. Přednáška 12 HOD/SEM. 6 kr. Ukončení: zk.
- Vyučující
- doc. RNDr. Luděk Cienciala, Ph.D. (přednášející)
- Garance
- doc. RNDr. Luděk Cienciala, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě - Omezení zápisu do předmětu
- Předmět je otevřen studentům libovolného oboru.
- Cíle předmětu
- V daném předmětu se studenti seznámí se základními pojmy, s důkazovými technikami a možnými aplikacemi teorie grafů.
- Výstupy z učení
- Student bude po absolvování předmětu schopen: - definovat důležité pojmy teorie grafů. - používat grafové algoritmy. - aplikovat získané poznatky na konkrétních příkladech.
- Osnova
- 1. Grafy a jednoduché grafy, stupeň vrcholu.
- 2. Podgrafy, reprezentace grafů pomocí matic, cesty, cykly, dosažitelnost, souvislost, souvislé, nesouvislé grafy, vzdálenost v grafu, excentricita vrcholu, průměr a poloměr grafu.
- 3. Stromy, třídy grafů.
- 4. Další třídy grafů - kompletní grafy, bipartitní a multipartitní grafy, izomorfismus, automorfismus. Vrcholová a hranová souvislost, bloky.
- 5. Párování, pokrytí, hranové barvení grafů, párování a pokrytí v bipartitních grafech, algoritmus hledající nesaturované alternující cesty.
- 6. Vrcholové barvení grafů, planární grafy.
- 7.-8. Problém 4 barev, Neplanární grafy, Eulerovské grafy, Úlohy typu bludiště - Tarryho algoritmus, Trémauxův algoritmus.
- 9. Hamiltonovské grafy, orientované grafy.
- 10. Orientované grafy, turnaje, sítě, toky a řezy.
- 11.-12. Algoritmus nalezení minimální kostry grafu, Primův algoritmus, Kruskalův, Obecné schéma prohledávání grafu, značkování vrcholů.
- 13. Prohledávání grafů do šířky, do hloubky, Backtracking.
- Výukové metody
- Přednáška s aktivizací
Cvičení - Metody hodnocení
- Zápočet: Povinná účast na cvičeních min. 75 %.
Písemná forma ověření studijních výsledků.
U zkoušky může student získat maximáně 60 bodů. Pro úspěšné ukončení je zapotřebí získat minimálně 30 bodů. - Další komentáře
- Studijní materiály
Předmět je dovoleno ukončit i mimo zkouškové období.
- Statistika zápisu (nejnovější)
- Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIINK14