На рисунке изображён граф. Оля обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. Укажите вершины, с которых Оля могла начать обводить граф.

Привет! Разберёмся с этой задачей. Нам нужно найти вершины, с которых Оля может начать обводить граф, не отрывая карандаша и не проходя по одному ребру дважды. Такая задача связана с Эйлеровыми графами.

Логика такая:

• Нужно определить количество нечётных вершин (вершин, из которых выходит нечётное количество рёбер).
• Если в графе 0 или 2 нечётные вершины, то существует Эйлеров путь (или цикл).
• Если 0 нечётных вершин, то начинать можно с любой вершины.
• Если 2 нечётные вершины, то начинать нужно с одной из них.

В нашем графе вершины A и E имеют 3 ребра (нечётные), а остальные вершины (B, C, D, M, N) имеют чётное количество ребер.

Таким образом, Оля могла начать обводить граф с вершин A или E.

Ответ: A, E

Проверка за 10 секунд: Убедись, что выбранные тобой вершины имеют нечётную степень (количество рёбер).

Доп. профит: Помни, что если в графе больше двух нечётных вершин, то нельзя нарисовать граф, не отрывая карандаша и не проводя по одному ребру дважды.