FPF:UIBUC21 Teorie grafů - Informace o předmětu
UIBUC21 Teorie grafů
Filozoficko-přírodovědecká fakulta v Opavězima 2021
- Rozsah
- 2/2/0. 5 kr. Ukončení: zk.
- Vyučující
- doc. RNDr. Luděk Cienciala, Ph.D. (přednášející)
doc. RNDr. Lucie Ciencialová, Ph.D. (cvičící)
Mgr. Ondřej Mazurek (cvičí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 8:05–9:40 B1
- Rozvrh seminárních/paralelních skupin:
- 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 (dvouoborové) (program FPF, B1803 InDO)
- 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.
- 1. Grafy a jednoduché grafy, stupeň vrcholu.
- Literatura
- doporučená literatura
- Cienciala, L., Ciencialová, L. Teorie grafů a grafové algoritmy. Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-060-3. info
- Even, S., Even, G. Graph algorithms, 2nd edition. New York Cambridge University Press, 2012. ISBN 978-0-521-51718-8. info
- Bondy, A., Murty, U. S. R. Graph Theory. Springer, 2011. info
- Merris, R. Graph Theory. New York : John Wiley, 2001. ISBN 0-471-38925-0. info
- 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
- Teoretické a praktické zvládnutí témat předmětu, podmínky budou upřesněny na začátku výuky.
U zkoušky může student získa maximáně 60 bodů. Pro úspěšné ukončení je zapotřebí získat minimálně 30 bodů. - Další komentáře
- Předmět je dovoleno ukončit i mimo zkouškové období.
- Statistika zápisu (nejnovější)
- Permalink: https://is.slu.cz/predmet/fpf/zima2021/UIBUC21