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

Циљ предмета:

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

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

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

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

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

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

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

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

Литература

  1. Цветковић Д., Теорија графова и њене примене, Научна књига, Београд, 1986.
  2. Цветковић Д., Комбинаторика – класична и модерна, Научна књига, Београд, 1990.
  3. Вељан Д., Комбинаторика с теоријом графова, Школска књига Загреб, 1989.
  4. Петровић В., Теорија графова, Универзитет у Новом Саду, Природно-математички факултет, Нови Сад, 1998.

Kreatori kursa: Irena Jovanović