General information
Kurs je namenjen studentima akademskih doktorskih studija programa Matematika.Svi koji su zainteresovani za slušanje ovog kursa treba da se jave i-mejlom radi dogovora.
Sadržaj kursa
- Grafovi i podgrafovi, matrice incidencije i susedstva. Grafovske invarijante.
- Osvrt na klasčne algoritme na grafovima i njihove primene.
- Nezavisni i dominantni skupovi grafa. Problem pokrivanja grafa i algoritmi za rešavanje.
- Bojenje grafova, hromatski polinomi i odgovarajući algoritmi.
- Cenatar, radijus, apsolutni i p-centri grafa. Algoritmi za njihovo određivanje.
- Minimalno razapinjuće stablo grafa, Štajnerov problem. Algoritmi za rešavanje i primene.
- Hamiltonovi i Ojlerovi ciklusi grafova. Algoritmi za njihovo određivanje.
- Softverski paketi i njihova implementacija.
Literatura
- N. Christofides: Graph Theory - An Algorithmic Approach, Academic Press, London, 1975.
- B. Korte, J. Vygen: Combinatorial Optimization, Springer, Berlin, 2005.
- D. Veljan: Kombinatorika s teorijom grafova, Školska knjiga, Zagreb, 1989.
Način formiranja ocene
- Predispitne obaveze
Seminarski rad, 30 poena
- Završni ispit
Usmeni ispit (teorija), 70 poena