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

Решение: Чтобы граф можно было обвести, не отрывая карандаша и не проходя ни по одному ребру дважды, необходимо, чтобы количество вершин, из которых выходит нечетное число ребер, было не больше двух. В данном графе вершины A, B, C, D, E, G имеют нечетное количество ребер (3 ребра у A, B, D, G, и 1 ребро у C и E). Так как Аня закончила обводить граф в вершине Е, значит, начала она в вершине с нечетным количеством ребер. Чтобы обвести граф, нужно чтобы количество нечетных вершин было равно двум. Следовательно, Аня должна была начать в вершине, имеющей нечетное количество ребер. Это вершины A, B, D, G. Однако вершины А и B не связаны напрямую с вершиной Е, поэтому обойти граф и закончить в вершине Е не получится, начав обход в вершине А или В. Если начать обход в вершине D или G, то можно закончить в вершине Е. Таким образом, можно сделать вывод, что граф был начат обводиться либо в вершине D, либо в вершине G. Без дополнительной информации невозможно однозначно определить, какая из этих двух вершин была начальной. Если предполагать, что вопрос требует единственного ответа, можно рассмотреть случай, когда нужно пройти все ребра, а значит, начинать нужно с вершины, у которой максимальная степень (количество ребер). Максимальная степень у вершин A, B, D и G. Из этих вершин только D и G могут привести к E. Поэтому возможные ответы D или G. Ответ: D или G