Введение

Тема 1. Определение графа

• 1.1. Основные определения (146мин.)
• 1.2. Представления графов (49мин.)
• • 1.2.1. Матрица смежности графа (24мин.)
  • 1.2.2. Матрица весов графа (24мин.)
  • 1.2.3. Реберный список графа (24мин.)
  • 1.2.4. Структура смежности графа (24мин.)
• 1.3. Примеры решения задач (24мин.)
• Задачи для самостоятельного решения (49мин.)
• Тест:  Определение графа (44мин.)

Тема 2. Кратчайшие пути на графе

• 2.1. Алгоритм Дейкстры поиска кратчайшего пути (97мин.)
• 2.2. Примеры выполнения заданий (121мин.)
• Тест:  Кратчайшие пути на графе (10мин.)

Тема 3. Минимальное остовное дерево

• 3.1. Основные определения (24мин.)
• 3.2. Алгоритм Краскала — жадная схема построения минимального остовного дерева (49мин.)
• 3.3. Алгоритм Прима — алгоритм ближайшего соседа построения минимального остовного дерева (24мин.)
• 3.4. Примеры выполнения заданий (97мин.)
• Тест:  Минимальное остовное дерево (18мин.)

Тема 4. Потоки в сетях

• 4.1. Понятие и свойства потока (49мин.)
• 4.2. Алгоритм Форда — Фалкерсона (73мин.)
• 4.3. Примеры выполнения заданий (267мин.)
• Тест:  Потоки в сетях (14мин.)

Тема 5. Хроматические графы

• 5.1. Понятие раскраски графа (49мин.)
• 5.2. Неявная схема раскраски вершин графа (24мин.)
• 5.3. Примеры выполнения заданий (146мин.)
• Тест:  Хроматические графы (12мин.)

Тема 6. Оптимальная раскраска Магу

• 6.1. Теорема об оптимальной раскраске (24мин.)
• 6.2. Метод Магу отыскания независимых множеств (73мин.)
• 6.3. Оптимальная раскраска методом Магу (73мин.)
• 6.4. Пример выполнения задания (73мин.)
• Тест:  Оптимальная раскраска Магу (12мин.)

Тема 7. Двудольные графы

• 7.1. Условия существования двудольных графов (24мин.)
• 7.2. Паросочетания (24мин.)
• 7.3. Алгоритм определения максимального паросочетания (24мин.)
• 7.4. Примеры выполнения заданий (146мин.)
• Тест:  Двудольные графы (14мин.)

Тема 8. Задача о назначениях

• 8.1. Системы различных представителей и их связь с двудольными графами (49мин.)
• 8.2. Задача о назначениях (121мин.)
• 8.3. Примеры выполнения заданий (121мин.)
• Тест:  Задача о назначениях (10мин.)

Тема 9. Метод поиска в глубину

• 9.1. Алгоритм Тарьяна поиска в глубину (24мин.)
• 9.2. Пример выполнения задания (97мин.)
• Тест:  Метод поиска в глубину (10мин.)

Тема 10. Метод поиска в ширину

• 10.1. Алгоритм поиска в ширину (49мин.)
• 10.2. Пример выполнения задания (97мин.)
• Тест:  Метод поиска в ширину (10мин.)

Тема 11. Компоненты связности графа

• 11.1. Отношение эквивалентности (49мин.)
• 11.2. Компоненты связности (24мин.)
• 11.3. Выделение компонент связности (24мин.)
• 11.4. Пример выполнения задания (73мин.)
• Тест:  Компоненты связности графа (14мин.)

Тема 12. Циклы, фундаментальные множества циклов

• 12.1. Пространство остовных подграфов (24мин.)
• 12.2. Квазициклы. Пространство циклов графа (73мин.)
• 12.3. Алгоритм поиска фундаментального множества циклов (24мин.)
• 12.4. Примеры выполнения заданий (146мин.)
• Тест:  Циклы, фундаментальные множества циклов (14мин.)

Тема 13. Листы и блоки. Связность графа

• 13.1. Листы (49мин.)
• 13.2. Блоки (97мин.)
• 13.3. Алгоритм поиска блоков графа (97мин.)
• 13.4. Пример выполнения задания (49мин.)
• Тест:  Листы и блоки. Связность графа (14мин.)

Тема 14. Эйлеровы графы. Клики

• 14.1. Эйлеровы графы (73мин.)
• 14.2. Диаметр, радиус и центры графа (24мин.)
• 14.3. Клики, независимые множества (49мин.)
• 14.4. Алгоритм поиска клик (73мин.)
• 14.5. Примеры выполнения заданий (73мин.)
• Тест:  Эйлеровы графы. Клики (14мин.)

Тема 15. Введение в теорию групп

• 15.1. Определение группы (24мин.)
• 15.2. Примеры групп (24мин.)
• 15.3. Смежные классы (24мин.)
• 15.4. Циклические подгруппы (97мин.)
• 15.5. Примарные подгруппы (97мин.)
• Тест:  Введение в теорию групп (10мин.)

Тема 16. Элементы теории чисел

• 16.1. Наибольший общий делитель (24мин.)
• 16.2. Наименьшее общее кратное (24мин.)
• 16.3. Простые числа (49мин.)
• 16.4. Сравнения, свойства сравнений (24мин.)
• 16.5. Полная система вычетов (24мин.)
• 16.6. Приведенная система вычетов (49мин.)
• 16.7. Функция Эйлера (73мин.)
• Тест:  Элементы теории чисел (22мин.)

Тема 17. Шифрование с открытым ключом

• Тест:  Шифрование с открытым ключом (16мин.)

Приложение. Варианты домашних заданий

• 1. Задачи первого задания (49мин.)
• 2. Задачи второго задания (24мин.)
• 3. Задачи третьего задания (49мин.)

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

Новые издания по дисциплине «Дискретная математика» и смежным дисциплинам

Завершение курса

• Тест:  Итоговое тестирование (42мин.)