вероятность и статистика · 7 класс · урок 19
Эйлеров путь. Задача о кёнигсбергских мостах
Кёнигсбергские мосты · эйлеров цикл · правило Эйлера
Запомни
- Эйлеров путь проходит по каждому ребру графа ровно один раз. Если он заканчивается там, где начался, — это эйлеров цикл.
- Нечётных вершин нет — есть эйлеров цикл. Начинать можно с любой вершины.
- Нечётных вершин две — есть эйлеров путь: он начинается в одной нечётной вершине и заканчивается в другой.
- Нечётных вершин больше двух — обойти граф нельзя. В Кёнигсберге степени 5, 3, 3, 3 — прогулка невозможна.
О чём урок
Сегодня мы узнаем, как нарисовать фигуру, не отрывая карандаша от бумаги, и решим знаменитую задачу о мостах города Кёнигсберга.
Задача из урока
Можно ли обойти граф, пройдя по каждому ребру ровно один раз? Если да, с какой вершины начать?
Ответ и решение по шагам: в тренажёре урока после покупки курса. Урок 01 и его тренажёр бесплатные.