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