Табела 5.1 Спецификација  предмета  на студијском програму докторских студија

Назив предмета:     И353 - Алгебарска теорија графова
Наставник (презиме, средње слово, име):   Стевановић П. Драган
Статус предмета:     изборни
Број ЕСПБ:     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.
Број часова  активне наставе:		Предавања: 4		Студијски истраживачки рад:
Методе извођења наставе Фронтална, индивидуална, интерактивна
Оцена  знања (максимални број поена 100)
Предиспитне обавезе	поена		Завршни испит		поена
домаћи задаци	30 (3x10)		усмени испит		70