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

Для решения этой задачи, необходимо определить, какие вершины графа имеют нечётную степень (количество рёбер, выходящих из вершины). Обход графа без отрыва карандаша возможен только в том случае, если количество вершин с нечётной степенью равно 0 или 2. Если таких вершин две, то обход должен начинаться в одной из них и заканчиваться в другой. Подсчитаем степени вершин: - A: 2 - M: 4 - N: 4 - B: 2 - P: 2 - C: 2 - K: 2 Все вершины имеют чётную степень. Это означает, что Петя мог начать обвод графа с любой вершины и вернуться в неё же. Поскольку Петя закончил обвод в вершине M, то он и начал обвод с вершины M.