Předmět Grafy a grafové algoritmy (UI / DI012)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu UI / DI012 - Grafy a grafové algoritmy, Filozoficko-přírodovědecká fakulta, Slezská univerzita v Opavě (SU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
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.
Získané způsobilosti
Teoretické porozumění tématům obsahového vymezení předmětu. Praktické dovednosti při práci s jednotlivými tématy.
Literatura
Demel, J. Grafy. Praha, SNTL, 1988. Kolář, J. Grafy. Praha, ČVUT, 1984. Kolář, J. Grafy - cvičení. Praha, ČVUT, 1984. Bosák, J. Grafy a ich aplikácie. Bratislava, Alfa, 1980. Diestel, R. Graph Theory. New York, Springer, 1997. Bondy, J. A. Graph Theory with Applications. The Macmillan Press, 1976. Behzad, M., Chartrand, G. Graphs and Digraphs. Weber, Schmidt, 1979. Bollobas, B. Modern Graph Theory. New York, Springer, 1998. Fronček, D. Úvod do teorie grafů. Opava, FPF SU, 2000.
Požadavky
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ů.
Garant
RNDr. Luděk CIENCIALA, Ph.D.