FPF:UIDI012 Grafy a grafové algoritmy - Informace o předmětu
UIDI012 Grafy a grafové algoritmy
Filozoficko-přírodovědecká fakulta v Opavězima 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
- Autonomní systémy (program FPF, P1801 Inf)
- 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í.
- Statistika zápisu (zima 2009, nejnovější)
- Permalink: https://is.slu.cz/predmet/fpf/zima2009/UIDI012