Геометрические свойства локально минимальных сетей (1097521), страница 54

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 54)

Повторяя описанную процедуру до тех пор, пока не будут исчерпаны все неустойчивые внутренние вершины дерева Г, мы построим искомое дерево Г, Предложение доказано. Замечание. Отметим, что при достаточно малом г на каждом шаге описанной в доказательстве предложения 4.17 процедуры, вершины деформируемого дерева Г смещаются внутри выпукюй оболочки вершин, остающихся неподвижными на этом шаге.

Определение. Линейное дерево Г, не содержащее ни фиктивных, ни неустойчивых внутренних вершин, назовем правильным. Из предложения 4.17 немедленно вытекает, что при доказательстве теоремы 6, можно ограничиться случаем правильных линейных деревьев. Всюду ниже, не ограничивая общности, будем рассматривать лшаь правильные линейные деревья. Замечание. Отметим, что все внутренние вершины правильного ли- нейного дерева, по определению, являются устойчивыми. Имеет место следующее просгое, но полезное предложение.

Предложение 4.18 Пусть Г --. произвольное правильное линейное дерево, и а и 6 такие ребра из Г, что Ск(а,б) = СкГ. Тогда ребра а и 6 необходимо являются граничными. Более точно, если 7(а,6) путь в Г, начинаюяяийся на ребре а и заканчивающийся на ребре Ь, то концевые вершины этого пути являются граничными. Доказательство. Предположим противное, и пусть, скажем, ребро 6 не является граничным. Так как дерево Г правильное, то обе вершины, инцидентные ребру 6, являются устойчивыми внутренними вершинами для Г. Рассмотрим лолсаную ", = 7(а, 6) единственный путь в Г от а к Ь, ориентируем у от а к Ь, и пусть В концевая вершина Глава 4. Плоские локально минимальные деревья.

246 ломаной у. По предположению, вершина В из Г является устоичивой внутренней вершиной, 1эассмотрим прямую 1.', проходящую через ребро Ь (и, в частности, чсроз вершину В). Тогда, так как В устойчивая внутреннля вершина, в каждой из порожденных прямой й открытых полуплоскостей содержатся ребра из Г, инцидентные В.

Выберем в каждой из этих полуплоскостей по одному такому ребру и обозначим выбранные ребра через со 1 = 1, 2. Рассмотрим ломаные "(, = т 0 с„ ориентированные от а к с;. Очевидно, что твистинги ломаных у; в вершине В отличны от нуля и противоположны по знаку, поэтому, или Хк(а, еи) > Ьк(а, Ь), или Счч(а, ся) > 1к(а, Ь), что противоречит выбору ребер а и Ь. Доказательство закончено, 4.4.4 Квази-геодезические В данном разделе вводится понятие квази-геодезичсскои в правильном линейном дереве.

Этот объект будет очень полезным при доказательстве теоремы 6. Пусть Г .- правильное линейное дерево, Р --- произвочьная внутренняя вершина из Г,и 1 произвольная прямая на плоскости. Мгя начнем с доказательства следующего несложного факта. Предложение 4.19 В сделанных выше обозначен ях, существует путь у в Г, соединяющий две граничньх вершины из Г, такой что Р Е у, и оргпогональная проекция пути 1 на прямую 1 взаимно однозначна с образом. Доказательство.

Разобьем доказательство на две леммы. Лемма 4.17 По крайней мере одно из ребер сети Г, иниидентных вершине Р (обозначим его через е), однозначно проектируется на прлмую 1 (т.е. ребро е не ортогонально 1). Доказательство. В самом деле, в противном случае все ребра., ипцидснтные Р, лежат на проходящей через Р прямой 1~, ортогональной к 1.

Поэтому каждая из порожденных 1~ открытых полуплоскостей не содержит ребер из Г. инцидентных Р, что противоречит предположению о том, что вершина Р -- внутренняя вершина правильного линейного дерева, т.е. устойчивая внутренняя вершина. Лемма 4,17 доказана. Лемма 4.18 Пусть е . произвольное ребро линейного дерева Г, Предположим, что е не ортогонально прямой 1, и пусть Р' вершина из Г, иниидентная е. Тогда, если Р' не является граничной вершиной 4.4.

Линейные деревья. 247 дерева Г, то среди ребер из Г, инцидентных Р' и отличных от е, найдется ребро е', такое что ортогональная проекция на прямую 1 пути, составленного из двух ребер е и е', взаимно однозначна с образом. Доказательство. Рассмотрим прямую 1~, проходяшую через Р' и перпендикулярную прямой П и обозначим через П„1 = 1, 2, две открытых полуплоскости, порожденные 1~. Так как ребро е не ортогонально 1, то оно ложит в одной из этих полуплоскостсй, скажем в Пм Поскольку вершина Р' является устойчивой внутренней вершиной дерева Г, в полуплоскости Пз лежит некоторое ребро из Г, инцидентное Р'. Обозначим это ребро через е'. Очевидно, ребро е' так же не ортогонально прямой й Обозначим через ьч Б." -+ 1 ортогональную проекцию плоскости на прямую й Точка г(Р') разбивает прямую 1 на две компоненты, в одну.из которых проектируется полуплоскость Пм а в другую -- Пг, Теперь ясно, что отрезки о(е) и о(е') пересекаются только по точке о(Р').

