4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 12:12, 25 сентября 2016
, 25 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 67: | Строка 67: | ||
'''Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является | '''Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NP-полной.''' | ||
Следующий результат показывает, что если рассматривать задачи о | Следующий результат показывает, что если рассматривать задачи о многосвязных объектах минимальной стоимости при достаточно большой размерности, эти задачи становятся APX-полными. | ||