4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 13:11, 6 сентября 2016
, 6 сентября 2016→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
Стоимость 8(x, y) дуги, соединяющей пару точек x, y 2 Rd, равна евклидовому расстоянию между точками x и y. Иначе говоря, S(x, y) = P di=1(xi ~~ i)2, где x = (x1, ... , xd) и y = (y1, ... : : , yd). В более общем виде стоимость можно определить с использованием других норм – таких как lp-нормы для любого p > l, т.е. 8(x,y) = Pid=1(xi ~ yi)p. Стоимость сети представляет собой сумму стоимостей всех ребер сети: cost(G) = ^\x -,eE S(x, y). | Стоимость 8(x, y) дуги, соединяющей пару точек x, y 2 Rd, равна евклидовому расстоянию между точками x и y. Иначе говоря, S(x, y) = P di=1(xi ~~ i)2, где x = (x1, ... , xd) и y = (y1, ... : : , yd). В более общем виде стоимость можно определить с использованием других норм – таких как lp-нормы для любого p > l, т.е. 8(x,y) = Pid=1(xi ~ yi)p. Стоимость сети представляет собой сумму стоимостей всех ребер сети: cost(G) = ^\x -,eE S(x, y). | ||
Сеть G = (V, E) служит остовом множества точек S, если V = S. Сеть G является k-вершинно-связной, если для любого множества l/cy, состоящего из менее чем k вершин, сеть (V n U; E \ ((V n U) x (V n U)) является связной. Подобным же образом G является k-реберно-связной, если E С E с количеством ребер менее k сеть (V, E n E) является связной. | |||
Евклидова задача нахождения k-связной остовной сети минимальной стоимости | |||
Для заданного множества S из n точек в евклидовом пространстве Rd найти k-вершинно-связную сеть минимальной стоимости, охватывающую все точки S. | |||