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

Анализ задачи

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

Пошаговое решение:

1. Анализ графа: Граф представляет собой звездообразную фигуру, вписанную в окружность, с центром O. Вершины обозначены буквами A, B, C, D, E, F.
2. Определение степеней вершин:
   • Вершина A: степень 2 (ребра AB, AF)
   • Вершина B: степень 3 (ребра BA, BC, BO)
   • Вершина C: степень 2 (ребра CB, CD)
   • Вершина D: степень 3 (ребра DC, DE, DO)
   • Вершина E: степень 2 (ребра ED, EF)
   • Вершина F: степень 3 (ребра FE, FA, FO)
   • Вершина O: степень 3 (ребра OB, OD, OF)
3. Выявление вершин с нечетной степенью: Вершины B, D, F и O имеют степень 3 (нечетную).
4. Условие для обхода: Граф имеет более двух вершин с нечетной степенью (4 вершины: B, D, F, O). Следовательно, обойти данный граф за один раз, не отрывая карандаша и не проводя ребра дважды, невозможно.

Ответ: Обойти данный граф за один раз невозможно, так как он имеет более двух вершин с нечетной степенью.