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

Граф G = (V, E), ребрам которого присвоены неотрицательные веса, определяет метрическое пространство <math>(V, d_G) \;</math>, где для каждой пары вершин <math>u, v \in V \;</math> за <math>d_G(u, v) \;</math> обозначается расстояние по кратчайшему пути между u и v в графе G. Метрика (V, d) является [[древесная метрика|древесной]], если существует некоторое дерево <math>T = (V', E') \;</math>, такое, что <math>V \subseteq V' \;</math> и для всех <math>u, v \in V \;</math> верно <math>d_T(u, v) = d(u, v) \;</math>. Метрика (V, d) также называется метрикой, порожденной T.