Глава 19. Вероятность и статистика. Введение в теорию графов
§ 67.
Эйлеров путь и ориентированные графы
Эйлеров путь и ориентированные графы
Проверяйте возможность обхода всех рёбер и учитывайте направление дуг.
Запомни
Записывайте решение последовательно. Для вычислительных задач делайте проверку, для текстовых — указывайте модель и единицы, для геометрических — чертёж и обоснования.
Вопросы и задания
- Нарисуйте связный граф, имеющий эйлеров цикл.
- Нарисуйте связный граф, имеющий эйлеров путь, но не цикл.
- Можно ли обвести прямоугольник с обеими диагоналями одним росчерком без повторения рёбер? Обоснуйте степенями вершин.
- Проверьте задачу о кёнигсбергских мостах на упрощённой схеме с четырьмя вершинами степеней 3, 3, 3, 5.
- Постройте ориентированный граф переходов между страницами сайта A, B, C, если A→B, A→C, B→C, C→A.
- Найдите ориентированные пути из A в C в графе задания 5.
- Объясните, почему расписание авиарейсов удобно представлять ориентированным графом.
- Составьте маршрут уборочной машины, проходящий по каждому участку дороги ровно один раз, либо докажите невозможность.
Ключевые понятия:Вероятность и статистика7 классэйлеров путьориентированный графобход