Вопрос:

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

Ответ:

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

Похожие