Специальные главы теории графов, комбинаторики и теории чисел

Цели и задачи дисциплины

Комбинаторика и теория графов находят широкое применение в различных прикладных областях математики, физики, биологии, гуманитарных наук. Также теория графов нашла непосредственное применение в программировании. Целью данного курса является ознакомление обучающихся с основными определениями и теремами этих областей математики.

Краткое содержание дисциплины

Множества и операции над ними. Отношения. Свойства отношений. Отношение эквивалентности. Комбинаторика. Правило произведения. Число подмножеств конечного множества. Размещения. Сочетания. Перестановки с повторениями. Полиномиальная формула. Комбинаторные тождества. Формула включения-исключения и ее применения. Рекуррентные соотношения. Графы. Определения и примеры. Связность. Метрические характеристики. Гамильтоновы графы. Эйлеровы графы. Деревья. Хроматический многочлен графа. Укладки графов. Планарные графы. Формула Эйлера. Ориентированные графы. Нахождение кратчайших путей в орграфе. Потоки в сетях.

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать:

ПК-3 способен проектировать и реализовывать учебно-методическое обеспечение дополнительного математического образования в общеобразовательных организациях