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

Ответ: M, N, K, P.

Чтобы обвести граф, не отрывая карандаша и не проходя по одному ребру дважды, необходимо, чтобы граф был эйлеровым или полуэйлеровым. Эйлеров граф — это граф, в котором все вершины имеют четную степень (количество ребер, выходящих из вершины). Полуэйлеров граф — это граф, в котором ровно две вершины имеют нечетную степень.

Определим степени каждой вершины:

• M: 3 (нечетная)
• N: 3 (нечетная)
• B: 4 (четная)
• C: 4 (четная)
• D: 2 (четная)
• K: 3 (нечетная)
• P: 3 (нечетная)

Граф имеет четыре вершины с нечетной степенью (M, N, K, P), следовательно, он не является ни эйлеровым, ни полуэйлеровым. Однако, если разрешено начинать и заканчивать в разных вершинах, то обход возможен, если начинать в одной из вершин с нечетной степенью.

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

Ответ: M, N, K, P.