Лемлса 4.18 доказана. Используя лемму 4.18, можно продолжить состоящий из одного ребра путь, найденный в лемме 4.17, до максимального пути, который, по лемме 4.18, будет ограничен некоторыми граничными вершинами дерева Г, Предложение 4.19 доказано. Определение. Пу.ть 7 в правильном линейном дереве Г, соединяющий пару граничных вершин из Г, и такой что существует прямая 1 на плоскости, ортогональная проскпия пути 7 на которую взаимно однозначна с образом, называется квази-геодезической. Прямая 1 в этом случае называе~ся направляющей квази-геодезической у.

Пусть теперь п произвольный единичный вектор (т.е. некоторое направление), и пусть! некоторая прямая, параллельная и. Пусть некоторая квазигеодезическая с направляющей 1 в правильном линейном дереве Г. Обозначим через А и В граничные вершины из Г, которые соединяет ",, и пусть Р некоторая точка на 7. Точка Р разбивает путь 7 на две компоненты 7' и уо (если Р совпадает с А или В, то одна из этих компонент пуста). Снова обозначим через о ортогональную проекцию плоскости на прямую й Положим А~ = о(.4), В~ = о(В), и Р~ = о(Р). Предположим, что компонента уь не пуста, вектор Р~В~ сонаправлен с п, и В концевая вершина пути уо. Определение.

Построенная выше компонента 7"а называется квази- геодезическим лучам, вьтущенным из точки Р в направлении п. Далее, если а ребро пути 7, содержащее Р и пересекающееся с уо более Глава 4. Плоские локально минимальные деревья. 248 чем по точке, то уо называют также кваэи-геодеэи веским лучом, вы- пущенным с ребра а сети Г в направлении и. Из предложения 4.19 вытекает следующий результат. Следствие 4.11 Иэ любой внутренней вершины произвольного правильного линейного дерева в любом направлении можно выпустить квази-геодезический луч,.

С любого ребра произвольного правильного линейного дерева в любом направлении, не перпендикулярном этому ребру, можно вьтустить квази-геодезический луч. В качестве первого приложения разработанной техники, мы докажем следующее полезное предложение, являющеесл обобщением классического результата о плоских минимальных деревьях (сьь ~9, 30, 69~). Предложение 4.20 Пусть Г -- произвольное линейное деревц даГ = М его геометрическая граница, и и выпукл л оболочка множества М. Тогда Г С и. Доказательство. Пусть сначала Г правильное линейное дерево.

Докажем предложение "от противного". Предположим, что существует точка Р из Г, лежащая вне и. Лемма 4.19 Пусть а произвольный выпуклый многоугольник, и Г произвольное правильное линейное дерево. Если Г не лежит целиком в щ то существует граничная вершина иэ Г, лежащая вне о. Доказательство. Пусть Р -- произвольная точка из Г, лежащая вне и. Если Р не является вершиной сети Г, то рассмотрим ребро е из Г, содержащее Р. Поскольку сс выпуклый многоугольник, а Р ф щ то одна из вершин сети Г, инцидентных ребру е, также не принадлежит и, поэтому, без ограничения общности, можно сразу предполагать, что точка Р - это вершина сети Г, Если Р .

граничная вершина, то утверждение леммы выполнено, Предположим, что вершина Р не принадлежит доГ. Тогда, так как Г правильное линейное дерево, вершина Р является устойчивой внутренней вершиной. Итак, пусть Р устойчивая внутренняя вершина. Пусть 1 некоторая прямая, отделяющая точку Р от выпуклого многоугольника и, Прямая 1 разбивает плоскость на две полуплоскости, которые мы обозначим через П' и П". Пусть, для опрсделенности.

Р 6 П'. Обозначим через и единичный вектор, перпендикулярный к 1 и направленный в полуплоскость П'. Выпустим из внутренней вершины Р квази- геодезический луч у в направлении и. Ясно, что у не пересекает о, поэтому концевая вершина луча у, принадлежащая доГ в силу леммы 4.18, лежит вне и. Лемма доказана. 4.4. Линейныс деревья. Из предположения о существовании точки Р е Г, лежащей вне щ и леммы 4,19 немедленно вытекает, что вне выпукюй оболочки множества М расположена точка из ЛХ противоречие, что и доказывает предложение 4.20 для случая правильных линейных деревьев. Пусть теперь Г -- произвольное линейное дерево. Повторив для него процедуру, описанную в доказательстве предложения 4.17, продеформируем Г сколь угодно малой деформацией в правильное линейное дерево Г„.

Характеристики

Список файлов диссертации