4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 22:04, 15 сентября 2016
, 15 сентября 2016→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
'''(Евклидова) задача нахождения k-вершинно-связной остовной сети минимальной стоимости''' | '''(Евклидова) задача нахождения k-вершинно-связной остовной сети минимальной стоимости''' | ||
Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-вершинно-связную сеть минимальной стоимости, охватывающую | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-вершинно-связную евклидову сеть минимальной стоимости, охватывающую точки S. | ||
'''(Евклидова) задача нахождения k-реберно-связной остовной сети минимальной стоимости''' | '''(Евклидова) задача нахождения k-реберно-связной остовной сети минимальной стоимости''' | ||
Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S. Рассматривается также вариант, допускающий наличие параллельных ребер: | ||
'''(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости''' | '''(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости''' | ||
Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову | Для заданного множества S из n точек в евклидовом пространстве <math>\mathbb{R}^d \;</math> найти k-реберно-связную евклидову мультисеть минимальной стоимости, охватывающую точки S (под мультисетью понимается сеть, допускающая наличие параллельных ребер. | ||