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

Решение:

• Задача сводится к поиску Эйлерова пути в графе. Эйлеров путь существует, если в графе ровно две вершины имеют нечетную степень (вершины, из которых выходит нечетное число ребер), или если все вершины имеют четную степень (в этом случае путь будет Эйлеровым циклом, и начало с концом совпадают).
• В данном графе вершины имеют следующие степени:
  • A: 3
  • B: 3
  • C: 2
  • D: 4
  • E: 1
  • F: 4
  • G: 2
• Вершины с нечетной степенью: A (3), B (3), E (1). Таким образом, в графе три вершины с нечетной степенью.
• По условию задачи, Аня начала обводить граф с одной вершины и закончила в вершине E. Это означает, что вершины, с которых начался и закончился обход, должны иметь нечетную степень.
• Так как в графе есть три вершины с нечетной степенью (A, B, E), и обход начался с одной из них и закончился в E, то начало обхода могло быть либо из вершины A, либо из вершины B.
• Однако, если бы она начала из A и закончила в E, то вершины B осталась бы с нечетной степенью, что противоречит условию, что она обвела весь граф. Аналогично, если бы она начала из B и закончила в E.
• Это означает, что в графе должен быть Эйлеров путь, начинающийся в одной из вершин с нечетной степенью и заканчивающийся в другой.
• Учитывая, что Аня закончила в вершине E (степень 1), а в графе есть еще вершины A (степень 3) и B (степень 3) с нечетной степенью, то для того, чтобы путь был полным, она должна была начать либо из A, либо из B.
• Если она начала из A и закончила в E, то B должна была быть пройдена, но это невозможно, так как тогда B имела бы нечетную степень.
• Следовательно, начало и конец обхода должны быть двумя вершинами с нечетной степенью. В нашем случае это A и B. Так как конец обхода E, то это условие не выполняется.
• Однако, если рассматривать граф, как показано на рисунке, и учитывать, что Аня не отрывала карандаш, то путь должен быть непрерывным.
• Вершины с нечетной степенью: A, B, E.
• Для существования Эйлерова пути, граф должен иметь 0 или 2 вершины с нечетной степенью. Так как у нас 3 вершины с нечетной степенью, то полного обхода всех ребер без повторений и без отрыва карандаша быть не может, если мы рассматриваем каждую вершину как точку, из которой выходят ребра.
• Но в задаче сказано, что она обвела граф. Если рассматривать это как нахождение Эйлерова пути, то начало и конец должны быть вершинами с нечетной степенью.
• Так как Аня закончила в вершине E, которая имеет нечетную степень (1), то она должна была начать с другой вершины, имеющей нечетную степень. Такими вершинами являются A (3) и B (3).
• Следовательно, она могла начать либо с A, либо с B.

Ответ: А или В