UINK104 Teorie grafů I

Filozoficko-přírodovědecká fakulta v Opavě
zima 2015
Rozsah
Přednáška 6 HOD/SEM, Cvičení 6 HOD/SEM. 6 kr. Ukončení: zk.
Vyučující
doc. RNDr. Luděk Cienciala, Ph.D. (přednášející)
doc. RNDr. Luděk Cienciala, Ph.D. (cvičí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ů.
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 multi-partitní 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. Problém 4 barev, Neplanární grafy, Eulerovské grafy, Úlohy typu bludiště - Tarryho algoritmus, Trémauxův algoritmus.
    8. Hamiltonovské grafy, orientované grafy.
    9. Orientované grafy, turnaje, sítě, toky a řezy.
    10. Algoritmus nalezení minimální kostry grafu, Primův algoritmus, Kruskalův, Obecné schéma prohledávání grafu - značkování vrcholů.
    11. Prohledávání grafů do šířky, do hloubky, Backtracking.
Literatura
    doporučená literatura
  • Fronček, D. Úvod do teorie grafů. Opava, FPF SU, 2000. info
  • Bollobas, B. Modern Graph Theory. New York, Springer, 1998. info
  • Diestel, R. Graph Theory. New York, Springer, 1997. info
  • Demel, J. Grafy. Praha, SNTL, 1988. info
  • Kolář, J. Grafy. Praha, ČVUT, 1984. info
  • Kolář, J. Grafy - cvičení. Praha, ČVUT, 1984. info
  • Bosák, J. Grafy a ich aplikácie. Bratislava, Alfa, 1980. info
  • Behzad, M., Chartrand, G. Graphs and Digraphs. Weber, Schmidt, 1979. info
  • Bondy, J. A. Graph Theory with Applications. The Macmillan Press, 1976. info
Výukové metody
Přednáška s aktivizací
Přednáška s analýzou videozáznamu
Metody hodnocení
Zkouška
Informace učitele
Student prezenčního studia píše v rámci cvičení dva zápočtové testy bodované maximálně 20 body za každý. K získání zápočtu je zapotřebí 20 bodů. V rámci semestru mohou studenti získat prémiové body.
Zkouška se skládá ze dvou částí. První část: jednoduchý test obsahující 10 otázek. K úspěšnému zvládnutí testu je potřeba alespoň 7-krát zodpovědět správně. Pouze studenti úspěšní v tomto testu mohou obdržet zadání druhé části. Druhá část se skládá z pěti otázek, každá je bodována maximálně 10 body. K počtu bodů získaných ve druhé části se studentovi připočítává 10 bodů z části první. Celkem je tedy ze zkouškové písemky možno získat 60 bodů. Pro úspěšné vykonání je potřeba získat 30 bodů. Známka je stanovena součtem bodů za zkoušku a bodů, které student získal v rámci semestru.

Hodnocení

Prezenční studium Kombinované studium
A 100 - 91 60 - 55
B 90 - 81 54 - 49
C 80 - 71 48 - 43
D 70 - 61 42 - 37
E 60 - 50 36 - 30
F 49 - 0 29 - 0
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 2009, zima 2010, zima 2011, zima 2012, zima 2013, zima 2014, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022.