Cilj predmeta je upoznavanje sa osnovnim pojmovima teorije grafova i stabala i osnovnim pojmovima spektralne teorije grafova u cilju primene u računarskim naukama.
Teorijska nastava
- Osnovni pojam grafa i definicija.
- Predstavljanje grafova. Matrica susedstva grafa. Matrice incidencije čvorova i grana. Matrica rastojanja grafa.
- Ojlerovi i Hamiltonovi grafovi.
- Pojam stabla.
- Korenska stabla.
- Primena binarnih stabala u računarstvu.
- Neki optimizacioni problemi na grafovima: Problem najkraćeg puta. Problem minimalnog razapinjućeg stabla. Problem trgovačkog putnika.
- Spektri grafova i primene.
- Laplasova matrica grafa.
- Sopstvene vrednosti i sopstveni vektori grafova.
- Osnovne osobine spektara grafova.
- Primena u računarstvu. Antivirusna zaštita, pretraživanje interneta i rangiranje sportista.
Praktična nastava
- Primena tehnike spektara grafova u računarstvu – internet tehnologijama i prepoznavanju mustri.
Literatura
- D. Cvetković, M. Čangalović, Đ. Dugošija, V. Kovačević-Vujčić, S. Simić, J. Vuleta, Kombinatorna optimizacija, Dopis, 1996.
- J. A. Anderson, Diskretna matematika sa kombinatorika. Računarski fakultet 2005.
- M. Čangalović, V. Manojlović, V. Baltić, Diskretne matematičke strukture. Fakultet organizacionih nauka 2009.
- D. Cvetković, P. Rowlinson, S. Simić, An Introduction to the Theory of Graph Spectra, Cambrige University Press, 2009.
- Selected Topics on Applications of Graph Spectra, Zbornik radova 14, Matematički institut SANU, 2011.
- D. Cvetković, S. Simić, Graph Spectra in Computer Sciences, Linear Algebra and Applications 2011.
