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

Для решения этой задачи нужно найти вершину, из которой можно начать обход графа, не отрывая карандаша и не повторяя рёбра, так, чтобы закончить в вершине М. Это задача на поиск Эйлерова пути.

Признак существования Эйлерова пути:

• В графе должно быть либо 0 вершин с нечетной степенью (тогда существует Эйлеров цикл, и начинать/заканчивать можно из любой вершины), либо ровно 2 вершины с нечетной степенью (тогда существует Эйлеров путь, который начинается в одной из этих вершин и заканчивается в другой).

Анализ степеней вершин:

• A: степень 3 (рёбра AB, AF, AK)
• B: степень 3 (рёбра BA, BC, BM)
• C: степень 3 (рёбра CB, CD, CN)
• D: степень 3 (рёбра DC, DE, DP)
• E: степень 3 (рёбра ED, EF, EQ)
• F: степень 3 (рёбра FA, FE, FL)
• L: степень 2 (рёбра LK, LF)
• K: степень 2 (рёбра KA, KL)
• Q: степень 2 (рёбра QE)
• M: степень 2 (рёбра MB, MN)
• N: степень 2 (рёбра NC, NM)
• P: степень 2 (рёбра PD)

В данном графе 8 вершин имеют нечетную степень (A, B, C, D, E, F) и 4 вершины имеют четную степень (L, K, Q, M, N, P).

Поскольку вершин с нечетной степенью больше двух, Эйлеров путь (или цикл) в этом графе не существует. Это означает, что Лёва не мог обойти весь граф, не отрывая карандаша и не повторяя рёбра.

Однако, если предположить, что в условии подразумевается не полный обход всего графа, а некоторая его часть, или что в графе есть ошибки, и он должен быть допустимым для Эйлерова пути, мы могли бы искать начало пути. Но при заданных условиях, Эйлеров путь невозможен.

Исходя строго из предоставленной информации и рисунка, задача не имеет решения в рамках теории графов об Эйлеровом пути.