Ответ:

Решение:

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

Рассмотрим степени вершин на данном графе:

  • Вершина A: степень 2 (четная)
  • Вершина B: степень 2 (четная)
  • Вершина C: степень 2 (четная)
  • Вершина D: степень 3 (нечетная)
  • Вершина E: степень 3 (нечетная)
  • Вершина O: степень 4 (четная)

Мы видим, что на графе есть две вершины с нечетной степенью: D и E.

По условию, Катя начала обводить граф в вершине D.

Поскольку Катя не может повторить ребра и должна закончить обход, она должна закончить в другой вершине с нечетной степенью.

Следовательно, Катя закончила обводить граф в вершине E.

Ответ: Катя закончила обводить граф в вершине E.