DOKTORANTŪROS STUDIJŲ KURSO PROGRAMA
Grafų teorija
Kursas skirtas
Informatikos specialybės doktorantams.
Kurso tipas:
privalomasis.
Apimtis: 60 val.
Atsiskaitymai: seminarai, egzaminas.
Dėstytojas:
prof., hab.dr. Eugenijus Manstavičius
Anotacija:
Kurse nagrinėjami fundamentalūs grafų teorijos uždaviniai bei pateikiami jų sprendimo algoritmai, skirti tiesiogiai realizuoti kompiuteriais. Kartu griežtai įrodomas visų pateiktų algoritmų korektiškumas bei išanalizuojamas ir asimptotiškai įvertinamas jų efektyvumas.
Tematika
Elementarūs grafų algoritmai
- Grafų vaizdavimas kompiuteryje
- Paieška į plotį
- Paieška į gylį
Topologinis rūšiavimas
Tampriai susieti komponentai
Minimalūs jungiantieji medžiai
- Minimalaus jungiančiojo medžio auginimas
Kruskalio ir Primo algoritmai
Trumpiausi atstumai nuo vienos viršūnės
Trumpiausias kelias ir relaksacija
Dijkstros algoritmas
Belmano-Fordo algoritmas
Trumpiausias kelias orientuotuose grafuose be ciklų
Skirtuminiai apribojimai ir trumpiausi keliai
Trumpiausi atstumai tarp viršūnių porų
- Trumpiausi keliai ir matricų daugyba
Floydo-Varšalo algoritmas
Džonsono algoritmas išretintiems grafams
Bendra schema orientuotų grafų kelių problemų sprendimui
Maksimalus srautas
Srautų tinklai
Fordo-Fulkersono metodas
Maksimalus dvidalių grafų suporavimas
Priešsraučio stūmimo algoritmai
Perkėlimo į priekį algoritmai
Literatūra
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
Introduction to Algorithms; McGraw-Hill Book Company, 1993.
- Béla Bollobás:
Graph Theory; An Introductory Course; Springer-Verlag New York Inc., 1979.
- Reinhard Diestel:
Graph Theory; Springer-Verlag New York, 1997.
Pradinis puslapis |
Main page