Реши

Для решения задачи необходимо найти Эйлеров путь. Эйлеров путь проходит по каждому ребру графа ровно один раз, начиная и заканчивая в разных вершинах. Граф имеет Эйлеров путь, если в нём не более двух вершин с нечётной степенью (числом рёбер, исходящих из вершины). Рассмотрим степени вершин графа. Посчитаем количество рёбер, соединяющих каждые вершины: 1. Вершина 1 имеет 3 рёбра. 2. Вершина 2 имеет 4 рёбра. 3. Вершина 3 имеет 3 рёбра. 4. Вершина 4 имеет 4 рёбра. 5. Вершина 5 имеет 4 рёбра. 6. Вершина 6 имеет 4 рёбра. Нечётные степени имеют вершины 1 и 3. Таким образом, Эйлеров путь существует, и он будет начинаться в одной из вершин с нечётной степенью и заканчиваться в другой. Начинаться он может в вершине 1 и заканчивается в вершине 3. Ответ: Полина начала обводить граф в вершине 1, а закончила в вершине 3.