Графы: маршруты и обход

Главное

Эйлеров путь проходит каждое ребро ровно один раз. Существует, если нечётных вершин 0 или 2.

Правила

1. 0 нечётных — эйлеров цикл
2. 2 нечётных — путь из одной в другую
3. Задача о кёнигсбергских мостах

Разберём пример

Можно ли обойти все мосты Кёнигсберга по одному разу?

Нет: 4 вершины нечётной степени

Частые ошибки

• Путать обход рёбер и обход вершин.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.