Neprihlásený používateľ
Cesta: Menu > Štúdium > Zoznam predmetov
2-INF-174 Teória grafov
Odporúčaný ročník: 3.
Semester: zimný
Rozsah: P3,C1
Hodnotenie: 0/100
Počet kreditov: 6
Vyučujúci:prednáša prof. RNDr. Martin Škoviera PhD.
cvičí Mgr. Michal Kotrbčík
prednáša doc. RNDr. Edita Mačajová PhD.
www stránka:

Cieľ:

Predmet buduje solídne základy teórie grafov dokázaním kľúčových klasických teorém a podaním najdôležitejších algoritmov na grafoch. Veľký dôraz sa kladie aj na motiváciu pochádzajúcu z iných vedných disciplín a praxe ako aj na možné aplikácie skúmanej problematiky.

Sylabus:

Základné pojmy: stromy, bipartitné grafy, prehľadávanie grafov a labyrintov, Eulerovské grafy; párenia v grafoch, Königova teoréma, Hallova teoréma a jej dôsledky; meranie sily súvislosti grafov; Mengerova teoréma; planárne grafy: Eulerova teoréma, Kuratovského teoréma. Farbenia: niektoré NP-úplné problémy, pažravý algoritmus, Brooksova teoréma, Vizingova teoréma, farbenie planárnych grafov; toky: Fordov a Fulkersonov algoritmus a jeho aplikácie, celočíselné a grupové toky, súvis s farbeniami; Hamiltonovské grafy: Chvátalova teoréma; náhodné grafy: pravdepodobnostné modely, vlastnosti náhodných grafov.

Literatúra:

Plesník J.: Grafové algoritmy. Veda
Diestel R.: Graph theory, Springer Verlag
Nesetřil J.: Teorie grafů, SNTL


Informačný list predmetu z AISu

Kontakt Hlavná stránka © 2012