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

Решение:

Граф можно обойти без отрыва карандаша и без повторения ребер, если он является Эйлеровым или содержит не более двух вершин нечетной степени (если начинать и заканчивать в разных вершинах).

В данном графе степени вершин следующие:

• Вершина D: степень 3 (ребра DK, DC, DA)
• Вершина K: степень 3 (ребра KD, KB, KF)
• Вершина C: степень 2 (ребра CD, CA)
• Вершина A: степень 4 (ребра AD, AC, AF, AN)
• Вершина B: степень 2 (ребра BK, BN)
• Вершина F: степень 2 (ребра FK, FN)
• Вершина N: степень 2 (ребра NA, NF)

Мы видим, что вершины D и K имеют нечетную степень (3). Все остальные вершины имеют четную степень.

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

В данном графе таких вершин две: D и K. Поскольку Алла начал в вершине D, он должен закончить в вершине K.

Ответ: K.