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

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