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

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

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

Поэтому. если какие-то вершины степени 3 попали во множество ЛХо,то следует сначъча рассмотреть ограничение Д граничного отображения,д на, множество всех вершин степени 1 из 2-дерева С, проверить, существует ли минимальная реализация Гь дерева С с границей Д, и сели да, то проверить, совпадает ли ограничение отображения Г1 на ЛХо с заданным отображением 8. Итак, мы предполагаем, что ЛХо Глава 4. Плоские локально минимальные деревья. 282 совпадает с множеством всех вершин из С степени 1. Если С имеет ровно одно ребро, то, очевидно, минимальная реализация существует тогда и только тогда, когда образы граничных вершин этого дерева различны (напомним, что мы ищем погруженные сети).

Пусть теперь С состоит более чем из одного ребра. По лемме 4.7, дерево С имеет некоторые усы (е, е'). Пусть и и и' -- - вершины степени 1, инцидентные ребрам е и е' соответственно, а в вершина степени 3, инцидентная одновременно ребрам с и с'. Обозначим через ев третье ребро, инцидентное вершине в, а через и«отличную от в вершину, инцидентную ребру е". Если образы А =,3(и) и А' = «3(и') вершин о и и' при отображении Д совпадают, то минимальной реализации не существует. В противном с.яучае, рассмотрим характеристический треугольник вершины в, и построим на плоскости треугольник АХВ, подобный этому характеристическому треутольникуч При этом, если р, о и г веса ребер е.

е'и ео соответственно,и РОК характеристический треугольник вершины в, где ~ЯВ~ = р, ~КР~ = д, и ~РГд~ = г, то соответствие между вершинами треугольников АХВ и РОВ устанавливается так: А «-> Р, А' «ь Я, и В +~ Л. Очевидно, треугольник АХВ может быть построен двумя способами. Перестроим дерево С в дерево С', отрезав от С усы. Определи граничное отображение Д' на множестве Ыо всех вершин из С' степени 1, положив его равным Д везде, кроме в, и определив 3'(в) равным В. Превратим дерево С' во взвешенное, ограничив функцию веса, заданную на ребрах из С, на ребра из С'. Очевидно, полученное взвешенное дерево по прежнему будет удовлетворять условию треугольника. Отметим, что в результате описанной перестройки количество граничных ребер уменьшилось на 1.

Следующая лемма вытекает из элементарных планиметрических построений, аналогичных доказательству предложения 4.28. Лемма 4.24 В сделанныт обозначениях, если взвешенное. 2-дерево С имеет минимальную реализацию Г с границей Д, то для одного из двух треугольников АА'В дерево С' имеет минимальную реализацию Г' с границей Д'. Миним льные сети Г и Г' совпадаюи«на С' 1 е". Треугольник АА'Г(«о) является рс1г-допустимым. В частности, луч с вершиной В в направлении точки Г'(«о) = Г(ю) содерокигпся внутри угла АВ.4' и содержит точку Г(в), которая, в свою очередь, лежит на окружности Я', описанной вокруг треугольника АВА', п тпочкп Г'(ж) = Г(ш) лежит внг круга, ограниченного окружностью У. Обратно, если сушествуеьп минимальная реализация Г' дерева С' 4.5. Взвешенные бинарные деревья.

283 с границей Д', гаакая что треугольник АА'Г'[ш) является рс(г-допустимым [и, поэтому выполняютися следующие условия: ° луч с вершиной В в направлении точки Г'[и~) содержится вну- три угла АВА', и ° точка Г'[и) лежит вне круга, ограниченного окружностью о~, которая описана вокруг правильного треугольника АВХ), то существует минимальная реализация 1' дерева С с границей д, которая получается из Г' так.

Обозначим через С гпочку пересечения интервала [Г'[в), Г'[и)) с окружностью У. На всех ребрах из С, отличных от е, е' и е", отображение Г определим равным отображению Г'. На ребрах е, е' и ео определим его так, чтобы эти ребра переходили соответственно в отрезки [С,А), [С,А') и [С,Г'[и)) соответственно. При этом, конечно же, Г[в) = С. АГ П(Ч В=('(л) А — Г(ч 1эис. 4.18; Иллюстрация идеи обобщенного алгоритма Мелзака. Итерируя описанный только что процесс перестройки взвешенного дерева С и граничного отображения (3 во взвешенное дерево С' и граничное отображение Д' до тех пор, пока в результирующем дереве останется ровно одно ребро, лгы роализусм прямой ход обобщенного алгоритма Мелзаьса.

1(аждзл итерация называетсл шагом прямогю хода обобщенного алгорип(ма Мелзака. Ясно, что сели прямой ход состои~ нз п шагов, то существует 2" реализаций прямого хода, в зависимости от выбора треугольника АВХ на каждом шаге. Для завершения обобщенного алгоритма Мелзака, необходимо выполнить так называемый обратньгй ход. На первом шаге обратного хода мы проверяем, не совпали ли образы граничных вершин результирующего дерева, состоящего из одного ребра. Ксли нет, то строим минимальную реализацию этого дерева, отображал единственное его Глава 4. Плоские локально минимальные деревья.

284 ребро в отрезок, с'оединяющий образы граничных вершин при результирующем граничном отображении. После этого, начинаем последовательно строить минимальные реализации взвешенных деровьев, полученных на прямом ходе. Соответствующие построения мы уже описали в лемме 4. 24. Если на одном из шагов обратного хода нарушаются условия леммы 4.24, то переходим к испытанию следующей из 2" реализаций прямого хода, Таким образом, или при проверке очередной реализации прямого хода обратный ход обобщенного алгоритма Мелзака приведет к построению искомой минимальной реализации и закончит работу, или будут проверены все 2" вариантов и сделан вывод о том, что данное взвешенное дерево С не имеет минимальной реализации с граничным отображением д. Нак мы уже отмечали, к успешному завершению прямого хода обобщенного алгоритлса Мслзака может привести не более одной реализации прямого хода.

Обобщенный алгоритм Мелзака, подобно стандартному. алгоритму Мелзака, не умеет отсеивать 'неперспективные" посжедоватечьности и, поэтому, тратит много времени на работу с ними. В случае бинарных деревьев локально асиниасатьной длины, напомним, имеется алгоритм Хванга, позволяющий заранее понять, как устроена та единственная последовательность треугольников АП.4', которая может привести к успешному завершению алгоритма Мелзака. В случае взвешенных локально минимальных бинарных деревьев анаже гичная конструкция не работает. В заключении данного пункта мы приведем два важных следствия из обобщенного алгоритма Мелзака.

Первое из них позволяет быстро вычислять вос взвешенного асинимального бинарного дерева. Предположим, что взвешенное бинарное дерево С с границей сЗ и с положительными весами имеет минимальную реализацию Г. Тогда, очевидно, для каждого ребра е дерева С можно так подобрать последовательность отрезания усов при работе прямого хода алгоритма Мелзака (вообще говоря, многими способами), что на последнем шаге перестроенное дерево совпадет как раз с ребром е. Отрезок Е на плоскости.

являющийся минимальной реализацией этого однореберного взвешенного дерева, называется линией Симпсона ребра е взвешенного минимального дерева Г, Отметим, что отрезок Е однозначно определяется ребром е и реализацией Г. Напомним, что в случае локально минимальных бинарных деревьев длина линии Симпсона произвольного ребра такого дерева совпадает с длиной всего минимального дерева, см, утверждение 4,5. Оказывается, в случае взвешенных бинарных деревьев имеет место аналогичное утверждение, Предложение 4.29 Пуста С взвешенное бинарное дерево с ноло- 4.5. Взвешенные бинарные деревья.

285 лсительньлми весами, и предположим, что существует его минимальная реализац я Г с границей В. Обозначим через В длину линии Симпсона, соответствующей ребру е из С при минимальной реализации Г, а через р вес ребра е. Тогда имеет место следующее равенство: рВ = %е1йЫ(Г). Доказательство. Предположим, что граница М = ЯЪ|ы) дерева Г состоит по крайней мере из 4 точек (случай трех точек рассмотрен в предыдущем разделе, слу.чай двух точек очевиден). В силу леммы 4.7, существуют граничные ребра е и е' иэ С, отличные от е, образующие усы.

Пусть в вершина из С инцидснтная обоим ребрам е и е', и ео третье ребро 2-дерева С, инцидентнос в. Обозначим через и, о' и оо вершины ребер е, с' и с", отличные от в соответственно, и положиы А = Г(оо), В = Г(о), С = Г(и') и Я = Г(в). Построим на отрезке ВС треугочьник Л'ВС, подобный характеристическому треугольнику вершины ж При этом, так как минимальная реализация Г уже имеется, положение вершины Л' определено однозначно: точки А' и Я должны лежать в разных полуплоскостях по отношению к прямой ВС. Обозначим через Г' минимальную реализацию дерева взвешенного дерева С',полученного из С отрезанием усов е и е'.

Очевидно, Г' получается из Г выбрасыванием ребер ЯЛ, ВВ и ЯС и добавлением ребра АА' веса р", где ро вес ребра ео в С. Поскольку ребра е и е' по построению отличны от ребра е, в дереве С' осталось ребро е. Кроме того. по определению линий Симпсона, линии Симпсона минимальных взвешенных 2-деревьев Г и Г' отвечающие ребру е, совпадают друг с другом, и, в частности, их длины одинаковы и равны Г. Докажем предложение по индукции. Д именно, предположим, что для всех 2-деревьев с числом граничных вершин меньшим чем у Г предложение имеет место. В частности, по предположению: рй = Ъеф11ь(Г').

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

Но, с другой стороны очевидно, р В = Чсе1й1П1Г') = ЧефЫ(Г) — %е1яЫ1Го) -~- ро1о = ЪКе1яЫ(Г). Глава 4. Плоские локально минимальные деревья. 286 Предложение доказано. Приведем еше одно важное следствие из алгоритма Мелзака, касающееся устойчивости минимальных взвешенных бинарных деревьев (аналог предложения 4.8). Напомним, что выше мы определили расстояние р на множестве граничных отображений бинарного дерева как максимум расстояний между.

образами соответствующих точек. Предложение 4.30 Предположил, что взвешенное 2-дерево С имеет минимальную реализацию Г для некоторого граничного от,ображения Д, заданного на множестве ЛХо всех вершин из С степени 1. Тогда существует такое е > О, что для любого граничного отображения ХХ', рЦЗ,ХХ') < е, дерево С также имеет минимальную реализацию с граничным отображением Д'. Иными словами, минимальные 2-деревья устойчивы при малых вариациях границы. Более пього, для любого е > О существует такое б > О, что для всех граничных отображений,д' дерева С, таких что р(Д',Д) < б, существуютп минимальные реалчзацин Г' дерева С с границами Д', и расстояние между образами Г(о) и Г'(и) произвольной вершины и Е С прп отображениях Г и Г' меньше е.

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

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