Минимальные k-связные геометрические сети: различия между версиями

Стоимость 8(x, y) дуги, соединяющей пару точек <math>x, y \in \mathbb{R}^d \;</math>, равна евклидовому расстоянию между точками 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).