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

Решение:

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

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

• Степень вершины A: 3 (ребра AB, AC, AF)
• Степень вершины B: 2 (ребра BA, BC)
• Степень вершины C: 4 (ребра CB, CD, CA, CO)
• Степень вершины D: 2 (ребра DC, DE)
• Степень вершины E: 2 (ребра ED, EF)
• Степень вершины F: 3 (ребра FA, FE)
• Степень вершины O: 2 (ребра OA, OC)

В данном графе две вершины имеют нечётную степень: A и F.

Чтобы обойти граф, начав и закончив в разных вершинах, нужно, чтобы ровно две вершины имели нечётную степень. В этом случае начинать обход нужно с одной из вершин с нечётной степенью (A или F) и закончить в другой.

Ответ: Ване стоит начать обводить граф с вершины A или F.