Преобразования метрик, сохраняющие типы одномерных минимальных заполнений, страница 4

Существует такая t ∈ M , что p1 ∈ rt,иначе порождающее дерево без p1 и всех содержащих её рёбер останетсяминимальным заполнением. Поэтому ρrt = 2ρp1 r > a, что противоречитвыбору r и s.Утверждение 2.25. Если в дереве аддитивного пространства (M, ρ) естьцентр, то оно ультраметрично.Доказательство. Пусть p — центр, u, v, w ∈ M , q = uv ∩ vw ∩ wu и ρpw = Rи p0 ∈ uv ∪vw ∪wu — конец кратчайшего пути от p до uv ∪vw ∪wu. Положим12ρpp0 = d, ρp0 q = x, тогда ρp0 u = ρp0 v = ρp0 w = R − d = r.

Без ограниченияобщности p0 ∈ uq, поэтому ρvu = ρwu = 2r, ρvw = 2r − 2x < 2r, то естьвыполнено условие ультраметричности.Пример 2.26. Рассмотрим произвольное 4-точечное ультраметрическоепространство с порождающим деревом с усами {1, 2} и {3, 4}, тогда ρ13 +ρ24 = ρ14 + ρ23 , и пусть λi — длина граничного ребра минимального заполнения, выходящего из вершины i, λ5 — длина внутреннего ребра. Тогда, безучёта перестановок элементов пространства, его центр находится либо навыходящем из вершины 1 ребре, либо на внутреннем ребре.

В первом случаеλ3 = λ4 = x, λ5 = y, λ2 = x + y, λ1 = z, поэтому ρ12 = ρ13 = ρ14 = x + y + z,ρ23 = ρ24 = 2x + 2y и ρ34 = 2x, а во втором λ1 = λ2 = x, λ3 = λ4 = y, λ5 = zпоэтому ρ13 = ρ14 = ρ23 = ρ24 = x + y + z, ρ12 = 2x и ρ34 = 2y.Утверждение 2.27. Пусть задано бинарное дерево и центр на одном изего рёбер. Обозначим переменными длину каждого ребра и тех двух частей, на которые разбито ребро центром. Выпишем в систему уравнения,полученные из условия равенства расстояний до центра, выражения расстояний через длины рёбер и неравенства неотрицательности длин рёбердерева и частей, на которые разбито ребро центром.

Тогда множествовекторов расстояний, удовлетворяющих системе, является в точностимножеством всех ультраметрических пространств, тип минимальногозаполнения которых совпадает с заданным бинарным деревом и центр лежит на том же ребре, что и заданный.Замечание 2.28. Пространство, вектор расстояний которого выражаетсятаким образом через длины рёбер порождающего дерева, аддитивно, поэтому и длины рёбер однозначно выражаются из этой системы через расстояния.Доказательство. Если вектор расстояний удовлетворяет системе, то из нёследует, что метрическое пространство с таким вектором аддитивно, порождено заданным бинарным деревом и его центр на том же ребре, что изаданный.

А если вектор расстояний метрического пространства таков, чтооно аддитивно, порождено заданным бинарным деревом, и его центр лежит на том же ребре, что и заданный, то вектор расстояний удовлетворяетсистеме.Следствие 2.29. Для каждого типа минимальных заполнений множество ультраметрических пространств такого типа равно объединениюмножеств порождаемых его деревом пространств по всем положениямцентра.Список литературы[1] Иванов А.О., Тужилин А.А. Одномерная проблема Громова о минимальном заполнении. Матем. сб., 2012, т. 203, N 5, с. 65-118.13[2] Иванов А.О., Тужилин А.А. Теория экстремальных сетей. Ижевск,ИКИ, с.

1-424.[3] Липатов С.Ю., Функции, не меняющие типы минимальных заполнений, Вестник Московского университета. Серия 1: Математика. Механика, 2015, 42–4514.