Теория графов и комбинаторика
Курс для студентов-программистов второго семестра. Число часов лекций - 36, число часов практических занятий - 36, в конце курса - экзамен.
Основные темы: общие сведения о графах и их характеристиках, эйлеровы и гамильтоновы графы, паросочетания и алгоритм построения наибольшего паросочетания в двудольном графе, алгоритм разбиения частично упорядоченного множества на минимальное число цепей, взвешенные графы и задачи о кратчайших маршрутах и остовах минимального веса, плоские графы и их основные свойства, раскраски графов и алгоритм Зыкова построения хроматического многочлена графа, ориентированные графы и сети, алгоритм Форда-Фалкерсона построения максимального стационарного потока в сети, основные комбинаторные соединения и бином Ньютона, метод включения-исключения, формальные степенные ряды и линейные рекуррентные соотношения.
Конспект лекций
Задачи и упражнения
Послать
сообщение