Назив предмета:     Алгебарска теорија графова

Наставник (презиме, средње слово, име):     Стевановић П. Драган

Статус предмета:     изборни

Број ЕСПБ:     12

Услов:     није предвиђен

Циљ предмета

Упознавање са применама линеарне алгебре и других алгебарских метода у теорији графова.

Исход предмета:

Студент је оспособљен да самостално прати и решава проблеме из теорије графова.

Садржај предмета:

 

  • Графови. Основне особине графова и њихова терминологија. Примери графова.

 

  • Теорија матрица. Матрица суседства. Матрица инциденције. Лапласове матрице. Сопствени вектори. Позитивно семидефинитне матрице. Перон-Фробенијусова теорема. Ранг симетричне матрице. Спектрална декомпозиција.

 

  • Преплитање сопствених вредности. Преплитање сопствених вредности. Једнакотабличне партиције. Сопствене вредности Кнесерових графова. Примене. Бипартитни подграфови. Фулерени.

 

  • Јако регуларни графови. Параметри. Сопствене вредности. Неке карактеризације. Графови латинских квадрата. Мали јако регуларни графови. Локалне сопствене вредности. Крајнове границе. Уопштени квадрати. Квазисиметрични дизајни. Витов дизајн са 23 тачке. Симплектични графови.

 

  • Графови грана и сопствене вредности. Уопштени графови грана. Звезда-затворени скупови грана. Рефлексије. Недељиви звезда-затворени скупови. Генеришући скуп. Класификација. Коренски системи. Јако регуларни графови.

 

  • Лапласова матрица графа. Лапласова матрица. Стабла. Репрезентације. Енергија и сопствене вредности. Повезаност. Преплитање. Цртање графова. Вишеструкости.

 

  • Примери и примене. Границе за сопствене вредности. Максимални пресек. Планарни графови. Случајни путеви. Експандери и кодови. Случајни графови. Примене у комбинаторној оптимизацији. Примене у квантном рачунању.

 

Препоручена литература:

 

  1. D. Cvetković, H. Sachs, M. Doob, Spectra of Graphs — Theory and Applications, Johann Ambrosius Barth Verlag, 1995.
  2. C. Godsil, G. Royle, Algebraic Graph Theory
  3. Brockwell, P.J., Davis, R.A., Time series: Theory and Methods, Springer-Verlag, New York, 1987.

 

Број часова  активне наставе:

Предавања: 60

Студијски истраживачки рад:

Методе извођења наставе

Фронтална, индивидуална, интерактивна

Оцена  знања

Предиспитне обавезе:

Студент је у обавези да уради 3 домаћа задатка, сваки потпуно урађени домаћи задатак доноси студенту 10 поена.

Начин и процедура полагања испита:

Испит се полаже усмено. Максималан број поена на усменом испиту је 70.