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

Обоснование:

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

Ключевые понятия:

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

Условия существования эйлерова пути/цикла в неориентированном графе:

• Эйлеров цикл существует тогда и только тогда, когда все вершины графа имеют чётную степень.
• Эйлеров путь существует тогда и только тогда, когда в графе ровно две вершины имеют нечётную степень. Эти две вершины будут началом и концом эйлерова пути.

Анализ графа (первого графа на рисунке):

Подсчитаем степени вершин:

• Степень вершины А = 3 (рёбра А-Б, А-В, А-Г) - нечётная
• Степень вершины Б = 2 (рёбра Б-А, Б-Е) - чётная
• Степень вершины В = 3 (рёбра В-А, В-3) - нечётная
• Степень вершины Г = 2 (рёбра Г-А, Г-Ж) - чётная
• Степень вершины Д = 1 (ребро Д-Ж) - нечётная
• Степень вершины Ж = 3 (рёбра Ж-Г, Ж-Д, Ж-К) - нечётная
• Степень вершины Е = 2 (рёбра Е-Б, Е-И) - чётная
• Степень вершины З = 3 (рёбра З-В, З-Е, З-К) - нечётная
• Степень вершины И = 2 (рёбра И-Е, И-Л) - чётная
• Степень вершины К = 3 (рёбра К-Ж, К-З, К-Л) - нечётная
• Степень вершины Л = 2 (рёбра Л-И, Л-К) - чётная

Результат подсчета:

Вершины с нечётной степенью: А (3), В (3), Д (1), Ж (3), З (3), К (3). Всего 6 вершин с нечётной степенью.

Вывод:

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

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

Если мы предположим, что задача сформулирована корректно и такой обход возможен, то либо в графе должно быть 0 или 2 вершины с нечетной степенью, либо Аня каким-то образом