13. Тип 11 Какое наименьшее число рёбер придетс обойти все рёбра куба и вернуться в исходную вершин

Решение:

В кубе 8 вершин. Из каждой вершины выходит 3 ребра. Чтобы обойти все ребра куба и вернуться в исходную вершину, нужно пройти по каждому ребру хотя бы один раз.

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

Чтобы сделать степень каждой вершины четной, нужно добавить ребра, проходя по ним повторно. Минимальное количество ребер, которые нужно пройти повторно, равно количеству вершин с нечетной степенью, деленному на 2. В кубе 8 вершин с нечетной степенью. Следовательно, нужно пройти повторно минимум 8 / 2 = 4 ребра.

Таким образом, наименьшее число ребер, которое придется обойти, равно 12 (все ребра) + 4 (повторно пройденные ребра) = 16.

Ответ: 4