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. prednáša doc. RNDr. Edita Mačajová PhD. |
www stránka: |
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.
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.
Plesník J.: Grafové algoritmy. Veda
Diestel R.: Graph theory, Springer Verlag
Nesetřil J.: Teorie grafů, SNTL