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

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

размер: количество ребер в графе.

степень: максимальное количество ребер, инцидентных вершине.

вес: сумма весов ребер.

диаметр остова: наименьшее целое число k, такое, что для любой пары вершин u и v из S существует путь в графе между u и v, длиной не более t • \uv\ и содержащий не более k ребер.

отказоустойчивость: сохранение работоспособности графа при отказе ребра, вершины или области.

Таким образом, качественные t-остовы должны иметь высокое значение отказоустойчивости и малые размер, степень, вес и диаметр остова.