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

Пусть G = (V, E) – [[геометрическая сеть]], множество вершин V которой соответствует множеству из n точек в пространстве <math>\mathbb{R}^d \;</math> для определенного целого числа <math>d \ge 2 \;</math>, а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V.

Стоимость <math>\delta(x, y) \;</math> дуги, соединяющей пару точек <math>x, y \in \mathbb{R}^d \;</math>, равна евклидовому расстоянию между точками x и y. Иначе говоря, <math>\delta(x, y) = \sqrt{ \sum^d_{i=1} (x_i - y_i)^2}</math>, где <math>x = (x_1, ..., x_d) \;</math> и <math>y = (y_1, ..., y_d) \;</math>. В более общем виде стоимость можно определить с использованием других норм – таких как <math>\ell_p</math>-нормы для любого p > 1, т.е. <math>\delta(x, y) = \Big( \sum_{i=1}^p (x_i - y_i)^p \Big)^{1/p} \;</math>. Стоимость сети представляет равна сумме стоимостей всех ребер сети: <math>cost(G) = \sum_{x, y \in e} \delta(x, y) \;</math>.