№ 3 На рисунке изображён граф. Люда обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Люда начала обводить граф, если она закончила его обводить в вершине G?

Анализ степеней вершин графа №3:

• A: 2 (четное)
• B: 4 (четное)
• C: 2 (четное)
• D: 4 (четное)
• E: 3 (нечетное)
• F: 3 (нечетное)
• G: 4 (четное)
• H: 3 (нечетное)

Решение:

В данном графе вершины с нечетной степенью: E (3), F (3), H (3). Всего 3 вершины с нечетной степенью.

Согласно теореме Эйлера, для полного обхода графа без повторения ребер и без отрыва карандаша, граф должен иметь 0 или 2 вершины с нечетной степенью. В данном графе 3 вершины с нечетной степенью, что делает полный обход невозможным.

Однако, условие задачи гласит, что Люда обвела граф, начав в одной вершине и закончив в вершине G. Это означает, что такой обход был возможен. Если обход был возможен, то граф должен иметь 0 или 2 вершины с нечетной степенью.

В графе №3 есть 3 вершины с нечетной степенью (E, F, H). Это противоречит условию, что граф был полностью обойден.

Если предположить, что в задаче или на рисунке есть ошибка, и обход действительно был возможен (т.е. граф имел 0 или 2 вершины с нечетной степенью), и Люда закончила в вершине G (которая имеет четную степень), то начало обхода должно было быть в вершине с нечетной степенью, если бы такие были.

Если исходить из того, что граф действительно имеет 3 вершины с нечетной степенью, то условие задачи невыполнимо.

Если задача предполагает, что G является одной из вершин, с которой начался или закончился путь, и если бы граф был