FPF:UIINP14 Teorie grafů - Informace o předmětu

UIINP14 Teorie grafů

Rozsah

2/2/0. 6 kr. Ukončení: zk.

Vyučující

doc. RNDr. Luděk Cienciala, Ph.D. (přednášející)
RNDr. Radka Poláková, Ph.D. (cvičící)

Garance

doc. RNDr. Luděk Cienciala, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě

Rozvrh

Po 9:45–11:20 B1

• Rozvrh seminárních/paralelních skupin:

UIINP14/A: St 18:55–20:30 B4, R. Poláková

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

• Informatika (program FPF, INFOR-bpk)
• Matematické metody a modelování (program MU, Bc-M)
• Matematické metody v ekonomii (program MU, Bc-M)
• Matematické metody v krizovém řízení (program MU, Bc-M)
• Obecná matematika (program MU, Bc-M)

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/UIINP14