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

Анализ графа №1:

• Вершина A: 2 ребра (четное)
• Вершина B: 4 ребра (четное)
• Вершина C: 4 ребра (четное)
• Вершина D: 3 ребра (нечетное)
• Вершина K: 3 ребра (нечетное)
• Вершина M: 3 ребра (нечетное)
• Вершина N: 4 ребра (четное)

Решение:

В данном графе три вершины с нечетной степенью (D, K, M). По теореме Эйлера, полный обход графа без повторения ребер и без отрыва карандаша возможен только в том случае, если граф имеет 0 или 2 вершины с нечетной степенью. Так как в графе 3 вершины с нечетной степенью, Ваня не сможет обойти его полностью, не отрывая карандаша и не проводя по ребрам дважды.

Однако, если задача предполагает нахождение *возможного* начала обхода, то Ваня может начать с любой из вершин, имеющих нечетную степень (D, K, или M), чтобы в итоге пройти по всем ребрам, но закончить придется в другой вершине с нечетной степенью.

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

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

Если же задача с подвохом, и полный обход невозможен, то правильного ответа нет.

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

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

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

В данном графе вершины D, K, M имеют нечетную степень. Если бы их было две, начинать следовало бы с одной из них.

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

Если предположить, что задача подразумевает, что обход возможен, то в графе должно быть 0 или 2 вершины с нечетной степенью. В данном графе 3 таких вершины. Поэтому полный обход невозможен.