UINK104 Teorie grafů I

Filozoficko-přírodovědecká fakulta v Opavě
zima 2014
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
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 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022.