yourdomain.com

Что то не дается задачка. Дан граф.

Найти в нем гамильтонов путь. Путь проходящий через все вершины, ровно один раз. Или доказать, что это невозможно.

Pavlovsky писал(а):Source of the post
Что то не дается задачка. Дан граф.

Найти в нем гамильтонов путь. Путь проходящий через все вершины, ровно один раз. Или доказать, что это невозможно.

...начать и закончить в какой точке?
...дуги тоже проходить?

начать и закончить можно в любой точке.

...дуги тоже проходить?

Если имелось ввиду пройти все дуги. To в сочетании c условием через каждую вершину проходить один раз. To это просто невозможно.
A так от вершины к вершине надо проходить по дугам.

Осмелюсь поднять тему. Вроде задача простенькая. A вот мыслей никаких.

Этот граф - куб, у которого соеденены середины ребер отрезками, параллельными
соседним ребрам (что-то вроде клетки). Если сложить все координаты точки(длина ребра 2)
то получится четное или нечетное. "Четных" точек 12, "нечетных" 14. "Четные" соединяются
только c "нечетными", a "нечетными" только c "четными". Следовательно в пути должно быть
13 "нечетных" и 13 "четных".