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

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