Контрольные задания > На рисунке изображён граф. Оля обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. Укажите вершины, с которых Оля могла начать обводить граф.
Вопрос:
На рисунке изображён граф. Оля обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. Укажите вершины, с которых Оля могла начать обводить граф.
Ответ:
Чтобы Оля могла обвести граф, не отрывая карандаша и не проходя по одному ребру дважды, нужно, чтобы граф был эйлеровым или полуэйлеровым. Эйлеров граф - это граф, в котором все вершины имеют четную степень (четное количество ребер, выходящих из вершины). Полуэйлеров граф - это граф, в котором ровно две вершины имеют нечетную степень. Начать обход полуэйлерова графа можно только из одной из этих двух вершин.
Считаем степени вершин:
* A: 2
* B: 4
* C: 4
* D: 2
* E: 2
Все вершины имеют четную степень. Это означает, что граф эйлеров. Начать обход можно с любой вершины.
Ответ: **A, B, C, D, E**.