Связь вида нормы и геометрии минимальных сетей (1104796), страница 7
Текст из файла (страница 7)
Рассмотрим тройник из S1 , выберем по одной точке на луче. ТочкаФерма полученной тройки точек — это ноль. В k · k2 у выбранной тройки точек точка Ферма — тоже ноль. По лемме 1.1, рассматриваемый тройник являетсятакже тройником во второй норме. Имеем S1 ⊆ S2 , аналогично получим S2 ⊆ S1 .36В следующей лемме мы воспользуемся результатами из работы [6].
В ней исследуются сети на евклидовой плоскости, но большинство результатов обобщаются наслучай нормированной плоскости со строго выпуклой дифференцируемой нормойпутем естественных переформулировок либо заменой соответствующих терминов.Введем необходимые определения, попутно обобщая определения там, где это понадобится.Пусть L — произвольная ломаная. По определению, все ее вершины Ai канонически перенумерованы. Ясно, что каждая ломаная может быть задана занумерованным набором своих вершин. Если перенумеровать точки Ai в противоположномпорядке, то мы снова получим ломаную, совпадающую с исходной как подмножество плоскости. Выбор одной из двух канонических нумераций вершин называетсяориентацией ломаной L.
Если ориентация ломаной L фиксирована, то можно рассматривать каждое звено Ai Ai+1 ломаной L как вектор с началом в Ai и концом вAi+1 .Пусть дана двумерная нормированная плоскость (R2 , ρ) со строго выпуклой идифференцируемой нормой, а также с фиксированной ориентацией. Пусть заданыграничное множество M , |M | = n, и топология бинарного дерева G. Пусть такжесуществует невырожденное линейное дерево Γ с границей M и тройник TX такие,что для любой подвижной вершины тройник, соответствующий ей, может бытьполучен параллельным переносом из TX или из тройника, полученного из TX спомощью центральной симметрии относительно любой точки.Здесь и далее (до теоремы 2.3 включительно) будем считать, что рассматриваемые ломаные — это пути между вершинами (в качестве вершин можно выбиратькак граничные, так и подвижные) в дереве Γ, а векторы — это направляющие векторы ребер дерева Γ. Таким образом, мы рассматриваем векторы 6 направлений(три из единичного ежа, соответствующего TX , и три противоположных им вектора).
Назовем объединение этих шести единичных векторов характеристическимежом. Твистингом tw(a, b) упорядоченной пары векторов a и b назовем следующую функцию от векторов: посмотрим, как векторы a и b расположены относи-37тельно друг друга в характеристическом еже; tw(a, b) = 0, если a = b, tw(a, b) = ±1,если a и b — соседние векторы, tw(a, b) = ±2, если a и b расположены через один, азнак твистинга совпадает с ориентацией репера (a, b). Твистинг не определен дляпротивоположных векторов.Пусть L — ориентированная ломаная, и ai = [Ai , Ai+1 ], i = 0, .
. . , n, — ее последовательные ребра (если ломаная замкнута, то сложение понимается по модулюn + 1).Твистингом tw Ai вершины Ai назовем твистинг tw(ai−1 , ai ) между последовательными векторами-звеньями, инцидентными Ai .Сумма твистингов всех внутренних вершин ломаной L называется кручениемвдоль L и обозначается через tn L:tn L =nXtw Ai .i=1Если ломаная L состоит из одного звена, то положим tn L = 0.Пусть a и b — произвольные ребра из Γ. Рассмотрим единственный ориентированный путь γ(a, b) в Γ, начинающийся на a и заканчивающийся на b.
Путь γ(a, b),очевидно, представляет собой ориентированную ломаную на плоскости. Числомвращения между ребрами a и b линейного дерева Γ назовем кручение ломанойγ(a, b): tw(a, b) = tn γ(a, b).Числом вращения линейного дерева Γ называется максимум чисел вращения,взятый по всем упорядоченным парам ребер из Γ:tw Γ = max tw(a, b).(a,b)Для частного случая выпуклого множества M и определенного выше дерева Γосновная теорема работы [6] звучит так:Теорема 2.3 tw Γ ≤ 6.Теперь все готово к доказательству следующей леммы.38Рис. 3: невозможный в условиях леммы 2.13 путь между X и Y .
Части пути XPи U Y изображены схематически.Лемма 2.13 Пусть дана двумерная нормированная плоскость (R2 , ρ) со строговыпуклой и дифференцируемой нормой. Пусть M, |M | = n, — множество вершин выпуклого n-угольника (некоторые его углы могут быть развернутыми).Рассмотрим минимальное дерево Штейнера Γ с границей M и возьмем любыеподвижные вершины X, Y ∈ Γ, соединенные некоторой невырожденной компонентой дерева Γ. Тогда для пути в дереве, соединяющего X и Y , верно, что в немнет четырех поворотов подряд в одну сторону.Доказательство. От противного. Пусть есть. Тогда на пути, соединяющем X иY , имеем ломаную P QRST U с поворотами в одну сторону в точках Q, R, S, T (см.Рис.
3). По лемме 2.6, P Q k ST, QR k T U . Внутри conv(P, Q, R, S, T, U ) не можетбыть граничных вершин: по следствию 2.1 имеем conv(P, Q, R, S, T, U ) ⊆ conv(M ),и принадлежность граничной вершины внутренности conv(P, Q, R, S, T, U ) противоречила бы тому, что все граничные вершины лежат на границе conv(M ). Одно изребер, инцидентных P , параллельно RS (назовем его OP ).
То же верно для одногоиз ребер, инцидентных U (назовем его U V ). Кручение вдоль ломаной OP QRST U Vравно шести, и если хотя бы одна вершина среди {O, V } не является граничной, торассмотрим такое инцидентное с ней ребро, чтобы продолженная им ломаная имела кручение равное семи, и тогда мы имеем противоречие с теоремой 2.3. Значит,O и V — граничные вершины.
Рассмотрим два случая:1) вершины O, P, U, V не лежат на одной прямой. Тогда одно из ребер среди OP39Рис. 4: отрезок OV принадлежит внутренности conv(M ), а подвижные вершины Pи U лежат вне conv(M ). Граница conv(M ) изображена схематически (пунктиром).и U V лежит в conv(P, Q, R, S, T, U ) (поскольку они параллельны и лежат по разныестороны от прямой P U ); имеем граничную вершину внутри conv(P, Q, R, S, T, U ),противоречие;2) вершины O, P, U, V лежат на одной прямой. Предположим, что эта прямаяпересекается с внутренностью conv(M ).
Тогда отрезок OV принадлежит внутренности conv(M ), и подвижные вершины P и U лежат вне conv(M ) (см. Рис. 4),что снова приводит к противоречию со следствием 2.1. Значит, прямая P U не пересекается c внутренностью conv(M ), и весь многоугольник (а также дерево Γ)лежит по одну сторону от прямой P U (с той стороны, где находится Q). Но у Pесть соседняя вершина, которая лежит по другую сторону от прямой P U , чем Q,противоречие со следствием 2.1.2.2Достаточное условие гомотетичности нормГлавный результат настоящего раздела — это теорема 2.5, являющаяся достаточным условием гомотетичности двух норм в терминах деревьев Штейнера, построенных в соответствующих нормированных пространствах.
Введем необходимыеопределения для этого раздела.Пусть заданы два ненулевых вектора v1 и v2 . Отложим v1 от некоторой точкиA, получим точку O. Также отложим v2 от O, получим B. Объединение лучейOA и OB разбивает плоскость на два сектора (в случае такого рода разбиений40Рис. 5: слева — вырожденная пара, справа — тройник из определения вырожденнойпары (изображен пунктиром).будем считать, что оба луча принадлежат обоим секторам). Если среди них естьнеразвернутый угол, обозначим его через S (в случае развернутого угла ∠AOBобозначим через S произвольный из двух секторов). Любой тройник разбиваетплоскость на три сектора. Если существует тройник с началом в O такой, чтоодин из его секторов содержится в S, пару (v1 , v2 ) будем называть вырожденнойпарой (см.
Рис. 5).Пару лучей будем называть вырожденной парой, если некоторая пара ненулевых сонаправленных соответствующим лучам векторов является вырожденнойпарой. Очевидно, что свойство вырожденности пары лучей не зависит от выборавекторов из определения.Пару отрезков, имеющих общий конец, будем называть вырожденной парой,если соответствующая им пара векторов, исходящих из общего конца отрезков,является вырожденной парой.Ежом будем называть множество лучей с общим началом, единичным ежом —множество единичных векторов или отрезков с общим началом.
Началом (единичного) ежа будем называть общее начало лучей (векторов или отрезков), входящихв еж.Вырожденным (единичным) ежом будем называть (единичный) еж, каждаяпара соседних в круговом порядке лучей (векторов или отрезков) которого является вырожденной парой.41Еж и единичный еж будем называть соответствующими друг другу, если векторы или отрезки единичного ежа лежат соответственно на лучах ежа.Несложно показать, что добавление дополнительных лучей (векторов или отрезков) оставляет вырожденный (единичный) еж вырожденным. Действительно,вырожденность пары лучей (векторов, отрезков) — это, по определению, возможность вписать некоторый сектор некоторого тройника в угол, смежный неразвернутому углу между элементами пары.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
