UIDI012 Grafy a grafové algoritmy

Filozoficko-přírodovědecká fakulta v Opavě
léto 2009
Rozsah
0/0. 0 kr. Ukončení: dzk.
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
1. Grafy a podgrafy. Grafy a jednoduché grafy, izomorfismus grafů. Podgrafy, stupeň vrcholu. Incidenční matice a matice sousednosti. Cesty a cykly. 2. Důležité třídy grafů. Souvislé a nesouvislé grafy. Kompletní grafy, bipartitní a multi-partitní grafy. Stromy, kostra grafu. 3. Vrcholová a hranová souvislost grafů. 4. Hranové a vrcholové barvení grafu. Hranové barvení, chromatický index grafu, Vizingova věta. Vrcholové barvení, chromatické číslo grafu. Brooksova věta. 5. Rovinné a planární grafy. 6. Reprezentace grafů - graficky, maticově, seznamem hran nebo seznamem vrcholů a jejich sousedů; volba reprezentace grafu v závislosti na aplikaci. 7. Algoritmy prohledávání grafů. 8. Topologické uspořádání vrcholů a hran - užití topologického uspořádání k hledání nejkratších cest; test acykličnosti grafu. 9. Komponenty souvislostí; Floydův algoritmus - testování existence cyklů se zápornou cenou. 10. Kostra grafu - Jarníkův a Borůvkův algoritmus. Souvislost s nejkratšími cestami v neorientovaném grafu. 11. Párování v bipartitních grafech - maximální párování, nejlevnější párování v bipartitních grafech. Maximální párování v obecných grafech - redukce grafu. 12. Toky v sítích, maximální tok - ekvivalence úlohy maximálního párování v bipartitním grafu a maximálního toku v specifické síti; Ford - Fulkersonův algoritmus; přípustný tok v síti. Odborná literatura: 1. Behzad, M. - Chartrand, G. - Lesniak-Foster, L.: Graphs and Digraphs. Prindle: Weber & Schmidt, 1979. 2. Bollobas, B.: Modern Graph Theory. New York: Springer, 1998. 3. Bondy, J. A. - Murty, U. S. R.: Graph Theory with Applications. The Macmillan Press, 1976. 4. Bosák, J.: Grafy a ich aplikácie. Bratislava: Alfa, 1980. 5. Demel, J.: Grafy. Praha: SNTL, 1988. 6. Diestel, R.: Graph Theory. New York: Springer, 1997. 7. Fronček, D.: Úvod do teorie grafů. Opava: FPF SU, 2000. 8. Kolář, J.: Grafy - cvičení. Praha: ČVUT, 1984. 9. Kolář, J.: Grafy. Praha: ČVUT, 1984.
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 2006, léto 2007, zima 2007, léto 2008, zima 2008, zima 2009, léto 2010, zima 2010, léto 2011, zima 2011, léto 2012, zima 2012, léto 2013, zima 2013, léto 2014, zima 2014, léto 2015, zima 2015, léto 2016, zima 2016, léto 2017, zima 2017, léto 2018, zima 2018, léto 2019, zima 2019, léto 2020, zima 2020, léto 2021, zima 2021, léto 2022.