Предисловие

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

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

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

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

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

• 2.1. Уникурсальные графы (251мин.)
• • Задача Эйлера о кенигсбергских мостах (18мин.)
  • Определение уникурсальных графов. Примеры (36мин.)
  • Признаки уникурсальных графов (54мин.)
  • Количество росчерков (18мин.)
  • Алгоритм нахождения эйлерова цикла (36мин.)
  • Задачи и упражнения (36мин.)
  • Ответы, указания и решения (54мин.)
• 2.2. Гамильтоновы графы (197мин.)
• • Гамильтоновы цепи и циклы (36мин.)
  • Некоторые свойства гамильтоновых графов (54мин.)
  • Задачи и упражнения (36мин.)
  • Ответы, указания и решения (72мин.)
• 2.3. Проблема планарности графов (663мин.)
• • Грани плоского графа (72мин.)
  • Теорема Эйлера о плоском графе (36мин.)
  • Двойственность плоских графов (36мин.)
  • Самодвойственные графы (54мин.)
  • Графы из многоугольников (72мин.)
  • Реберные пересечения в полных графах (125мин.)
  • Графы Понтрягина - Куратовского (36мин.)
  • Прямолинейные графы (18мин.)
  • Задачи и упражнения (36мин.)
  • Ответы, указания и решения (161мин.)
• 2.4. Раскраска графов (484мин.)
• • Раскраска граней плоского графа (269мин.)
  • Раскраска вершин графа (36мин.)
  • Раскраска ребер графа (36мин.)
  • Монохроматические треугольники (54мин.)
  • Задачи и упражнения (18мин.)
  • Ответы, указания и решения (72мин.)
• 2.5. Теория замощений (717мин.)
• • Правильные замощения плоскости (72мин.)
  • Полуправильные замощения плоскости (269мин.)
  • Правильные замощения сферы (36мин.)
  • Полуправильные плоские графы (269мин.)
• Тест:  Классические вопросы теории графов (44мин.)

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

• 3.1. Основные понятия и свойства (161мин.)
• • Орграф и его элементы (36мин.)
  • Симметризация орграфа (18мин.)
  • Инцидентность и смежность элементов орграфа (18мин.)
  • Полустепени вершин орграфа (36мин.)
  • Изоморфизм орграфов (18мин.)
  • Элементарные орграфы (36мин.)
• 3.2. Связные орграфы (233мин.)
• • Ориентированные маршруты (36мин.)
  • Упражнения (18мин.)
  • Связность и сильная связность орграфов (36мин.)
  • Эйлеровость, согласованная с ориентацией (90мин.)
  • Гамильтоновость, согласованная с ориентацией (36мин.)
  • Ориентируемые графы (36мин.)
• 3.3. Графы бинарных отношений (143мин.)
• • Бинарные отношения и их графы (72мин.)
  • Графы бинарных отношений со свойствами (36мин.)
  • Граф отношения эквивалентности (36мин.)
• 3.4. Ориентированные графы в задачах (125мин.)
• • Задачи на ориентируемость графов (18мин.)
  • Задачи на изменения состояний системы (36мин.)
  • Задачи о выигрышных стратегиях (18мин.)
  • Задачи и упражнения (36мин.)
  • Ответы, указания и решения (18мин.)
• Тест:  Ориентированные графы (44мин.)

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

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

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

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