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

Решение:

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

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

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

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