Discrete Mathematics

2022/2023

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Department of Mathematics

Course type:

Compulsory course

When:

1 year, 1, 2 module

Instructor

Казакевич Виктория Григорьевна

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

• Целью освоения дисциплины «Дискретная математика» является изучение начального курса теории графов, а также необходимых для этого инструментов (базовой комбинаторики и бинарных отношений).

Планируемые результаты обучения

• Демонстрирует знание базовых комбинаторных понятий и приемов, в частности, понятий размещения, сочетания и перестановки, принципов сложения и умножения, принципа Дирихле и принципа включения-исключения, демонстрирует умение проводить простые комбинаторные рассуждения и вычисления.
• Демонстрирует знание понятия бинарного отношения, владение поянтиями частичного, линейного, строгого и нестрогого порядков, а также отношения эквивалентности, демонстрирует умение определять тип бинарного отношения по стандартным формам представления, а также транслировать описание бинарного отношения из одной формы представления в другую.
• Демонстрирует знание определений базовых понятий теории графов, владение понятиями «направленное и ненаправленное ребро», «степень вершины», «путь» (открытый или замкнутый), «простой путь», «цепь», «цикл», «дерево», «полный граф» и так далее. Умеет задавать граф бинарным отношением, списком инцидентности, матрицами смежности и инцидентности, а также транслировать один способ задания в другой, умеет применять алгоритмы поиска (обхода) в ширину и глубину.
• Демонстрирует знание понятий связности и k-связности для неориентированного графа, умеет выделять мосты и компоненты связности. Демонстрирует знание понятий слабой и сильной связности для орграфа, умеет вы делять компоненты сильной связности с использованием алгоритма Косарайю, а также строить граф Герца.
• Демонстрирует знание понятий эйлерова пути и эйлерова цикла, а также эйлерова и полуэйлерова графа; умеет определять эйлеровость/полуэйлеровость графа с использованием соответствующих критериев, а при их наличии - строить в графе эйлеров путь/цикл.
• Демонстрирует знание понятия дерева и связанных с ним понятий, умеет строить по дереву его код Прюфера и восстанавливать дерево по его коду Прюфера. Демонстрирует знание понятий остовного дерева, главного цикла и разреза.
• Демонстрирует знание понятия сети и потока в ней, понимание постановки задачи о максимальном потоке в сети; уменет определять, является ли сеть плоской, умеет решать задачу о максимальном потоке в сети при помощи алгоритмов Форда-Фалкерсона, Эдмондса-Карпа и Диница.
• Демонстрирует знание понятия двудольного графа, умение опрее\делять двудольность графа с использованием теоремы Кенинга. Демонстрирует знание понятия паросочетания, понимание различий между максимальным и наибольшим паросочетанием, умеет строить наибольшее паросочетание.
• Демонстрирует зание понятия вершинной раскраски графа, правильной вершинной раскраски, хроматического числа. Демонстрирует знание понятия хроматического многочлена, умение сопоставлять некоторые характеристики графа с некоторыми свойствами хроматического многочлена, умение построить для графа хроматический многочлен при помощи теоремы о разделяющей клике или теоремы о редукции.
• Демонстрирует знание понятия минимального остовного дерева взвешенного графа, умение построить минимальное остовное дерево при помощи алгоритмов Прима и Краскаля.
• Демонстрирует знание понятия кратчайшего пути (во взвешенном и невзвешенном графах). Умеет строить кратчайший путь от фиксированной вершины взвешенного графа до прочих при помощи алгоритмов Дейкстры и Форда-Беллмана.
• Демонстрирует знание понятия кратчайшего пути (во взвешенном и невзвешенном графах). Умеет строить кратчайший путь от фиксированной вершины взвешенного графа до прочих при помощи алгоритмов Дейкстры и Форда-Беллмана. Умеет строить все кратчайшие пути во взвешенном графе при помощи алгоритмов Флойда и Джонсона.

Содержание учебной дисциплины

• Базовые комбинаторные понятия и приемы.
• Бинарные отношения: основные определения, свойства, способы задания.
• Теория графов: базовые определения и свойства, примеры.
• Связность, k-связность, слабая и сильная связность.
• Эйлеровы и полуэйлеровы графы
• Деревья, остовные деревья, код Прюфера, корневые деревья.
• Задача о максимальном потоке в сети
• Двудольные графы, критерий двудольности (теорема Кенинга).
• Вершинные раскраски графа
• Минимальные остовные деревья взвешенных графов.
• Задача о построении кратчайших путей.
• Построение всех кратчайших путей во взвешенном графе

Элементы контроля

• Контрольная работа 1
  Состоит из 6 задач. Максимальная стоимость задания: 1-4 — 20 баллов, 5,6 — 10 баллов.
• Контрольная работа 2
  Состоит из 6 задач. Максимальная стоимость задания: 1-4 — 20 баллов, 5,6 — 10 баллов.
• Домашнее задание 1
  Состоит из 5 заданий по 5 пунктов в каждом. Максимальная оценка за каждый пункт — 4 балла.
• Домашнее задание 2
  Состоит из 14 заданий. Максимальная стоимость заданий 10-13 — по 10 баллов, остальные — по 6 баллов.
• Домашнее задание 3
  Состоит из 4 задач. Максимальная стоимость задания: 1,2 — 10 баллов, 3,4 — 40 баллов.

Промежуточная аттестация

• 2022/2023 учебный год 2 модуль
  0.25 * Контрольная работа 2 + 0.25 * Домашнее задание 2 + 0.25 * Контрольная работа 1 + 0.125 * Домашнее задание 3 + 0.125 * Домашнее задание 1

Список литературы

Рекомендуемая основная литература

• Алгоритмы: построение и анализ : пер.с англ., Кормен, Т., 2013
• Комбинаторика, Виленкин, Н. Я., 2006
• Теория графов, Харари, Ф., 2018

Рекомендуемая дополнительная литература

• Теория графов : алгоритмический подход, Кристофидес, Н., 1978