|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ruslan Shevelyov 2:5020/9481.21 28 May 2002 23:30:48
To : Sveta Ivanova
Subject : Провести ломаную через точки
--------------------------------------------------------------------------------
SI> То, что задача гамильтонова пути в произвольном графе NP-трудна,это,
SI> конечно известно. А может ли нам помочь тот факт, что точки даны на
SI> плоскости?
Hавряд ли; в тех алгоритмах поиска гамильтонова пути,
описания которых я видел, под графом понимается набор
из двух множеств: множества вершин v1...vn и множества
дуг -- пар вида (vi,vj). Как видите, ни плоскости, ни
длины рёбер в этом определении не наблюдаются.
SI> Известно ли что-нибудь о трудности находжения гамильтонова
SI> пути в геометрическом графе?
Геометрический граф -- это граф с заданными
длинами рёбер?
Цитируется по книге "Курс дискретной математики"
Авторы: В. H. Hефёдов, В. А. Осипова
Стр. 259-260
"Задачи теории графов можно классифицировать
следующим образом:
--- skip ---
3) задачи, для которых известны только алгоритмы
экспоненциальной сложности, но про которые нельзя
сказать, что для них нет алгоритмов полиномиальной
сложности;
--- skip ---
Третий класс содержит следующие задачи:
о существовании в графе гамильтонова цикла..."
WBR...
---
* Origin: Cosmo Canyon Station (2:5020/9481.21)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
