Что то не дается задачка. Дан граф.
Найти в нем гамильтонов путь. Путь проходящий через все вершины, ровно один раз. Или доказать, что это невозможно.
Гамильтонов путь
Гамильтонов путь
Последний раз редактировалось Pavlovsky 30 ноя 2019, 13:59, всего редактировалось 1 раз.
Причина: test
Причина: test
Гамильтонов путь
Pavlovsky писал(а):Source of the post
Что то не дается задачка. Дан граф.
Найти в нем гамильтонов путь. Путь проходящий через все вершины, ровно один раз. Или доказать, что это невозможно.
...начать и закончить в какой точке?
...дуги тоже проходить?
Последний раз редактировалось Vova 30 ноя 2019, 13:59, всего редактировалось 1 раз.
Причина: test
Причина: test
Гамильтонов путь
начать и закончить можно в любой точке.
Если имелось ввиду пройти все дуги. To в сочетании c условием через каждую вершину проходить один раз. To это просто невозможно.
A так от вершины к вершине надо проходить по дугам.
...дуги тоже проходить?
Если имелось ввиду пройти все дуги. To в сочетании c условием через каждую вершину проходить один раз. To это просто невозможно.
A так от вершины к вершине надо проходить по дугам.
Последний раз редактировалось Pavlovsky 30 ноя 2019, 13:59, всего редактировалось 1 раз.
Причина: test
Причина: test
Гамильтонов путь
Осмелюсь поднять тему. Вроде задача простенькая. A вот мыслей никаких.
Последний раз редактировалось Pavlovsky 30 ноя 2019, 13:59, всего редактировалось 1 раз.
Причина: test
Причина: test
Гамильтонов путь
Этот граф - куб, у которого соеденены середины ребер отрезками, параллельными
соседним ребрам (что-то вроде клетки). Если сложить все координаты точки(длина ребра 2)
то получится четное или нечетное. "Четных" точек 12, "нечетных" 14. "Четные" соединяются
только c "нечетными", a "нечетными" только c "четными". Следовательно в пути должно быть
13 "нечетных" и 13 "четных".
соседним ребрам (что-то вроде клетки). Если сложить все координаты точки(длина ребра 2)
то получится четное или нечетное. "Четных" точек 12, "нечетных" 14. "Четные" соединяются
только c "нечетными", a "нечетными" только c "четными". Следовательно в пути должно быть
13 "нечетных" и 13 "четных".
Последний раз редактировалось malk 30 ноя 2019, 13:59, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 13 гостей