Геометрические остовы: различия между версиями

Рассмотрим множество S из n точек в d-мерном Евклидовом пространстве. Сеть на множестве S может быть смоделирована при помощи неориентированного графа G с множеством вершин S размера n и множеством ребер E, в котором каждое ребро (U, V) имеет вес. Геометрическая (евклидова) сеть представляет собой сеть, в которой весом ребра (u, v) является евклидово расстояние |uv| между его конечными точками. Пусть дано вещественное число t > 1. Мы говорим, что граф G является ''t-остовом'' множества S, если для каждой пары точек <math>u, v \in S \;</math> существует путь в G с весом, не более чем в t раз превышающим евклидово расстояние между u и v. Минимальное значение t, при котором граф G является t-остовом S, называется коэффициентом растяжения, или протяженностью, G. Более детальное изложение процедуры построения t-остовов можно найти в книге Нарасимхана и Смида [18]. В данной статье рассматривается построение t-остовов для заданного множества S из n точек в пространстве <math>R^d \;</math> и положительного вещественного числа t > 1, где d является константой.