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

Ответ: C

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

Степень вершины - это количество ребер, которые выходят из этой вершины.

Считаем степени вершин графа:

• A: 3
• B: 3
• C: 3
• D: 3
• K: 2
• N: 2

Так как у нас 4 вершины с нечетной степенью (A, B, C, D), то в графе нет ни эйлерова пути, ни эйлерова цикла. Однако, если можно начинать и заканчивать в разных вершинах, то нужно найти путь, начинающийся в B и заканчивающийся в другой вершине с нечетной степенью.

Попробуем построить путь, начиная с вершины B:

1. B - N
2. N - A
3. A - C
4. C - D
5. D - N
6. N - B
7. B - K
8. K - D
9. D - A
10. A - C

Ответ: C