7. Найди путь Условие задания: Выбери все варианты ответа, в которых указан эйлеров путь для графа, изображённого на рисунке. N B C K M-K-C-N-B-M ON-C-K-M-B-N-K OK-C-N-B-M-K ON-K-M-C-N-B Ответить!

Решение:

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

В данном графе степени вершин:

• Вершина C: степень 2 (ребра CK, CN)
• Вершина K: степень 3 (ребра KC, KN, KM)
• Вершина M: степень 3 (ребра MK, MN, MB)
• Вершина N: степень 3 (ребра NC, NK, NM, NB)
• Вершина B: степень 2 (ребра BN, BM)

Граф имеет 4 вершины с нечетной степенью (K, M, N). Согласно теореме Эйлера, для существования эйлерова пути необходимо, чтобы в графе было не более двух вершин с нечетной степенью. В данном графе 4 вершины с нечетной степенью, поэтому эйлерова пути не существует.

Пересмотрим степени вершин, так как на рисунке изображен полный граф K4 с одной вершиной (C) добавленной сверху, соединенной с двумя вершинами (N, K).

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

• Вершина C: 2 (связана с N и K)
• Вершина N: 3 (связана с C, K, B)
• Вершина K: 3 (связана с C, N, M)
• Вершина B: 2 (связана с N и M)
• Вершина M: 2 (связана с K и B)

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

Проверим предложенные варианты:

• M-K-C-N-B-M: Проходит по ребру M-K, K-C, C-N, N-B, B-M. Ребро K-N не пройдено. Не является эйлеровым путем.
• N-C-K-M-B-N-K: Проходит по ребру N-C, C-K, K-M, M-B, B-N. Ребро K-N пройдено дважды. Не является эйлеровым путем.
• K-C-N-B-M-K: Проходит по ребру K-C, C-N, N-B, B-M, M-K. Это путь, который проходит по всем ребрам ровно один раз. Начинается в K (нечетная степень) и заканчивается в K (нечетная степень) - это не верно. Он должен заканчиваться в другой нечетной вершине.
• N-K-M-B-N-C-K: Проверим путь K-C-N-B-M-K. Вершины K, C, N, B, M. Ребра: (K,C), (C,N), (N,B), (B,M), (M,K). Все ребра пройдены. Старт K, конец K. Это эйлеров цикл, но эйлеров путь должен начинаться в одной нечетной вершине и заканчиваться в другой.

Пересмотрим условие: