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

Решение:

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

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

Теорема:

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

Анализ графа на рисунке:

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

• Вершина A: степень 2 (четная)
• Вершина B: степень 2 (четная)
• Вершина C: степень 4 (четная)
• Вершина D: степень 2 (четная)
• Вершина G: степень 2 (четная)
• Вершина H: степень 2 (четная)
• Вершина K: степень 4 (четная)
• Вершина L: степень 2 (четная)

Вывод:

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

Ответ: С любой вершины.