UIMOIBK008 Teorie grafů

Filozoficko-přírodovědecká fakulta v Opavě
zima 2024
Rozsah
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 nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
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ů.
Předmět je zařazen také v obdobích zima 2020, zima 2021, zima 2022, zima 2023.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIMOIBK008