Předmět Teorie grafů (KMA / TEGRG)
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 / TEGRG - Teorie grafů, 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
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
zná základní pojmy z oblasti teorie grafůchápe obecné vlastnosti a základní věty z teorie grafůumí ilustrovat základní pojmy a vysvětlit vlastnosti na konkrétních příkladechosvojuje si základní algoritmické postupy pro řešení jednoduchých úloh z teorie grafů a umí je aplikovatupevňuje si schopnost samostaté práce s odbornou literaturourovíjí komunikativní a studijní dovednosti
Literatura
Jiří Močkoř. Úvod do diskrétní matematiky. Ostravská univerzita, 1992. Sedláček, J. Úvod do teorie grafů. Academia Praha, 1977. Demel, J. Grafy a jejich aplikace. SNTL Praha, 1988. J.Gross, J.Yellen. Graph Theory and its Applications. CRC Press, Londo, New York, 1998. Demel, J. Grafy. SNTL Praha, 1988. Nešetřil, J. Teorie grafů. Praha : SNTL, 1979.
Požadavky
Zápočet je průběžným hodnocením studia. Skládá se ze seminární práce a jednoho písemného testu v 2. polovině semestru popřípadě dvou písemných testů. Varianta včetně termínů je upřesněna na začátku výuky daného semestru. Test/y lze 1x opakovat.Celkem je možné získat max. 100 bodů. Hodnocení probíhá v souladu s ustanoveními článku 31 a 33 Studijního a zkušebního řádu OU.
Garant
RNDr. Petra Konečná, Ph.D.
Vyučující
RNDr. Petra Konečná, Ph.D.Mgr. Jakub DvorskýRNDr. Petra Konečná, Ph.D.