Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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