Гамильтонов путь

Pavlovsky · Сообщение **Pavlovsky** » 31 окт 2007, 16:12

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

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

Vova · Сообщение **Vova** » 01 ноя 2007, 06:48

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

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

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

Pavlovsky · Сообщение **Pavlovsky** » 01 ноя 2007, 07:16

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

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

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

Pavlovsky · Сообщение **Pavlovsky** » 05 дек 2007, 10:41

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

malk · Сообщение **malk** » 06 дек 2007, 05:49

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

yourdomain.com