Связь вида нормы и геометрии минимальных сетей (1104796), страница 9
Текст из файла (страница 9)
[3]) в более общем случае.Классическое свойство клина формулируется в евклидовой норме таким образом:пусть дан фрагмент плоскости W , содержащий в себе угол2π3и не содержащийграничных вершин. Тогда для любой выбранной топологии ни одна из подвижныхвершин минимального параметрического дерева Штейнера не будет лежать в W .Две нормы k · k1 и k · k2 будем называть гомотетичными, если существуетчисло α > 0 такое, что для любого вектора v выполненоk v k1 = α k v k2.Теорема 2.5 Пусть k · k1 и k · k2 — две строго выпуклые дифференцируемыенормы на двумерной плоскости такие, что множества деревьев SM T (M ) в нихсовпадают для любого граничного множества M . Тогда указанные нормы гомотетичны.47Доказательство.
Зафиксируем единичный вектор v. Построим единичный тройник в норме k · k1 , содержащий v, и достроим этот тройник до единичного ежа сшестью векторами, центрально симметрично отразив его относительно его начала.Полученный единичный еж обозначим за H1 ; он является вырожденным.Добавим к H1 произвольный единичный вектор w, полученный единичный ежобозначим через H1w , соответствующий ему еж обозначим через H w . По теореме 2.4, единичные ежи, соответствующие H w в нормах k · k1 и k · k2 , гомотетичны,пусть коэффициент гомотетии равен k. Заметим, что коэффициент гомотетии kоднозначно определяется тем, во сколько раз растягивается единичный отрезок внаправлении вектора v, поэтому k не зависит от выбора w.
Значит, для всех единичных векторов w коэффициент гомотетии одинаков, что и дает гомотетичностьнорм k · k1 и k · k2 .3Минимальные параметрические сетиВ данной главе изучается поведение минимальных параметрических сетей при малых деформациях их граничных множеств.Лемма 3.1 Пусть дано нормированное пространство (Rn , k · k). Пусть такжев нем выбраны четыре точки A, B, C, D, обозначимТогда k EF k≤kADk+kBCk.2A+B2через E,C+D2через F .В случае строго выпуклой нормы равенство возможнотолько в случае сонаправленных векторов AD и BC.Доказательство. Используем равенства сумм векторовEF = EB + BC + CF = EA + AD + DF, EB = −EA, CF = −DF,2EF = BC + ADПо неравенству треугольника, имеемk EF k≤k BC k + k AD k248В случае строго выпуклой нормы, равенство в последнем неравенстве достигаетсятолько в случае сонаправленных AD и BC, чтд.Пусть дано нормированное пространство X = (Rm , k · k) и фиксировано граничноемножество точек M .
Будем рассматривать вложенные бинарные деревья с границей M, |M | = n, фиксированной бинарной топологии G. Длина ` каждого такогодерева есть функция координат всех граничных и подвижных вершин (для фиксированной границы скажем, что зависимость есть только от координат подвижныхвершин). У бинарного дерева с n граничными вершинами есть ровно n − 2 подвижные вершины. Будем задавать соединяющее дерево с известной границей векторомv = (v1 , v2 , ..., vn−2 ), где (vi ) — это вектор из m координат i-той подвижной вершины.
На пространстве таких векторов введем следующую норму:kvk∞ = max kvi k, i ∈ [1, n − 2].iЛемма 3.2 Пусть два дерева топологии G, соединяющие M , заданы соответственно векторами v 1 и v 2 наборов координат подвижных вершин. Тогда `( v`(v 1 )+`(v 2 )21 +v 22)≤. В случае строго выпуклой нормы k · k, равенство достигается только втом случае, когда любая пара векторов соответствующих ребер в двух деревьяхявляется парой сонаправленных векторов.Доказательство. Обозначим через T i дерево, построенное по вектору v i , а черезT 0 обозначим дерево, построенное по векторуv 1 +v 2.2Заметим, что норма каждогоребра из T 0 не превосходит полусуммы норм соответствующих ребер из T 1 и T 2 полемме 3.1.
Из этого непосредственно вытекает верность неравенства из формулировки леммы.В случае строго выпуклой нормы k · k, равенство в неравенстве из формулировки леммы будет достигаться только в случае выполнения соответствующихравенств для всех пар ребер, каждое из которых, по лемме 3.1, выполняется, когдапара векторов соответствующих ребер в двух деревьях является парой сонаправленных векторов.49Усами будем называть пару ребер, идущих из подвижной вершины в две соседниеграничные вершины. Следующая лемма была ранее доказана в [4, теорема 6.1].Лемма 3.3 Пусть норма k · k пространства X строго выпукла. Пусть заданограничное множество M , |M | = n, и топология бинарного дерева G.
Пусть также существует невырожденное дерево T 1 , принадлежащее P M T (G, ∂Γ). Тогда|P M T (G, ∂Γ)| = 1.Доказательство. Будем доказывать индукцией по n. База: n = 2. Существуетвсего одно подходящее бинарное дерево и единственное его линейное вложениев X (просто одно ребро — отрезок между двумя данными вершинами), значит,|P M T (G, ∂Γ)| = 1, и база доказана. Переход: пусть утверждение доказано дляM : |M | < n. Докажем его от противного для M : |M | = n. Пусть есть второедерево (T 2 ) из P M T (G, ∂Γ). По лемме 3.2, любая пара векторов соответствующих ребер в T 1 и T 2 является парой сонаправленных векторов, поскольку иначе`( v1 +v 22)<`(v 1 )+`(v 2 )2= `(v 1 ) (где v i — вектор координат подвижных вершин дереваT i ), противоречие с тем, что T 1 ∈ P M T (G, ∂Γ).Найдем у T 1 пару ребер-усов.
Рассмотрим соответствующие усы у T 2 . Ребраэтих усов из T 2 можно построить как отрезки, полученные при пересечении прямых, содержащих соответствующие ребра в T 1 , то есть — единственным образом.Совершим редукцию деревьев T 1 и T 2 , заменив граничные вершины рассмотренf1 и Tf2 будутных усов на соседнюю им подвижную вершину.
Полученные деревья Tразличными невырожденными бинарными деревьями с границей, состоящей из(n − 1) точки, противоречие с предположением индукции. Таким образом, переходдоказан.Введем расстояние между границами одного размера, учитывающее нумерациюграничных вершин. Полученное пространство будет нормированным с нормойkM k∞ = max kMi k.1≤i≤|M |50Лемма 3.4 Пусть норма k · k пространства X строго выпукла. Пусть заданы граничное множество M , |M | = n, граничное отображение ∂Γ и топологиябинарного дерева G. Пусть также существует невырожденное дерево Γ, принадлежащее P M T (G, ∂Γ), и |P M T (G, ∂Γ)| = 1.
Тогда существует окрестностьB(M ) такая, что для M 0 ∈ B(M ) выполнено:1) |P M T (G, ∂Γ0 )| = 1, где ∂Γ0 (∂G) = M 0 ,2) при непрерывном изменении границы M 0 в B(M ) координаты подвижныхвершин единственного дерева из P M T (G, ∂Γ0 ) изменяются непрерывно.Доказательство. Рассмотрим функцию `(v) длины дерева, где v — вектор координат подвижных вершин дерева с границей M , аналогично `0 (v) — функциядлины дерева с v — вектором координат подвижных вершин дерева с границейM 0 .
Обозначим через w вектор координат подвижных вершин дерева Γ. Пусть`(w) = m. Функция `(v) имеет глобальный и единственный минимум в точке w.Зафиксируем некоторое ε > 0. Рассмотрим замкнутую окрестность B 2ε (w). Пустьминимальное значение на границе окрестности B 2ε (w) равно m + (n + 1)δ. Обозначим через S множество всех точек v таких, что `(v) = m + (n + 1)δ. Тогда все v ∈ Sлежат в B 2ε (w). Действительно, если это не так, возьмем точку s из S, не принадлежащую B 2ε (w), и пересечем отрезок от w до нее с границей B 2ε (w), получив точкуs0 . Функция ` выпукла, а также имеет единственный глобальный минимум в точкеw; это означает, что ` мажорируется линейной функцией, график которой проходит через точки w, `(w) и s, `(s) на отрезке ws.
Получаем `(s0 ) < m + (n + 1)δ,противоречие.Для каждой точки v из S рассмотрим точку h(v) = w + 2(v − w). Функция `выпукла, поэтому значение ` h(v) больше, чем m + 2(n + 1)δ. Заметим, что налюбом отрезка с началом в w и концом на границе B 2ε (w) найдется точка из S, изначит, на любом отрезке с началом в w и концом на границе Bε (w) найдется точкаиз h(S).
Функция ` выпукла, а также имеет единственный глобальный минимум вточке w. Для каждого луча с началом в w верно, что значение функции ` на нем51монотонно возрастает при удалении от w. Из этого следует, что при v снаружиBε (w) значение функции `(v) больше, чем m + 2(n + 1)δ.Рассмотрим теперь сдвинутую границу M 0 : kM − M 0 k∞ < δ. Тогда:`0 (v) ≥ m + 2(n + 1)δ − nδ > m + (n + 1)δ ∀v 6∈ Bε (w).Первое неравенство верно, поскольку сети на вершинах (M, v) и (M 0 , v) различаются только граничными ребрами, и соответствующие граничные ребра различаютсяпо длине не более, чем на δ. По той же причине, имеем `0 (w) ≤ m+nδ < m+(n+1)δ.Это означает, что минимум функции `0 достигается в Bε (w). Заметим, что можноподобрать такое малое ε (а с ним и δ), чтобы все деревья c вектором граничных вершин из Bδ (M ) и вектором подвижных вершин из Bε (w) были невырожденными.Тогда то дерево, которое будет давать минимум функции `0 (v), будет невырожденным, а значит, по лемме 3.3, будет единственным деревом из P M T (G, ∂Γ0 ).
Вкачестве B(M ) можно рассмотреть Bδ (M ).Следующая теорема будет использовать понятие поворота сети при малых деформациях границы. По лемме 3.4, для любой пары M, P M T (G, ∂Γ), где единственнаясеть из P M T (G, ∂Γ) реализуется в виде невырожденного бинарного дерева, и любого ε > 0 можно выбрать δ так, чтобы при сдвиге M не далее, чем на δ (то естьдля M 0 : kM 0 − M k∞ < δ), единственная сеть из P M T (G, ∂Γ0 ), где ∂Γ0 (∂G) = M 0 ,сдвинулась не далее, чем на ε (имеется в виду расстояние между векторами координат подвижных вершин соответствующих деревьев).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
