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

 

Назив предмета    И341 - Алгебарска комбинаторика

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

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

Број ЕСПБ:   12

Услов:  нема

Циљ предмета

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

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

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

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

Полином спаривања. Рекурентне формуле. Интеграли. Полином ловца. Полином поготка. Стирлин-гови и Ојлерови бројеви. Полиноми поготка и интеграли. Карактеристични полином. Коефицијенти и рекурентне формуле. Шетње у графу и карактеристични полином. Сопствени вектори. Регуларни графови. Спектрална декомпозиција. Формални степени редови и функције генератрисе. Формални степени редови. Границе. Операције са степеним редовима. Степен и логаритам. Нелинеарне једначине. Примене и примери. Функција генератриса шетњи у графу. Јакобијева теорема. Шетње и путеви. Декомпозициона формула. Идентитет Кристофел-Дарбуа. Реконструкција чворова. Коспектрални графови. Случајне шетње на графовима. Делиоци графова. Еквитабеларне партиције. Сопствене вредности и вектори. Шетња-регуларни графови. Уопштено преплитање. Прекривачи. Спектрални радијус стабла. Спаривања и шетње. Стабло путева. Стаблолике шетње. Последице реалности. Идентитети Кристофел-Дарбуа. Пфафијани. Пфафијани и детерминанте. Експанзија по врсти. Оријентисани графови. Оријентације. Тешкоће у пребројавању савршених спаривања. Раздаљинско-регуларни графови. Неке фамилије. Матрице раздаљина. Параметри. Делиоци. Импритивни раздаљинско-регуларни графови. Кодови. Потпуно регуларни подскупови. Шеме асоцијације. Транзитивне групе пермутација. P и Q-полиномне шеме асоцијација. Примитивност и импримитивност. Кодови и антикодови. Карактери Абелових група. Кејлијеви графови. Представљање раздаљинско-регуларних графова. Представљања графова. Низ косинуса. Инјек-тивност. Вишеструкост сопствених вредности. Ограничавање дијаметра. Сферни дизајни. Граница за клике. Допустиви аутоморфизми.

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

1.       C. Godsil, Algebraic Combinatorics, Chapman Hall/CRC Math Series, 1993.

2.      D. Cvetković, H. Sachs, M. Doob, Spectra of Graphs — Theory and Applications, Johann Ambrosius Barth Verlag, 1995.

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

Предавања:

4

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

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

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

Оцена  знања (максимални број поена 100)

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

поена

Завршни испит

поена

домаћи задаци

45 (3x15)

усмени испит

55