Теорија графова

Студије
Мастер академске студије (1. семестар)
Предавања
Мирјана Чангаловић, Весна Манојловић
Вежбе
Небојша Николић, Марија Боричић, Нада Младеновић, Душан Џамић

Циљ предмета је упознавање са основним појмовима теорије графова и стабала и основним појмовима спектралне теорије графова у циљу примене у рачунарским наукама.

Теоријска настава

  1. Основни појам графа и дефиниција.
  2. Представљање графова. Матрица суседства графа. Матрице инциденције чворова и грана. Матрица растојања графа. 
  3. Ојлерови и Хамилтонови графови. 
  4. Појам стабла.
  5. Коренска стабла. 
  6. Примена бинарних стабала у рачунарству. 
  7. Неки оптимизациони проблеми на графовима: Проблем најкраћег пута. Проблем минималног разапињућег стабла. Проблем трговачког путника. 
  8. Спектри графова и примене.  
  9. Лапласова матрица графа. 
  10. Сопствене вредности и сопствени вектори графова. 
  11. Основне особине спектара графова. 
  12. Примена у рачунарству. Антивирусна заштита, претраживање интернета и рангирање спортиста.

Практична настава

  1. Примена технике спектара графова у рачунарству – интернет технологијама и препознавању мустри.


Литература

  • Д. Цветковић, М. Чангаловић, Ђ. Дугошија, В. Ковачевић-Вујчић, С. Симић, Ј. Вулета, Комбинаторна оптимизација, Допис, 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.

© 2017 Катедра за математику| Факултет организационих наука | Универзитет у Београду