Можно ли обойти все рёбра куба, пройдя по каждому ребру ровно один раз? В ответе запишите 1, если это возможно, или 0, если невозможно.
Решение. Будем считать вершины куба вершинами графа, а ребра куба — ребрами графа. Обход всех ребер куба означает, что граф можно нарисовать, не отрывая карандаша от бумаги, пройдя все ребра по одному разу.
Рисуя граф так, как требуется в условии, в каждую вершину, за исключением начальной и конечной, нужно войти столько же раз, сколько выйти из нее. Поэтому в графе должно быть либо ровно две вершины нечетной степени (начальная и конечная), либо вершин нечетной степени нет, если конечная вершина совпадает с начальной.
Но в этом графе 8 вершин нечетного индекса, поэтому требуемое невозможно.
Ответ: 0.
Ответ: 0
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем