Аппроксимация метрических пространств древесными метриками: различия между версиями

Известно, что древесные метрики плохо аппроксимируют метрики общего вида; иначе говоря, если дан цикл <math>C_n \;</math> с n вершинами, то любая древесная метрика, аппроксимирующая эту графовую метрику, имеет невязку <math>\Omega (n) \;</math> [17]. Однако Карп [15] заметил, что случайное остовное дерево <math>C_n \;</math> дает довольно неплохую ожидаемую аппроксимацию расстояния между двумя вершинами в <math>C_n \;</math>. Позднее Алон, Карп, Пелег и Уэст [1] доказали, что граница средней невязки при аппроксимации любой графовой метрики ее остовным деревом составляет <math>exp(O(\sqrt{log \; n \; log \; log \; n }))</math>.