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

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

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

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

• Вершина 1: степень 4
• Вершина 2: степень 3
• Вершина 3: степень 3
• Вершина 4: степень 4
• Вершина 5: степень 2
• Вершина 6: степень 2
• Вершина 7: степень 3
• Вершина 8: степень 3

У нас четыре вершины с нечетной степенью: 2, 3, 7, и 8. Так как Пётр закончил обход в вершине 3, значит, он начал обход в одной из вершин 2, 7 или 8.

Рассмотрим вариант, что Пётр начал обход в вершине 7.

Ответ: 7