Элементы теории графов в курсе дискретной математики



Дисциплина «Дискретная математика» входит в учебные планы ряда направлений подготовки бакалавров и специалистов, например, «Математика», «Математика и компьютерные науки», «Фундаментальная математика и механика», и обычно включает в себя такие разделы, как комбинаторика, теория графов, теория кодирования, теория функциональных систем, целочисленное программирование и т. п.

Являясь одним из основных разделов дискретной математики, теория графов в то же время оказывается достаточно трудным объектом изучения.

Начало теории графов относят к 1736 г., когда Л. Эйлер решил популярную задачу о кенигсбергских мостах, а также нашел критерий существования в графе специального маршрута — эйлерова цикла.

Этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине 19 века инженер-электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А. Кэли решил перечислительные задачи для трех типов деревьев, описывающих строение углеводородов.

Однако за последние полвека теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами приложений.

В терминах теории графов формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок-схем программ, находят свое применение в экономике и статистике, химии и биологии, в теории расписаний и дискретной оптимизации.

Таким образом, теория графов — наука сравнительно молодая и как учебная дисциплина еще окончательно не сформировалась. Это затрудняет разработку рабочих программ и оценочных средств текущего контроля успеваемости, а также промежуточной и итоговой аттестации.

Так как обычно на преподавание дисциплины «Дискретная математика» отводится не более одного семестра, одной из проблем является отбор оптимального объема теоретического материала для лекций и практических заданий для лабораторных работ.

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

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

Второй модуль — это специальные вопросы теории графов: эйлеровы и гамильтоновы графы, раскраски графов, независимость и покрытия, паросочетания.

Третий модуль — это вопросы, относящиеся к ориентированным графам.

Наиболее полным и доступным пособием, в котором приведены соответствующие теоретические сведения, является [1]. Достаточно объемный сборник задач, как типовых, так и нестандартных, представлен в пособиях [2] и [3].

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

Например, на факультете математики и компьютерных наук КубГУ, читается курс «Комбинаторные алгоритмы», который посвящен изучению классических алгоритмов решения задач на графах; построению новых алгоритмов и модификации и комбинации уже известных схем для решения конкретных задач; оценке эффективности указанных алгоритмов. Алгоритмы на ориентированных графах изучаются в рамках специальной дисциплины на отдельных профилях. Им посвящено учебное пособие [4].

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

Цель изучения: формирование у студентов теоретических и методологических основ теории графов.

Задачи изучения:

− расширение сферы компетенции студентов в теории графов;

− овладение студентами понятийно-терминологическим аппаратом теории графов;

− овладение приемами применения теории графов к решению прикладных задач.

В результате изучения студент должен:

− знать основные понятия теории графов (определение графа, виды графов, способы задания графов, раскраска графов, циклы и пути в графах, алгоритмы на графах), необходимые для успешного изучения математических и теоретико-информационных дисциплин, решения задач, возникающих в профессиональной сфере;

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

− владеть навыками практического использования современного математического инструментария для решения и анализа задач, предусматривающими знание адекватных алгоритмов.

Большую роль в освоении курса играет самостоятельная работа студента.

Самостоятельность работы студента проявляется в действиях различного характера:

− подражание образцу;

− упражнения с измененными данными;

− осмысливание прослушанного и прочитанного материала;

− приобретение новых знаний из различных источников;

− применение полученных знаний в практической деятельности;

− повторение изученного.

Самостоятельная работа студента включает в себя следующие компоненты творческой и познавательной деятельности:

1. переработка информации, полученной непосредственно на занятиях:

– ведение кратких записей в процессе восприятия учебного материала;

– систематизация полученной информации;

– просмотр соответствующего материала в учебниках и учебных пособиях;

– дополнение и изменение в записях;

– выделение главного, существенного в конспектах;

– самостоятельная формулировка выводов и обобщений.

2. выполнение практических заданий:

– самостоятельное изучение отдельных тем (вопросов) программного обучения;

– конспектирование необходимой учебной литературы;

– написание докладов, сообщений, рефератов;

– подготовка письменных ответов на проблемные вопросы;

– обработка результатов научных исследований (по данной теме);

– расширение и углубление знаний путем самообразования.

Преподавателями кафедры вычислительной математики и информатики КубГУ было создано учебное пособие [5], занявшее первое место во внутривузовском конкурсе учебных пособий в 2015 году.

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

