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

Пусть 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].

Задача 1. Определить наименьшее вещественное число t > 1, для которого выполняется следующее утверждение: Для каждого множества S из n точек на плоскости существует плоский граф с множеством вершин S, являющийся t-остовом для S. Разработать эффективный алгоритм построения такого плоского t-остова.

Задача 2. Определить наименьшее целое положительное число D, для которого выполняется следующее утверждение: Существует константное значение t, такое, что для каждого множества S из n точек на плоскости существует плоский граф с множеством вершин S и максимальной степенью, не превышающей D, который является t-остовом для S. Разработать эффективный алгоритм построения такого плоского t-остова.