Геометрические свойства локально минимальных сетей (1097521), страница 44
Текст из файла (страница 44)
Однако, если на каждом шаге обратного хода выполняются условия леммы 4.8, то такая реализация существует. Более того, из алгоритма Хванга-Мелзака вытекает следующая теорема единственности, полученная Хвангом (351, см. также обобщение этого результата в главе 5.
Предложение 4.7 Дяя каждого дерева Штейнера С и граничного отображения Д: Ыо — > П4 сушелтнвует нг более одной минимальной реализации. Приведем еще одно полезное следствие из рассмотренных алгоритмов. Как было отмечено выше, для успешного завершения обратного хода алгоритма Мещанка необходимо и достаточно выполнение на каждом шаге условий леммы 4.8. Легко видеть, что если существует минимальная реализация 2-дерева С с граничным отображением,д, то при маном шевелении границы, т.е.
при малом изменении граничного Глава 4. Плоские локально минимальные деревья. 202 отображения Д, условия леммы 4.8 по-прежнему выполняются. Чтобы сформулировать соответствующий результат, введем следующее определение. Путть С произвольное бинарное дерево, н ЛХо некоторое подмножество множества его вершин. Введем на множестве всех отображений р': ЛХо -+ Кз метрику р следующим образом. Если,д и 3' два таких отображения, то положим р(8,8 ) = п1ах ф(х), 3 (о)~. Предложение 4.8 Предположим, что 2-дерево С имеет минимальную реализацию Г для некоторого граничного отображения 8, заданного на множестве ЛХп всех вершин из С степени 1. Тогда существует такое е > О, что для любого граничного отображения,З', р(11,.р') < е, дерево С также имеет минимальную реализацию с граничным отображением,З', Иными словами, минимильные 2-деревья устойчивы при малые вариациях границы.
Более пюго, для любого е > 0 сушешпвуетп такое б > О, тпо для всех граничные отображений Д' дерева С, таких чгпо р(У,Д) < б, суи1ествуют минимальные реализации Г' дерева С с границами 8', и расстояние между обризами Г(о) и Г'(п) произвольной вершины и й С при отображениях Г и Г' меньше ". Иными словами, минимальная реализация дерева С непрерывно зависит от граничного отображения этого дерева. Замечание.
Предложение 4.8 не может быть обобщено на произвольные деревья Штсйнера в силу того, что при малом шевелении граничного отображения угол между ребрами невырожденных компонент, стыкукьщихся в некоторой вершине степени 2, может стать меньше 120' (если, конечно, до этого он был в точности равен 120'). На1юмним, что результатом прямого хода алгоритма Мелзака является пара точек, В качестве первого шага обратного хода мы строим отрезок, соединлющий полученные точки. Этот отрезок называется линией Симпсона. Отметим, что, в силу произвольности выбора усов на каждом шаге прямого хода, мы, вообще говоря, можем построить много разных линий Симпсона. На самом деле, существует естественное взаимно однозначное соответствие между линиями Симпсона и ребрами 2-дерева С. Действительно, в процессе прямого хода мы перестраиваем дерево С, отрезая от него выбранные усы.
На последнем шаге прямого хода от дерева С остается ровно одно ребро, которое и надо поставить в соответствие полученной линии Симпсона. Несложно 4.2. Бинарные деревья. 203 показать, что каждому ребру дерева С соответствует некоторая линия Симпсона. Более того, имеет место следующее утверждение ~64]. э'тверждение 4.5 Если 2-дерево С имеет минимальную ре лизицию Г с граничным отображением Д, то длина любой линии Симпсона сети Г равни длине этой сети. Мы используем полученные следствия для доказательства следующего важного для нас результата об общем положении. 4.2.6 Теорема об общем положении Пусть Г минимальное 2-дерево, затягивающее конечное множество ЛХ точек плоскости.
Определение. Будем говорить, что Г находится в общем положении, если каждое его ребро е находится в общем положении с каждым отрезком ~т,т.~, соединяющим любую пару вершин ты пьг из М. Последнее означает, что ребро е может пересекаться с отрезком ~т,т ~ лишь по одной точке, которая или является внутренней как для е, так и для ~т,т ~, или принадлежит М. Предложение 4.9 Для любого минимального 2-дерева, затягивающего конечное множество М точек плоскости, состоящее по крайней мере из трех точек, и для каждого е > 0 существует деформация множества М в некоторое множество М', такая что: ° расстояние между каждой смещенной вершиной т' е ЛХ' и ее начальным положением т е М не превосходит е; ° разбиение множества ЛХ на уровни выпуклости сохраняется при этой деформации; ° эти деформация может быть продолжена до деформации минимального 2-дерева Г в классе минимальных 2-деревьев в некоторое минимальное 2-дерево Г', пшпология которого совпадает, конечно, с топологией исходного дерсви Г; ° полученное дерево Г' находится в общем положении.
Доказательство. Тот факт, что любая достаточно малая деформация граничного множества М может быть продолжена до деформации затягивающего это множество минимального 2-дерева Г в классе минимальных 2-деревьев и поэтому, очевидно, без изменения топологии Глава 4. Плоские локально минимальные деревья. 204 дерева Г, вытекает из предложения 4,8. Ясно также,что среди таких деформаций существует деформация, сохраняющая разбиение множества ЛХ на уровни выпуклости, и такая что в продеформированном множестве ЛХ, которое мы снова обозначим через ЛХ, все уровни выпуклости представляют собой многоугольники с углами меньшими чем х. Заметим.
что любые достаточно малые деформации не меняют разбиение на уровни выпук юсти такого перестроенного множества М, Таким образом, осталось показать, что существуют сколь угодно малые деформации граничного множества М, переводящие сеть Г в сеть общего положения. Начнем с того. что с помощью малой деформации преобразуем множество ЛХ в такое множество, которое мы снова обозначим через ЛХ, что угол между любой парой отрезков, соединяющих точки из ЛХ, не кратен я/3.
Для так псрестроенного множества М лишь один из отрезков, соединяющих точки из ЛХ, может оказаться параллельным ребру затягивающей ЛХ перестроенной минимальной сети, которую мы снова обозначаем через Г. Предположим, что такой отрезок существует, и обозначим его через а. Так как множество М состоит по крайней мере из трех точек, существует точка Р Е ЛХ, не являющаяся концевой точкой отрезка а. Напомним, что направление любой линии Симпсона минимального 2-дерева Г совпадает с точностью до т(3 с направлениями ребер Г и может быть записано в виде: Р ехр(~/ — Хк,я/3) + Р ехр(ъ/ — Нт!3), Р,ем,гдгг где ЛХ и й --- некоторые целые числа, (Здесь мы рассматриваем точки Р и Р из ЛХ как соответствующие комплексные числа).
Поскольку умножение на ехр(~/ — Тйя/3) задает изоморфизм плоскости, ясно, что сушеству.ет изменяющее направление линии Симпсона смещение точки Р, причем сколь угодно малое. Отрезок а при этом не изменяется. Таким образом, существует деформация множества ЛХ, такая, что направления всех отрезков, соединяющих точки из перестроенного ЛХ, отличны от направлений ребер перестроенной сети Г. Снова будем обозначать перестроенное множество и сеть теми же буквами.
Наконец, предположим, что некоторая точка Штейнера Р соти Г попала на отрезок а, соединяющий некоторые точки из ЛХ. Нам остается показать, что малыми деформациями можно 'снять" точку Штсйнера Р с отрезка а. Если таких точек несколько. то мы будем их "снимать" последовательно, Итак, пусть Р Е а, и обозначим через е одно из ребер сети Г, инцидентное Р. Разрежем сеть Г по ребру е. Мы получим две сети Г' 4.2. Бинарные деревья.
205 и Г". Множество М, в свою очередь, так же распадется на две компоненты: множества ЛХ'и ЛХ", инцидентные Г'и Со соответственно. Для опроделенности, предположим, что М' содержит точку, не явчяющуюся концевой вершиной отрезка а. Напомним, что для каждого ребра сети Г найдется линия Симпсона, содержащая это ребро. Пусть Х -- линия Симпсона, содержащая ребро е. Напомним, что пользуясь алгоритмом Мелвина можно построить по точкам множества М" такой правильный треугольник Т с однои отмеченной вершиной В; и, пользуясь точками множества ЛХ', такую точку В,что ° отрезок ВВ совпадает с линией Симпсона Хс ° вершина Р совпадает с точкой пересечения линии Симпсона Х с описанной закрут треугольника Т окружностью э'~.
Принимая во внимание, что ° расположение вершин треутольника Т определяется только точками из ЛХ": ° направление линии Симпсона Х, можно изменить малым |певелением любой точки из ЛХ', в частности, той точки из М', которая не является концевой точкой отрезка а; ° в результате деформации, порожденной шевелением этой точки из ЛХ' отрезок а и окружность У не изменяются, а линия Симпсона Х меняет свое направление при неподвижной концевой точке В; можно построить малую деформацию.
в результате которой вершина Р перестает принадлежать отрезку а. Доказательство теоремы закончено. 4.2.7 Теорема о связи числа вращения плоского минимального бинарного дерева и количества уровней выпуклости его граничного множества Основным результатом данного раздела является следующий важный результат. Предложение 4.10 Если лоское минимальное 2-дерево Г затягивает коне гное подмножество М точек плоскости, имеющее к уровней выпуклости, то число вращения 1зиГ дерева Г не превосходит 12(1е — 1)+ Глава 4. Плоские локально минимальные деревья. 206 5, Эта оценка является точной в следующем смысле.' для любого целого й > 1 существует минимальное 2-дерево Г, 1жГ = 12[я — Ц + 5, граница копюрого имеет ровно к уровней выпуклости. Замечание.
Отметим, что предложение 4.10 существенно ограничивает возможные топологии минимальных 2-деревьев, если число уровней выпуклости граничного множества ЛХ, состоящего из и точек, невелико по сравнению с максимально возможным числом уровней выпуклости у множеств. имеющих и точек. В самом деле, ясно, что множество, состоящее из п точек, имеет не более [(п + 2)/3) уровней выпуклости, а чисхо вращения плоского 2-дерева с и граничными вершинами не превосходит п — 2. Поэтому, предложение 4,10 дает нетривиальную оценку если только 12[к — Ц + 5 < п — 2, т.е. к < [и + 5)/12. Таким образом, предложение 4.10 можно уточнить следующим образом. 'Теорема 5 Если плоское минимальное 2-дерево Г затягивает конечное подмножество ЛХ точек плоскости, состоящее иэ и элементов и имеюиьее й уровней вьепуклосхпп, то число вращения бкГ дерева Г не превосходит шш[п — 2,12[1 — Ц+ 5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
