4. На рисунке изображён граф. Оля обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. Укажите вершины, с которых Оля могла начать обводить граф.

Решение:

Для того чтобы обойти граф, не отрывая карандаша и не проводя по одному ребру дважды, граф должен быть либо Эйлеровым (все вершины имеют четную степень), либо полу-Эйлеровым (ровно две вершины имеют нечетную степень).

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

Давайте определим степени вершин на рисунке:

• Степень вершины K: 2 (нечетная)
• Степень вершины A: 2 (четная)
• Степень вершины B: 2 (четная)
• Степень вершины C: 2 (четная)
• Степень вершины D: 4 (четная)
• Степень вершины M: 4 (четная)
• Степень вершины T: 2 (четная)
• Степень вершины P: 2 (четная)
• Степень вершины N: 2 (четная)

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

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

• K: 2 ребра (четная)
• A: 2 ребра (четная)
• B: 2 ребра (четная)
• C: 2 ребра (четная)
• D: 4 ребра (четная)
• M: 4 ребра (четная)
• T: 2 ребра (четная)
• P: 2 ребра (четная)
• N: 2 ребра (четная)

Внимательно смотрим на изображение графа. Видно, что граф имеет 2 вершины с нечетной степенью: K (2 ребра) и A (2 ребра). А также вершины D и M имеют степень 4. Все остальные вершины имеют степень 2.

Давайте пересчитаем степени вершин еще раз, внимательно смотря на рисунок:

• K: 2 ребра (четная)
• A: 2 ребра (четная)
• B: 2 ребра (четная)
• C: 2 ребра (четная)
• D: 4 ребра (четная)
• M: 4 ребра (четная)
• T: 2 ребра (четная)
• P: 2 ребра (четная)
• N: 2 ребра (четная)

Внимательно вглядевшись в рисунок, я вижу, что в вершине D сходятся 4 ребра. В вершине M сходятся 4 ребра. В вершинах K, A, B, C, T, P, N сходятся по 2 ребра.

Таким образом, все вершины имеют четную степень. Такой граф называется Эйлеровым.

В Эйлеровом графе можно начать и закончить обход в любой вершине.

Однако, в условии сказано: «не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды». Это условие выполняется для Эйлерова цикла (начинаем и заканчиваем в одной вершине) или Эйлерова пути (начинаем и заканчиваем в разных вершинах).

Для Эйлерова пути (нечетные степени) начало и конец — это вершины нечетной степени.

Для Эйлерова цикла (четные степени) начало и конец — это любая вершина.

В нашем графе ВСЕ вершины имеют ЧЕТНУЮ степень (2 или 4). Это значит, что это Эйлеров граф.

В Эйлеровом графе можно начать и закончить обход с ЛЮБОЙ вершины.

Но если вопрос подразумевает, что Оля могла НАЧАТЬ с вершины, то это любая вершина.

Давайте еще раз посмотрим на картинку. Я вижу, что вершины K, A, B, C, N, T, P имеют степень 2. Вершины D и M имеют степень 4. Все вершины имеют четную степень.

Следовательно, Оля могла начать обводку графа с ЛЮБОЙ из указанных вершин.

В качестве ответа нужно указать вершины.

Ответ: K, A, B, C, D, M, T, P, N (любая вершина)