Ниже приведены задания, общие для всех студентов. Согласно номеру варианта преподаватель указывает граф (не более 8 вершин), с которым предстоит работать студенту.

Типовой расчет.

1. Пометьте вершины графа числами 1, 2, 3, … Найдите степени всех вершин графа. Проверьте справедливость леммы о рукопожатиях для данного графа. Является ли граф регулярным? Полным?
2. Сколько ребер содержит дополнение графа? Нарисуйте его. Является ли граф самодополнительным? Приведите пример графа, изоморфного данному.
3. Постройте матрицу смежности графа и матрицу инцидентности. Как по ним определить степени вершин? Покажите связь между этими матрицами.
4. Приведите пример графа, гомеоморфного данному. Постройте граф, производными от которого являются эти графы.
5. Есть ли в графе циклы? Приведите три примера. Чему равен обхват графа?
6. Является ли граф двудольным? (Воспользуйтесь поиском в ширину и теоремой Кенига).
7. Постройте матрицу расстояний графа. Найдите эксцентриситеты всех вершин графа, его радиус, диаметр, центр, периферию и медианы.
8. Постройте подграф, порожденный вершинами {1, 2, 3, 4}. Найдите в нем все маршруты длины 3. Сколько их? Какие из них являются цепями? Простыми цепями? Какие из них являются циклами?
9. Чему равно цикломатическое число графа?
10. Сколько остовов имеет граф? Нарисуйте один из них, построив его при помощи обхода в ширину или глубину или разрушая циклы.
11. Постройте для остова из п. 10 код Прюфера, затем переведите этот код обратно в дерево. (Убедитесь, что это одно и то же дерево).
12. Постройте матрицу фундаментальных циклов данного графа.
13. Найдите число вершинной связности и число реберной связности графа. Есть ли в графе точки сочленения и мосты?
14. Является ли граф планарным? Воспользовавшись алгоритмом , постройте его плоскую укладку или докажите, что граф не планарный.
15. Проверьте справедливость формулы Эйлера для плоской укладки из п.14. Триангулируйте полученный плоский граф. Сколько у него ребер и граней?
16. Найдите род, толщину, число скрещиваний, искаженность графа.
17. Является ли граф эйлеровым, гамильтоновым? Если нет, то проверьте, имеет ли он эйлерову и/или гамильтонову цепь.
18. Постройте правильную раскраску графа. Определите его хроматическое число.
19. Постройте хроматический полином данного графа.
20. Найдите независимые подмножества вершин графа, максимальные независимые подмножества вершин графа, наибольшие независимые подмножества вершин графа. Определите число независимости графа.
21. Найдите доминирующие подмножества вершин графа, минимальные доминирующие подмножества вершин графа, наименьшие доминирующие подмножества вершин графа. Найдите число доминирования.
22. Найдите ядро графа.
23. Найдите вершинные покрытия графа, минимальные вершинные покрытия графа, наименьшие вершинные покрытия графа. Найдите число вершинного покрытия.
24. Найдите реберные покрытия графа, минимальные реберные покрытия графа, наименьшие реберные покрытия графа. Найдите число реберного покрытия.
25. Найдите клики графа, максимальные клики графа, наибольшие клики графа. Нарисуйте подграфы, порожденные максимальными кликами. Найдите плотность графа. Найдите число кликового покрытия. Постройте матрицу клик, граф клик.
26. Найдите паросочетания графа, максимальные паросочетания, наибольшие паросочетания графа. Найдите число паросочетания.

На выполнение данных заданий студенту отводится весь семестр. Умение решать такие задачи является необходимым «минимумом» для допуска студента к зачету или экзамену.

Практика выполнения таких заданий демонстрирует достаточный уровень овладения студентами базовыми понятиями теории графов и формулировками основных теорем.

Литература:

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

3. Мельников О. И. Теория графов в занимательных задачах. — М.: Книжный дом «ЛИБРОКОМ», 2009.
4. Сухан И. В. Ориентированные графы: уч. пос. — Краснодар: КубГУ, 2016.
5. Сухан И. В., Иванисова О. В., Кравченко Г. Г. Графы: уч. пос., изд. 2-е, испр. и доп. — Краснодар: КубГУ, 2015.