На рисунке изображён граф, а в вариантах ответа — пути для этого графа. Выбери все варианты ответа, в которых указан эйлеров путь.

Решение:

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

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

• Степень вершины C: 2 (рёбра CB, CK, CN)
• Степень вершины K: 2 (рёбра KC, KM, KN)
• Степень вершины N: 3 (рёбра NC, NK, NB)
• Степень вершины B: 3 (рёбра BN, BK, BM)
• Степень вершины M: 2 (рёбра MK, MB)

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

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

• K–M–B–N–C–K–N: В этом пути вершина K повторяется, а ребро KN пройдено дважды. Это не эйлеров путь.
• M–K–C–N–B–M: Проверим прохождение всех рёбер. Ребра: MK, KC, CN, NB, BM. Ребро BK не пройдено. Это не эйлеров путь.
• N–C–K–M–B–N–K: Этот путь начинается с N и заканчивается K. У нас две вершины с нечетной степенью N и B. Этот путь содержит 7 вершин и 6 рёбер, что соответствует количеству рёбер в графе. Проверим уникальность прохождения рёбер: NC, CK, KM, MB, BN, NK. Все рёбра графа пройдены по одному разу. Этот путь является эйлеровым.
• B–N–K–C–N–B–M–K: Этот путь имеет 8 вершин и 7 ребер. В графе 6 ребер. Это не эйлеров путь.

Таким образом, единственным эйлеровым путём является N–C–K–M–B–N–K.

Ответ: N–C–K–M–B–N–K