Циљ предмета је упознавање са основним појмовима теорије графова и стабала и основним појмовима спектралне теорије графова у циљу примене у рачунарским наукама.
Теоријска настава
- Основни појам графа и дефиниција.
- Представљање графова. Матрица суседства графа. Матрице инциденције чворова и грана. Матрица растојања графа.
- Ојлерови и Хамилтонови графови.
- Појам стабла.
- Коренска стабла.
- Примена бинарних стабала у рачунарству.
- Неки оптимизациони проблеми на графовима: Проблем најкраћег пута. Проблем минималног разапињућег стабла. Проблем трговачког путника.
- Спектри графова и примене.
- Лапласова матрица графа.
- Сопствене вредности и сопствени вектори графова.
- Основне особине спектара графова.
- Примена у рачунарству. Антивирусна заштита, претраживање интернета и рангирање спортиста.
Практична настава
- Примена технике спектара графова у рачунарству – интернет технологијама и препознавању мустри.
Литература
- Д. Цветковић, М. Чангаловић, Ђ. Дугошија, В. Ковачевић-Вујчић, С. Симић, Ј. Вулета, Комбинаторна оптимизација, Допис, 1996.
- Ј. А. Андерсон, Дискретна математика са комбинаторика. Рачунарски факултет 2005.
- М. Чангаловић, В. Манојловић, В. Балтић, Дискретне математичке структуре. Факултет организационих наука 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, Зборник радова 14, Математички институт САНУ, 2011.
- D. Cvetković, S. Simić, Graph Spectra in Computer Sciences, Linear Algebra and Applications 2011.
