UIN1004 Teorie grafů I

Filozoficko-přírodovědecká fakulta v Opavě
zima 2015
Rozsah
2/2/0. 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í)
Mgr. Jan Drastik, Ph.D. (cvičící)
Mgr. Martina Foldynová (cvičící)
Mgr. Adam Kožaný (cvičící)
Mgr. Marek Menšík, Ph.D. (cvičící)
RNDr. Michal Perdek (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
předmět má 7 mateřských oborů, zobrazit
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 1993, zima 1994, zima 1995, zima 1996, zima 1997, zima 1998, zima 1999, zima 2002, zima 2003, zima 2004, zima 2005, zima 2006, zima 2007, zima 2008, 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.