Комбинаторика и теорија графова

Циљ и исход нпредмета

Оспособљавање студената на апстрактно мишљење и стицање основних знања из области класичних и некласичних комбинаторних објеката и теорије графова Студенти ће научити да класификују проблеме из комбинаторике, а затим и да их их решавају користећи познате комбинаторне методе, кроз усвајање теоријских знања и решавање практичних примера. Кроз учења познатих појмова и тврђења из теорије графова, студент ће бити оспособљен да поставља графовске моделе из примена у различитим дисциплинама.

Теоријска настава

Графови и подграфови. Матрице инциденције и матрице суседства. Графовске инваријанте. Путеви и циклуси – детаљнији приступ. Цикломатички број графа. Чворна и гранска повезаност графа. Стабла и њихове примене. Хамилтонови и Ојлерови циклуси и њихове примене. Бојење графова – детаљнији приступ. Планарни графови и графови полиедара. Теорема Куратовски-Понтрјагина. Бојење планарних графова. Спаривања у графовима и примене. Независни скупови, покривачи и клике графа. Унутрашња и спољашња стабилност графа са применом у теорији кодова. Примена у линеарној алгебри. Степени квадратних матрица и Марковљеви ланци. Графови протока сигнала. Рамсејева теорија графова. Оријентисани графови, блок-дизајни, коначне геометрије и матроиди.

Практична настава

Решавање репрезентативних задатака на табли, из области са којима су студенти упознати на теоријској настави.