Связь вида нормы и геометрии минимальных сетей (1104796), страница 6
Текст из файла (страница 6)
По лемме 1.1 начало тройника O является точкой Ферма тройки {A1 , A2 , A3 }.По неравенству треугольника для строго выпуклой нормы, ρ(OA1 ) + ρ(OA3 ) >ρ(A1 A2 ) + ρ(A2 A3 ). Также имеем ρ(OA2 ) > 0. Значит, ρ(OA1 ) + ρ(OA2 ) + ρ(OA3 ) >ρ(A2 A1 ) + ρ(A2 A2 ) + ρ(A2 A3 ), и O не является точкой Ферма тройки {A1 , A2 , A3 },противоречие.Альтернативное доказательство следующего факта можно прочитать в [11, теорема 6.2.8].Следствие 2.1 Пусть дана двумерная нормированная плоскость со строго выпуклой дифференцируемой нормой (R2 , ρ).
Тогда SM T (M ) ⊂ conv(M ) для любогограничного множества M .31Доказательство. Пусть это не так. Тогда найдется такая подвижная точка сети,лежащая снаружи conv(M ), что все три ребра сети лежат в одной полуплоскости относительно некоторой прямой, проходящей через эту подвижную точку, чтоневозможно по лемме 2.4. В качества такой вершины подойдет любая вершинаSмногоугольника conv(M SM T (M )), не являющаяся вершиной многоугольникаconv(M )Лемма 2.5 (лемма о тройнике) Пусть дана двумерная нормированная плоскость со строго выпуклой дифференцируемой нормой (R2 , ρ). Пусть задан лучс началом в точке O. Тогда существует и единственен тройник, включающий всебя этот луч с началом в точке O.Доказательство. Введем необходимые обозначения: n1 — единичный направляющий вектор данного луча, p1 = ∇ρ(n1 ). Заметим, что по лемме [4, лемма 7.3]P3найдется единственная пара ковекторов p2 , p3 ∈ Σ∗ , такая чтоi=1 pi = 0.
Полемме 2.3, при помощи отображения (∇ρ)−1 по градиенту с Σ∗ единственным образом восстанавливается вектор с Σ. Значит, тройник с одним известным лучомсуществует и единственен.Пусть дана двумерная нормированная плоскость (R2 , ρ) со строго выпуклой и дифференцируемой нормой. Пусть заданы граничное множество M , |M | = n, граничное отображение ∂Γ и топология бинарного дерева G. Пусть также существует невырожденное дерево Γ, принадлежащее P M T (G, ∂Γ). Для произвольной подвижной вершины соответствующим ей тройником будем называть тройник сначалом в ней, лучи которого содержат инцидентные ей ребра в дереве.Лемма 2.6 Пусть дана двумерная нормированная плоскость (R2 , ρ) со строговыпуклой и дифференцируемой нормой.
Пусть заданы граничное множество M ,|M | = n, граничное отображение ∂Γ и топология бинарного дерева G. Пусть также существует невырожденное дерево Γ, принадлежащее P M T (G, ∂Γ). Тогда:321) существует тройник TX такой, что для любой подвижной вершины тройник, соответствующий ей, может быть получен параллельным переносом из TXлибо из тройника, полученного из TX с помощью центральной симметрии относительно любой точки;2) найдутся три семейства параллельных прямых такие, что каждая прямая, содержащая ребро дерева Γ, принадлежит одному из этих семейств.Доказательство. Заметим сначала, что из центральная симметрия является изометрией нормы ρ, и поэтому образ тройника, отраженного при помощи центральной симметрии относительно любой точки, является тройником.Если n ≤ 3, то количество ребер в дереве Γ не превышает трех, и в этом случаеутверждение тривиально.Пусть n > 3.
Тогда в дереве Γ есть по крайней мере две подвижные вершины.Для любого ребра XY между подвижными вершинами Γ рассмотрим два тройника TX и TY , соответствующие вершинам X и Y . Заметим, что по лемме 2.5TX (TY , соответственно) — это единственный тройник с началом в X(Y , соответственно), включающий в себя луч [XY i([Y Xi). Также заметим, что образ TX0 тройника TX при центральной симметрии относительно середины ребра XY являетсяединственным тройником с началом в Y , включающим в себя луч [Y Xi. Значит,TX0 совпадает с TY . Из центральной симметричности друг другу тройников TX иTY следует попарная параллельность прямых, содержащих соответствующие лучив TX и TY .
Рассмотрим любое ребро e дерева Γ. Оно инцидентно по крайней мереодной подвижной вершине, обозначим ее через Z (а соответствующий ей тройник— через TZ ). Построим путь между X и Z по ребрам Γ (все вершины этого путибудут внутренними вершинами Γ). Для каждой пары соседних вершин проведемрассуждения, аналогичные рассуждениям выше о центральной симметричностидруг другу тройников TX и TY . Получим, что прямая, содержащая e, параллельнаодной из трех прямых, содержащих лучи тройника TX , а также то, что тройникTZ получается параллельным переносом из TX или из TY .33Рис.
2: луч [OBi лежит между лучами [OAi и [OCi.Далее приведем лемму о монотонности, естественный факт из теории нормированных пространств. В работе [8] лемма сформулирована для выпуклых норм, мыже ограничимся строго выпуклым случаем. Будем говорить, что луч [OBi лежитмежду лучами [OAi и [OCi, если [OBi принадлежит неразвернутому углу ∠AOC(см.
Рис. 2).Лемма 2.7 (лемма о монотонности) Пусть дана двумерная нормированная плоскость со строго выпуклой нормой (R2 , k·k). Пусть даны точки A, B, C и не совпадающая ни с одной и них O, A 6= C, такие, что луч [OBi лежит между лучами[OAi и [OCi и что kOBk = kOCk. Тогда kABk ≤ kACk, и равенство достигаетсятолько в случае B = C.Доказательство. Следует из [8, Monotonicity Lemma].Следствие 2.2 Пусть A и à — диаметрально противоположные точки Σ, единичной окружности строго выпуклой нормы, и они разбивают Σ на две дуги.Тогда для каждой из двух дуг верно, что при движении точки X по дуге от A кà норма отрезка kAXk будет монотонно расти.Доказательство следующего факта можно найти в [13, Proposition 5.4.7].
Напомним, что любое конечномерное нормированное пространство является рефлексивным.34Лемма 2.8 Рефлексивное нормированное пространство является строго выпуклым (гладким) тогда и только тогда, когда его дуальное пространство являетсягладким (строго выпуклым).Лемма 2.9 (лемма о тройниках с общим началом) Пусть дана двумерная нормированная плоскость со строго выпуклой дифференцируемой нормой (R2 , ρ).
Пустьтакже даны два тройника с началом в точке O. Первый тройник разбивает плоскость на три открытые части. Тогда либо два данных тройника совпадают, либо в каждой из трех открытых частей плоскости лежит по одному лучу извторого тройника.У данной леммы есть несложное прямое доказательство с помощью введения координат. Приведем здесь более красивое, на наш взгляд, доказательство с использованием следствия 2.2.Доказательство. Обозначим тройники как T1 и T2 . Заметим, что если у двухтройников есть хотя бы один совпадающий луч, то тройники совпадают по лемме 2.5.Пусть теперь у тройников нет совпадающих лучей и нашелся элемент разбиения плоскости при помощи T1 , в котором лежит не менее двух лучей T2 . Три лучаT2 в одном элементе оказаться не могут по лемме 2.4.
Получается, что с точностьюдо переобозначения внутри тройников лучи тройников упорядочены следующимобразом: {T11 , T21 , T22 , T12 , T13 , T23 }, где Tij — j-тый луч i-того тройника. По лемме 2.3,отображение градиента нормы ∇ρ : Σ → Σ∗ является гомеоморфизмом, сохраняющим ориентацию, отображающим полуокружности в полуокружности. Значит,соответствующие ковекторы с единичных котройников упорядочены в той же последовательности, что и соответствующие им лучи тройников. Осталось показатьPневозможность равенства нулю суммы 3j=1 T2∗j , где Ti∗j — это j-тый ковектор i-гокотройника.Заметим, что четыре луча T11 , T21 , T22 , T12 лежат в одной полуплоскости, значит,то же верно и для соответствующих им ковекторов из котройников.
По лемме 2.8,35конорма является строго выпуклой. Теперь дважды воспользуемся следствием 2.2для конормы; в первом неравенстве в качестве A выступает точка −T1∗1 , и точкаT2∗2 находится от нее дальше, чем T1∗2 , а во втором в качестве A выступает точка−T2∗2 , и точка T2∗1 находится от нее дальше, чем T1∗1 :1 = ρ∗ (T1∗1 + T1∗2 ) < ρ∗ (T1∗1 + T2∗2 ) < ρ∗ (T2∗1 + T2∗2 )Но конорма T2∗3 равна 1, значит,P3j=1T2∗j 6= 0, чтд.Следующая лемма доказана в [5, утверждение 1].Лемма 2.10 Для каждой вершины v степени 3 бинарного дерева с n вершинамистепени 1, кратчайший по количеству ребер путь, соединяющий v с множествомвершин степени 1, состоит не более, чем из log22n3ребер.Назовем разреженностью множества M в метрическом пространстве величинуD(M ) = sup{ρ(M1 , M2 )|M = M1 t M2 , Mi 6= ∅}Лемма 2.11 Пусть дана двумерная нормированная плоскость (R2 , ρ).
Пусть также дано некоторое граничное множество M . Тогда в SM T (M ) нет ребер длиннееD(M ).Доказательство. Лемма является ослабленной версией утверждения [5, утверждение 3].Лемма 2.12 Пусть даны две нормы k · k1 и k · k2 на плоскости такие, что множества деревьев SM T (M ) в них совпадают для любого граничного множестваM . Рассмотрим Si — множество всех тройников в k · ki с центром в нуле. ТогдаS1 = S2 .Доказательство. Для любых трех точек сети Штейнера в нормах k · k1 и k · k2совпадают.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
