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

Студије
Мастер академске студије (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.

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