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

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