Введение

Тема 1. Основы теории графов

• 1.1. Граф, степень, изоморфизм (17мин.)
• 1.2. Пути, связность, расстояние (17мин.)
• 1.3. Регулярные графы (17мин.)
• 1.4. Специальные классы графов (17мин.)
• 1.5. Операции над графами (35мин.)
• 1.6. Подграфы (17мин.)
• Тест:  Основы теории графов (18мин.)

Тема 2. Матрицы и графы

• 2.1. Матрица смежности (35мин.)
• 2.2. Матрица инцидентности (17мин.)
• 2.3 Матрица Кирхгофа (17мин.)
• Тест:  Матрицы и графы (12мин.)

Тема 3. Характеристический полином и спектр графа

• 3.1. Характеристический полином (35мин.)
• 3.2 Спектр графа (52мин.)
• 3.3. Решение задач со спектрами (35мин.)
• Тест:  Характеристический полином и спектр графа (10мин.)

Тема 4. Дистанционно-регулярные графы

• 4.1. Определение дистанционно-регулярного графа (35мин.)
• 4.2. Сильно регулярные графы (87мин.)
• 4.3. Графы Мура (35мин.)
• Тест:  Дистанционно-регулярные графы (12мин.)

Тема 5. Группы и графы

• 5.1. Основные понятия (35мин.)
• 5.2. Диэдральная группа (17мин.)
• 5.3. Симметрическая группа (17мин.)
• 5.4. Группа автоморфизмов графа (87мин.)
• Тест:  Группы и графы (12мин.)

Тема 6. Транзитивные графы

• 6.1. Вершинно- и реберно-транзитивные графы (52мин.)
• 6.2. Дистанционно-транзитивные графы (52мин.)
• 6.3. Графы Кэли (70мин.)
• 6.4. Схематическая связь между регулярными и транзитивными графами (35мин.)
• Тест:  Транзитивные графы (10мин.)

Тема 7. Семейства графов

• 7.1. Граф Хэмминга (52мин.)
• 7.2. Граф Джонсона (70мин.)
• 7.3. Граф Кнезера (35мин.)
• Тест:  Семейства графов (10мин.)

Тема 8. Графы Кэли на симметрической группе

• 8.1. Транспозиционный граф (17мин.)
• 8.2. Граф пузырьковой сортировки (35мин.)
• 8.3. Звездный граф (35мин.)
• 8.4. Реверсальный граф (17мин.)
• 8.5. Блинный граф (35мин.)
• Тест:  Графы Кэли на симметрической группе (10мин.)

Тема 9. Нахождение диаметра графа Кэли

• 9.1. NP-трудность и кубик Рубика (17мин.)
• 9.2. Диаметр графа Кэли на абелевой группе (17мин.)
• 9.3. Диаметр графа Кэли на неабелевой группе (17мин.)
• 9.4. Диаметр графов Кэли на симметрической и знакопеременной группах (70мин.)
• Тест:  Нахождение диаметра графа Кэли (16мин.)

Тема 10. Задача о блинах

• 10.1. Постановка задачи (52мин.)
• 10.2. Алгоритм Гейтса — Пападимитроу (70мин.)
• 10.3. Верхняя оценка на диаметр блинного графа (35мин.)
• 10.4. Нижняя оценка на диаметр блинного графа (35мин.)
• 10.5. Точные значения диаметра блинного графа (35мин.)
• Тест:  Задача о блинах (10мин.)

Тема 11. Гамильтоновость графов Кэли

• 11.1. Гипотезы Ловаса и Бабаи (52мин.)
• 11.2. Комбинаторные условия для гамильтоновости (52мин.)
• 11.3. Гамильтоновость графов Кэли на симметрической группе (35мин.)
• Тест:  Гамильтоновость графов Кэли (10мин.)

Тема 12. Коды Грея

• 12.1. Гамильтоновость гиперкуба и код Грея (35мин.)
• 12.2. Иерархическое строение блинного графа (35мин.)
• 12.3. Гамильтоновость блинного графа (17мин.)
• 12.4. Порождающий алгоритм Закса (35мин.)
• 12.5. Префикс-реверсальный код Грея (35мин.)
• Тест:  Коды Грея (10мин.)

Тема 13. Спектр звездного графа

• 13.1. Целочисленные графы (17мин.)
• 13.2. Целочисленность звездного графа (17мин.)
• 13.3. Перестановки и классы сопряженности (35мин.)
• 13.4. Разбиения и таблицы Юнга (17мин.)
• 13.5. Представление симметрической группы (70мин.)
• 13.6. Пример определения кратности собственных значений графа (105мин.)
• Тест:  Спектр звездного графа (10мин.)

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

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

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