Путь в графе

[Danila44]

Существует в графе "каркас куба" путь, проходящий через одну из вершин 25 раз, а через остальные - по 30?

[maxal]

С каждым ребром ассоциируйте неизвестную, равную количеству прохождений пути через это ребро, а для каждой вершины запишите уравнение вида: сумма неизвестных соответствующих инцидентным ребрам равна удвоенному числу посещений вершины (для замкнутого пути или неконцевой вершины незамкнутого пути) или ему же уменьшенному на 1 (для концевой вершины незамкнутого пути). Если получившаяся система имеет решение - путь существует, а нет - так нет.

[sergey1]

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

[Danila44]

Спасибо всем ответившим! Второй вариант особенно понравился - и как я сам не смог сообразить...

[DrGonzo]

Добрый день.
Сейчас пытаюсь решить эту же задачу. Логика была примерно такая же, как у maxal.

Составил систему линейный уравнений, обозначив за неизвестные количество проходов по рёбрам. А в качестве столбца свободных членов взял посещения вершин, домноженные на 2 (т.е. 60 и один член 50).

Для существования пути система должна быть совместной.

Проверил - получилось. Вроде бы всё, но что-то терзают меня смутные сомнения...