Предисловие

Введение. Происхождение теории графов

• МОЖНО ЛИ ДОВЕРЯТЬ МАТЕМАТИКЕ? | IQ (0мин.)

Глава 1. Неориентированные графы

• 1.1. Абстрактное определение графа (26мин.)
• 1.2. Определение геометрического графа (52мин.)
• 1.3. Инцидентность и смежность элементов графа (26мин.)
• • Определение инцидентности (26мин.)
  • Определение смежности (26мин.)
• 1.4. Степени вершин графа (26мин.)
• • Задачи и упражнения (26мин.)
  • Ответы и пояснения (26мин.)
• 1.5. Изоморфизм графов (52мин.)
• • Упражнения (52мин.)
  • Ответы и пояснения (26мин.)
• 1.6. Геометрические реализации абстрактных графов (104мин.)
• 1.7. Некоторые классы конечных графов (26мин.)
• • Элементарные графы (26мин.)
  • Элементарные графы с петлями (26мин.)
  • Мультиграфы и псевдографы (26мин.)
  • Однородные графы (26мин.)
  • Двудольные и k-дольные графы (26мин.)
• 1.8. Части графа (52мин.)
• • Упражнения (26мин.)
  • Ответы и пояснения (52мин.)
• 1.9. Пополнения элементарных графов (52мин.)
• 1.10. Непрерывные последовательности ребер графа (26мин.)
• • Маршруты (26мин.)
  • Цепи и циклы (26мин.)
  • Простые цепи и циклы (26мин.)
  • Упражнения (26мин.)
  • Ответы и пояснения (52мин.)
• 1.11. Связность графов (78мин.)
• • Определение связных и несвязных графов (26мин.)
  • Компоненты связности (26мин.)
  • k-связные графы (52мин.)
  • Задачи и упражнения (52мин.)
  • Ответы, указания и решения (52мин.)
• 1.12. Множества сочленения и разделяющие множества (78мин.)
• • Множества сочленения (26мин.)
  • Разделяющие множества и разрезы (52мин.)
  • Упражнения (26мин.)
  • Ответы и пояснения (104мин.)
• 1.13. Древовидные графы (78мин.)
• • Различные определения деревьев (52мин.)
  • Определение леса (26мин.)
  • Покрывающее дерево связного графа (26мин.)
  • Задачи и упражнения (26мин.)
  • Ответы, указания и решения (104мин.)
• Тест:  Неориентированные графы (44мин.)

Глава 2. Классические вопросы теории графов

• 2.1. Уникурсальные графы (156мин.)
• • Задача Эйлера о кенигсбергских мостах (26мин.)
  • Определение уникурсальных графов. Примеры (52мин.)
  • Признаки уникурсальных графов (78мин.)
  • Количество росчерков (26мин.)
  • Алгоритм нахождения эйлерова цикла (52мин.)
  • Задачи и упражнения (52мин.)
  • Ответы, указания и решения (78мин.)
• 2.2. Гамильтоновы графы (78мин.)
• • Гамильтоновы цепи и циклы (52мин.)
  • Некоторые свойства гамильтоновых графов (78мин.)
  • Задачи и упражнения (52мин.)
  • Ответы, указания и решения (104мин.)
• 2.3. Проблема планарности графов (468мин.)
• • Грани плоского графа (104мин.)
  • Теорема Эйлера о плоском графе (52мин.)
  • Двойственность плоских графов (52мин.)
  • Самодвойственные графы (78мин.)
  • Графы из многоугольников (104мин.)
  • Реберные пересечения в полных графах (182мин.)
  • Графы Понтрягина - Куратовского (52мин.)
  • Прямолинейные графы (26мин.)
  • Задачи и упражнения (52мин.)
  • Ответы, указания и решения (234мин.)
• 2.4. Раскраска графов (442мин.)
• • Раскраска граней плоского графа (390мин.)
  • Раскраска вершин графа (52мин.)
  • Раскраска ребер графа (52мин.)
  • Монохроматические треугольники (78мин.)
  • Задачи и упражнения (26мин.)
  • Ответы, указания и решения (26мин.)
• 2.5. Теория замощений (729мин.)
• • Правильные замощения плоскости (0мин.)
  • Полуправильные замощения плоскости (0мин.)
  • Правильные замощения сферы (0мин.)
  • Полуправильные плоские графы (0мин.)
• Тест:  Классические вопросы теории графов (44мин.)

Глава 3. Ориентированные графы

• 3.1. Основные понятия и свойства (182мин.)
• • Орграф и его элементы (0мин.)
  • Симметризация орграфа (0мин.)
  • Инцидентность и смежность элементов орграфа (0мин.)
  • Полустепени вершин орграфа (0мин.)
  • Изоморфизм орграфов (0мин.)
  • Элементарные орграфы (0мин.)
• 3.2. Связные орграфы (208мин.)
• • Ориентированные маршруты (0мин.)
  • Упражнения (0мин.)
  • Связность и сильная связность орграфов (0мин.)
  • Эйлеровость, согласованная с ориентацией (0мин.)
  • Гамильтоновость, согласованная с ориентацией (0мин.)
  • Ориентируемые графы (0мин.)
• 3.3. Графы бинарных отношений (156мин.)
• • Бинарные отношения и их графы (0мин.)
  • Графы бинарных отношений со свойствами (0мин.)
  • Граф отношения эквивалентности (0мин.)
• 3.4. Ориентированные графы в задачах (78мин.)
• • Задачи на ориентируемость графов (0мин.)
  • Задачи на изменения состояний системы (0мин.)
  • Задачи о выигрышных стратегиях (0мин.)
  • Задачи и упражнения (0мин.)
  • Ответы, указания и решения (0мин.)
• Тест:  Ориентированные графы (44мин.)

Используемая литература

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

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

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