Опште информације
Курс је намењен студентима академских докторских студија програма Математика.Сви који су заинтересовани за слушање овог курса треба да се јаве и-мејлом ради договора.
Садржај курса
- Графови и подграфови, матрице инциденције и суседства. Графовске инваријанте.
- Осврт на класчне алгоритме на графовима и њихове примене.
- Независни и доминантни скупови графа. Проблем покривања графа и алгоритми за решавање.
- Бојење графова, хроматски полиноми и одговарајући алгоритми.
- Ценатар, радијус, апсолутни и p-центри графа. Алгоритми за њихово одређивање.
- Минимално разапињуће стабло графа, Штајнеров проблем. Алгоритми за решавање и примене.
- Хамилтонови и Ојлерови циклуси графова. Алгоритми за њихово одређивање.
- Софтверски пакети и њихова имплементација.
Литература
- N. Christofides: Graph Theory - An Algorithmic Approach, Academic Press, London, 1975.
- B. Korte, J. Vygen: Combinatorial Optimization, Springer, Berlin, 2005.
- Д. Вељан: Комбинаторика с теоријом графова, Школска књига, Загреб, 1989.
Начин формирања оцене
- Предиспитне обавезе
Семинарски рад, 30 поена
- Завршни испит
Усмени испит (теорија), 70 поена