3. Какое наименьшее число рёбер придется пройти дважды, чтобы обойти все рёбра куба и вернуться в исходную вершину?

Решение:

Куб имеет 12 рёбер. Чтобы обойти все рёбра и вернуться в исходную вершину, мы можем пройти каждое ребро один раз. Такой путь существует, если в каждой вершине сходятся рёбра, общее число которых — чётное. Однако, у куба в каждой вершине сходятся 3 ребра (нечётное число).

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

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

У куба 8 вершин, и в каждой вершине сходятся 3 ребра (нечётное число). Нам нужно сделать эти степени чётными. Если мы пройдём некоторые рёбра дважды, то для этих рёбер степень вершины увеличится на 2. Нам нужно выбрать рёбра так, чтобы в итоге каждая вершина имела чётную степень. Это означает, что мы должны пройти по некоторому количеству рёбер дважды.

Пусть \( V \) — число вершин, \( E \) — число рёбер. В каждой вершине \( v \) сходятся \( deg(v) \) рёбер. Для Эйлерова цикла необходимо \( deg(v) \) — чётно для всех \( v \). У куба \( deg(v) = 3 \) для всех 8 вершин.

Чтобы сделать степень каждой вершины чётной, нам нужно пройти по рёбрам так, чтобы в каждой вершине суммарно было пройдено чётное число рёбер. Если мы проходим ребро \( (u, v) \) дважды, то \( deg(u) \) и \( deg(v) \) увеличиваются на 1. Таким образом, для каждой вершины с нечётной степенью нам нужно «добавить» один проход по ребру.

Чтобы все вершины стали чётными, нам нужно найти минимальное число рёбер, которые нужно пройти дважды. Это означает, что нам нужно соединить вершины с нечётной степенью парами. Количество вершин с нечётной степенью всегда чётно. В нашем случае все 8 вершин имеют нечётную степень (3).

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

Мы можем пройти, например, 4 рёбра, которые не образуют цикла, соединяя вершины. Например, рёбра, которые идут от одной вершины к соседним, затем к следующей, и так далее, чтобы охватить все 8 вершин. В данном случае, чтобы каждая вершина имела чётную степень, нам нужно пройти ровно 4 ребра дважды. Например, если мы возьмем 4 ребра, которые идут от одной вершины к трем соседним, и еще 3 ребра, которые идут от другой вершины к трем соседним, а оставшиеся 4 ребра идут между этими группами, то мы можем выбрать 4 ребра, которые пройдем дважды.

Например, можно пройти 4 ребра, соединяющие вершины таким образом, чтобы каждая из 8 вершин была «покрыта» одним дополнительным проходом. Пройдем 4 ребра, которые соединяют вершины. Например, возьмем 4 ребра, которые образуют квадрат на одной грани, и еще 4 ребра, которые идут вверх, и еще 4 ребра, которые образуют квадрат на другой грани. Всего 12 ребер.

Если мы пройдем 4 ребра дважды, то общее число проходов по рёбрам будет \( 12 + 4 = 16 \). Это будет путь, где каждая вершина будет иметь степень 6 (3 + 1*2 = 5, нечётное, что неверно).

Правильное рассуждение:

В графе куба 8 вершин, каждая имеет степень 3. Чтобы получить Эйлеров цикл, все вершины должны иметь чётную степень. Нам нужно увеличить степень вершин, проходя по некоторым рёбрам дважды. Прохождение ребра дважды увеличивает степень его концов на 1. Нам нужно увеличить степень всех 8 вершин на 1 (с 3 до 4).

Это означает, что нам нужно найти минимальное количество рёбер, таких, что если мы удвоим их проход, то степень каждой вершины станет чётной. Это эквивалентно нахождению минимального набора рёбер, которые образуют путь или цикл, соединяющий вершины с нечётной степенью. Нам нужно «уравновесить» степени всех вершин. Количество вершин с нечётной степенью всегда чётно.

В данном случае все 8 вершин имеют нечётную степень (3). Чтобы все вершины имели чётную степень, нам нужно пройти через 4 ребра дважды. Например, можно выбрать 4 ребра, которые не пересекаются и соединяют все 8 вершин.

Если мы пройдем 4 ребра дважды, то общее число проходимых рёбер будет \( 12 + 4 = 16 \). При этом в каждой вершине будет проходить \( 3 \) исходных ребра плюс \( 1 \) или \( 2 \) дополнительных ребра, в зависимости от того, сколько из удвоенных рёбер выходят из этой вершины.

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

Ответ: 4