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

Пусть S – множество точек на плоскости, а G – неориентированный граф с множеством вершин S, каждое ребро (u, v) которого имеет вес, равный евклидовому расстоянию |uv| между точками u и v. Для любых двух точек p и q в S обозначим кратчайший путь между ними в графе G за <math>\delta_G (p, q) \;</math>. Если <math>t \ge 1 \;</math> – вещественное число, то граф G является ''t-остовом'' S в случае, если <math>\delta_G(p, q) \le t |pq| \;</math> для любых двух точек p и q в S. Таким образом, если значение t близко к 1, то граф G содержит достаточно хорошие приближения <math>\tbinom{n}{2}</math> евклидовых расстояний, определяемых парами точек в S. Если к тому же G включает O(n) ребер, то этот граф можно считать разреженным приближением полного графа на S. Наименьшее значение f, при котором G будет являться t-остовом, называется ''коэффициентом растяжения'' (или ''протяженностью'') G. Исчерпывающий обзор геометрических остовов можно найти в работе Нарасимхана и Смида [16].