Předmět Grafové algoritmy (KMA / GRAFA)
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 KMA / GRAFA - Grafové algoritmy, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).
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
Předpokládaný semestrální plán:1.ZÁKLADNÍ POJMY;Grafy a jejich vlastnosti, zadávání grafů, důležité typy podgrafů - cesta, sled, komponenta, faktor, strom, kostra, pravidelné grafy.2.ZÁKLADNÍ GRAFOVÉ ALGORITMY; Pojem grafových algoritmů. Značkovací algoritmy, Backtracking, hledání nejkratší cesty.3.ZÁKLADNÍ GRAFOVÉ ALGORITMY; Hledání nejkratší cesty v ohodnoceném grafu, hledání maximální kostry grafu, určování počtu koster grafu, využití matice sousednosti.4.PÁROVÁNÍ; Párování v obecných grafech.5.PÁROVÁNÍ; Párování v bipartitních grafech.6.EULEROVSKÉ GRAFY; Eulerovské grafy, úloha čínského pošťáka.7.HAMILTONOVSKÉ GRAFY; Hamiltonovské cesty a kružnice (obecně).8.HAMILTONOVSKÉ GRAFY; Hledání nejkratší neorientované Hamiltonovské cesty a kružnice.9.BAREVNOST NEZÁVISLOST, KLIKY; Základní pojmy, určování barevnosti grafu.10.BAREVNOST NEZÁVISLOST, KLIKY; Kombinatorické pojmy a jejich vztahy. Hledání maximální nezávislé množiny.11.SÍTĚ A TOKY V SÍTÍCH; Základní pojmy, značkovací procedura.12.SÍTĚ A TOKY V SÍTÍCH; Algorimus pro maximální tok, algoritmus pro přípustnou cirkulaci.13.Předtermín, opravný termín pro průběžný test
Získané způsobilosti
rozvíjí orientaci v oblasti teorie grafůzná algoritmické postupy pro řešení základních typů úloh (prohledávání grafů, eulerovské a hamiltonovské grafy, párování, barevnost, sítě a toky)umí ilustrovat získané znalosti na konkrétních příkladechdokáže aplikovat algoritmické postupy na řešení konkrétních úlohupevňuje si schopnost samostaté práce s odbornou literaturourovíjí komunikativní a studijní dovednosti
Literatura
Sedláček, J. Úvod do teorie grafů. Academia Praha, 1977. Gross, J., Yellen, J. Graph theory and its applications. CRC Press, London, New York, 1998. Demel, J. Grafy. SNTL Praha, 1988. Demel, J. Grafy a jejich aplikace. SNTL Praha, 1988. Nešetřil, J. Teorie grafů. SNTL Praha, 1979.
Požadavky
Forma: písemnáZkouška se skládá ze dvou písemných testů nebo seminární práce a jednoho testu. Varianta je upřesněna na začátku semestru.Celkem lze získat až 100 b.Hodnocení probíhá v souladu s ustanoveními článku 32 a 33 Studijního a zkušebního řádu OU.
Garant
prof. Irina Perfiljeva, CSc.
Vyučující
RNDr. Petra Konečná, Ph.D.prof. Irina Perfiljeva, CSc.Mgr. Jakub DvorskýRNDr. Petra Konečná, Ph.D.