13. Тип 11 № 11329. Какое наименьшее число рёбер придется пройти дважды, чтобы обойти все рёбра куба?

Решение:

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

У куба 8 вершин, и каждая вершина имеет степень 3 (из каждой вершины выходит 3 ребра).

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

Так как у куба все 8 вершин имеют нечётную степень (3), то ни Эйлерова пути, ни Эйлерова цикла не существует. Чтобы обойти все рёбра, нам придётся пройти некоторые рёбра повторно.

Минимальное число повторных проходов равно половине количества вершин с нечётной степенью, так как каждый повторный проход «превращает» две вершины нечётной степени в чётные (входящее ребро и исходящее ребро).

Количество вершин с нечётной степенью = 8.

Минимальное число рёбер, которые придётся пройти дважды = \( \frac{8}{2} = 4 \).

Ответ: 4.