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

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

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

Проанализировав граф на рисунке, видим следующее:

1. Из вершины D Катя могла пойти только в вершину G.
2. Из G можно перейти в E или H.
3. От H есть возможность перейти к F, а от E - к A.
4. В F она могла пойти либо в B, либо в С.

Для завершения обвода в графе, будут следующие возможные пути:

• D -> G -> E -> A
• или D -> G -> H -> F -> C
• или D -> G -> H -> F -> B

Таким образом, Катя должна была закончить обвод в одной из вершин: A, B или C.