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

Решение:

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

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

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

• D: 3 (нечетная степень)
• H: 4 (четная степень)
• K: 4 (четная степень)
• C: 4 (четная степень)
• G: 4 (четная степень)
• A: 2 (четная степень)
• B: 2 (четная степень)
• F: 2 (четная степень)
• E: 2 (четная степень)
• L: 1 (нечетная степень)

В данном графе есть две вершины с нечетной степенью: D (3) и L (1). Поскольку Катя начала обход в вершине D, она должна закончить его в вершине L, чтобы пройти по Эйлерову пути.

Ответ: L