На рисунке изображён граф. Аня обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Аня начала обводить граф, если она закончила его обводить в вершине ?
Показать решение
Аня проходит каждое ребро ровно один раз, не отрывая карандаша — это эйлеров путь в графе.
Найдём степени вершин (сколько рёбер выходит из каждой вершины):
— 3; — 3; — 2; — 2; — 2.
Вершины нечётной степени: и .
Эйлеров путь существует тогда и только тогда, когда вершин нечётной степени ровно две (или ни одной). Если таких вершин две, путь обязан начинаться в одной из них и заканчиваться в другой.
По условию обход закончился в вершине . Значит, он начался в вершине .
Ответ: .
Теория
Эйлеров путь в графе — это путь, который проходит по каждому ребру ровно один раз (вершины при этом можно посещать несколько раз).
Степень вершины — число рёбер, выходящих из этой вершины.
Критерий:
- если все вершины чётной степени — эйлеров путь существует и может начинаться в любой вершине (это эйлеров цикл);
- если ровно две вершины нечётной степени — эйлеров путь существует и начинается в одной из них, а заканчивается в другой;
- если нечётных вершин больше двух — такого пути нет.
Поэтому в задачах вида «закончила в вершине X — с какой начала?» достаточно найти две вершины нечётной степени: ответ — вторая из них.