11. Тип 11 № 8719 i На рисунке изображён граф. Ваня обвёл этот граф, не отрывая каранда- ша от листа бумаги и не проводя ни одно ребро дважды. С какой верши- ны Ваня начал обводить граф, если он закончил его обводить в верши- не Е?

Ответ: N

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

Граф содержит следующие вершины: A, B, C, D, E, F, G, H, K, L, M, N.

Степень вершины - это количество ребер, инцидентных этой вершине. Посчитаем степени каждой вершины:

• A: 3
• B: 3
• C: 3
• D: 3
• E: 3
• F: 3
• G: 2
• H: 2
• K: 2
• L: 2
• M: 2
• N: 4

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

В данном графе вершины G, H, K, L, M имеют степень 2, вершины A, B, C, D, E, F имеют степень 3, а вершина N имеет степень 4.

Начальная и конечная вершины должны иметь нечетную степень, если они различны. Конечная вершина - E. Значит, E должна быть вершиной нечетной степени. Другая вершина нечетной степени - N. Ваня начал обход с вершины N.

Ответ: N