INFORMAČNÝ LIST PREDMETU |
|||||
Kód: P203 |
Skratka: GK |
Názov: Grafy a kombinatorika | |||
Študijný odbor: Informačné a riadiace systémy, Aplikovaná matematika |
|||||
Garantuje: Zabezpečuje: doc. RNDr. Stanislav Palúch, CSc. |
|||||
Semester: letný Odporučený: 2 |
Rozsah výučby: prednášky – cvičenia –
laboratórne cvičenia Týždenný: 2-2-0 Za semester: 24-24-0 |
ECTS kredity: 7 |
|||
Podmieňujúce predmety: | |||||
Ukončenie predmetu a spôsob hodnotenia: priebežne – 15% skúška (písomná a ústna) – 85% |
|||||
Cieľ predmetu :
Uviesť študentov do problematiky teórie grafov a diskrétnej optimalizácie. |
|||||
Stručný sylabus: Prednášky: 1.Základné pojmy teórie grafov. 2.Algoritmy, výpočtová zložitosť a NP-ťažké úlohy. 3.Cesty v grafoch, súvislosť a prieskum grafov. 4.Najkratšia cesta v grafe a digrafe. Hľadanie cyklov zápornej ceny. 5.Stromy, kostra grafu a cesta maximálnej priepustnosti. 6.Acyklické digrafy a úloha časového plánovania. 7.Toky v sieťach. 8.Najlacnejší maximálny tok a ďalšie tokové úlohy. 9.Eulerovské ťahy. Párenia. Úloha čínskeho poštára. 10.Úloha obchodného cestujúceho. 11.Farbenie grafov. 12.Mediány a centrá. Kliky, nezávislé množiny a pokrývacie množiny. Cvičenia: (Všetky V) 1.Binárne relácie a opakovanie základov kombinatoriky. 2.Výpočtová zložitosť a polynomiálne redukcia úloh. 3.Súvislosť a Tarryho algoritmus. 4.Algoritmy pre hľadanie najkratšej cesty v grafe a digrafe. Hľadanie cyklu zápornej ceny. 5.Kruskalov algoritmus a hľadanie cesty maximálnej priepustnosti. 6.Acyklické digrafy. Monotónne očíslovanie. Sieťová analýza-metóda CPM. 7.Ford-Fulkersonov algoritmus pre maximálny tok v sieti. 8.Najlacnejší maximálny tok v sieti. 9.Algoritmy pre eulerovský ťah v grafe a digrafe, Edmonsov algoritmus pre úlohu čínskeho poštára. 10.Heuristiky pre úlohu obchodného cestujúceho. 11.Farbenie grafov. Rovinné grafy 12.Alokačné úlohy, nezávislá množina a klika. |
|||||
Literatúra: Plesník, J.: Grafové algoritmy, VEDA,SAV Bratislava 1983 Evans, J.,R., Minieka, E.: Optimizarion Algorithms for Networks and Graphs, Marcel Decker, New Yourk, second edition 1992, ISBN 0-8247-8602-5 Gross,J., Yellen, J.: Graph Theory and its Applications, CRC Press, 1998, ISBN 0-8493-3982-0 |
|||||
Dátum poslednej úpravy osnovy: 18.12.2002 |