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

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