Федеральное государственное образовательное автономное учреждение Высшего образования

Перечень основных разделов дисциплины:

1. 
   Начальные понятия теории графов (основные определения; способы задания графов; изоморфизм графов; операции над графами; связность и компоненты; метрические характеристики графов; важнейшие классы графов).
   
2. 
   Алгоритмы для решения задач на графах (процедура поиска в ширину; процедура поиска в глубину; выявление блоков; построение базы циклов; алгоритмы поиска эйлеровых и гамильтоновых циклов).
   
3. 
   Классические задачи теории графов и алгоритмы их решения (независимые множества, клики, вершинные покрытия; раскраска вершин и рёбер; паросочетания и рёберные покрытия; задача об оптимальном каркасе; жадные алгоритмы; кратчайшие пути; задача о максимальном потоке).
   

Преподавание дисциплины предусматривает следующие виды учебной работы: лекции, практические занятия, самостоятельная работа, консультации, программирование алгоритмов. Самостоятельная работа включает разбор лекционного материала, выполнение домашних заданий, подготовку к контрольным работам.

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


Правила аттестации по дисциплине.
Программой дисциплины предусмотрены следующие виды контроля: текущий контроль успеваемости в форме выполнения домашних работ и программирования изучаемых алгоритмов, а также написания двух контрольных рабо. Промежуточная аттестация по дисциплине проводится в конце 8 семестра в форме дифференцированного зачёта.


Учебно-методическое обеспечение дисциплины.
В преподавании дисциплины используется следующие основные источники:

1. 
   Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений: Учебник. – М.: БИНОМ. Лаборатория знаний, 2006.-320с.
   
2. 
   Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов: Учебное пособие – М.: Книжный дом «ЛИБРОКОМ», 2009.-392с.
   
3. 
   Емеличев В.А., Зверович И.Э., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Теория графов в задачах и упражнениях: Более 200 задач с подробными решениями. – Москва: Книжный дом «ЛИБРОКОМ», 2013.-416с.