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

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

• Граф имеет вершины A, B, C, D, E.
• Подсчитаем количество ребер (степень вершины) для каждой вершины:
• Вершина A: 2 ребра (AD, AB)
• Вершина B: 3 ребра (BA, BC, BD)
• Вершина C: 2 ребра (CB, CD)
• Вершина D: 3 ребра (DA, DB, DC)
• Вершина E: 1 ребро (EB)
• Вершины с нечетной степенью: B, D, E.
• Для обхода графа без повторения ребер и без отрыва карандаша, начало и конец обхода должны быть в вершинах с нечетной степенью. Если таких вершин две, то начало и конец обхода совпадают с этими вершинами. Если таких вершин больше двух, то обойти граф таким образом невозможно.
• В данном графе вершины B, D, E имеют нечетную степень. Однако, согласно условию, Петя закончил обводить граф в вершине E. Это значит, что начало обхода должно быть в другой вершине с нечетной степенью.
• Следовательно, Петя начал обводить граф с вершины D.

Ответ: D