Табела 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