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

Решение:

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

Проверим степени вершин на рисунке:

• Степень вершины A: 3 (нечётная)
• Степень вершины B: 3 (нечётная)
• Степень вершины C: 4 (чётная)
• Степень вершины D: 4 (чётная)
• Степень вершины E: 2 (чётная)
• Степень вершины F: 2 (чётная)
• Степень вершины G: 2 (чётная)
• Степень вершины H: 2 (чётная)

В данном графе есть две вершины с нечётной степенью — A и B. Это означает, что начало и конец обхода графа должны приходиться на эти вершины.

По условию, Марта закончила обводить граф в вершине В. Следовательно, она должна была начать с другой вершины с нечётной степенью, то есть с вершины А.

Ответ: А