Геометрические свойства локально минимальных сетей (1097521), страница 61
Текст из файла (страница 61)
Определение. Максимум чисел вращения Фк(а, 6), взятый по всевозможным у.порядоченным парам ребер дерева Г, называется числом вращения 1ъ Г взвешенного 2-дерева Г. Отметим, что сч(а, Ь) = — св(Ь,а), и сч (а, Ь)+си(Ь,с) = св(а,с) для любых ребер а, Ь и с из Г, лежащих на одном пути в Г. Кроме того, если Си Г = съ(а, Ь), то ребра а и Ь инцидентны вершинам степени 1. Ребро 2-дерева, инпидентное вершине степени 1, т.е. граничной вершине, называется граничным ребром. Пусть Г взвешенное минимальное 2-дерево, и (а, Ь) произвольная упорядоченная пара его ребер.
Рассмотрим единственный путь ) в Г, соединяющий а и 6., и ориентируем его от а к Ь. Путь ~ является., очевидно, ломаной линией, поэтому определено кручение 1п 7 вдоль него, С другой стороны, определено число вращения Сч (а, 6) между ребрами а и Ь взвешенного 2-дерева Г. По определению, сну = сж(а, 6). Этот 4.5. Взвешенные бинарные деревья.
277 факт дает определенному только что числу вращения минимального взвешенного 2-дерева, естественную геометрическую интерпретапию. Утверждение 4.16 '1исло вращенил произвольного взвешенного минимального 2-дерева Г, как, плоского взвешенного бинарного дерева, совпадает с числом вращения дерева Г как плоского линейного дерева.
Таким образом, из утверждения 4.16 и следствия 4.21 получаем следующее важное утверждение. Следствие 4.22 Пусть Г минимальное взвешенное 2-дерево с положительными весами, затягивающее фиксированное конечное множество М точек плоскости. Тогда 1иГ < 12(м(ЛХ) — 1) + 6, где через ьиГ обозначено, как и выше, число вращения Г как плоского взоешснного бинарного дерева. 4.5.2 Обобщенный алгоритм Мелзака: случай трех точек Знание локальной структуры минимального взвешенного бинарного дерева с положительными весами позволяет построить для таких деревьев аналог алгоритма Мелзака. В данном разделе мы разберем случай трех точек, а в следующем общий случай. Итак, пусть взвешенное минимальное 2-дерево Г затягивает вершины треугольника АВС.
Обозначим через В единственную точку Штейнера сети Г. Пусть р, ц и г -- веса ребер ВА, ВВ и ВС, а пл, пв и по сдиничныс векторы, сонаправленные с векторами ВА, ЛВ и ЛС соответственно. В силу теоремы 2 о локальной структуре имеет место равенство: рпл + упв+ гпс = 6. Отсюда, в частности, вытекает, что числа р, о и г удовлетворяют правилу треугольника, т.е. сумма любых двух из них не превосходит оставшегося.
Опишем вокруг треутольника Вл'С окружность В~, и продолжим отрезок АВ за точку 5 до следующего пересечения прямой АВ с окружностью В1 в некоторой точке А'. Ясно, что угол ВВА' равен углу ВСА', а угол СВ.4' равен углу СВА', см. рис.
4.17. Построим характеристический треугольник РОЛ вершины В, положив 1,1Л = р ил, ЛР = а па и РЦ = г по (это возможно, так как рпл+ у ив +с по = 0). Обозначим через ор, сььу и он углы треугольника РЫЛ в вершинах Р, Ц и Л соответственно. Легко понять, что угол ВВА', равный утлу 278 Глава 4.
Плоские локально минимальные деревья. в'и-. --;А -.-' с Рис. 4.17: Минимальное взвешенное дерево, затлгивающее вершины треугольника, ВСА', равен ан, а угол СВ.4', равный СВА', равен ао. Поэтому треугольники А'ВС и РЯВ подобны. Аналогичная процедура может быть проделана и для двух других сторон треугольника АВС, а именно на них аналогично могут быть построены точки С' и В' и соответствующие треугольники АВС' и АВ'С, подобные треугольнику РЯВс, см.
рис. 4.17. Отметим, что точка 5 лежит на пересечении отрезков АА', ВВ' и СС'. Вычислим теперь длину отрезка АА'. Для этого выберем на отрезке о'А' точку о', такую что треугольник о'ВВ подобен треугольнику Р17К, и угол Во'5 равен ар (это можно сделать, поскольку угол ВВА' равен ан, а угол ВВА' больше чем ао).
Заметим, что треутольники ВСЯ и ВА'В' также подобны. В самом деле, угол ВА'У = ВА'В, очевидно, равен углу ВСЯ, а угол ВВ'А' равен х — ар = оо + ан, и поэтому равен углу ВВС. Используя все эти соображения, можно записать: р~ЯЯ'~ = 4~ЯВ~, р(Я'А'~ = ~ЯС~. В итого получаем: р )АА'! = р (ВА! + о (ВВ! + г (ВС( = ЪЪе181й(Г). Ясно, что анаюгично можно вычистить длины отрезков ВВ' и СС', показав.что ЯВВ'~ = г (СС'( = Же181й(Г). Из построения также ясно, что если а., Д и 7 утлы треугольника АВС в вершинах А, В и С соответственно, то имен>т место следующие неравенства: 4.б. Взвешенные бинарные деревья. 279 Пусть теперь р, ц и г --.
произвольные положительные числа, удовлетворяющие правилу треугольника. Рассмотрим треугольник РСдй, такой что длины его сторон лежащих напротив вершин Р., Сд и В, равны соответственно р, и и г. Обозначим через ар. ас1 и он соответственно углы треугольника РСдй в вершинах Р, Сд и Л. Пусть АВС --- некоторый другой треугольник на плоскости, и пусть а, В и 7 углы треугольника .4ВС в вершинах А, В и С соответственно. Назовем треугольник АВС рс4г-допустимы и, если а < я — ар, ~3 < я — ас7, и Т < я — ан. Из сказанного выше вытекает, что если существует взвешенное минимальное 2-дерево, состоящее из трех ребер А$, В$ и С$ с весами р, я и г соответственно, то треугольник АВС необходимо является рс1т-допустимым.
Покажем, что справедливо и обратное утверждение. Итак, пусть АВС рс1т-допустимый треугольник, и а, ф и Т его углы в вершинах А, В и С соответственно. Построим на его сторонах три треугольника ХВС, АВ'С и АВС', каждый из которых пересекается с АВС только по одной стороне, и такис что углы этих треугольников в их вершинах .4, В и С равны соответственно ар,ос~ и он.
Отрезки АА', ВВ' и СС' называются лвниллт Силикона, отвечающими сторонам ВС, АС и .4В соответственно. Рассмотрим теперь треутолы|ик А'ВС и опишем вокрут него окружность У. Поскольку угол ВА'С этого треугольника по построению равен ор, для любой точки $, лежащей на дуге б окружности У ограниченной точками В и С и не содержащей точку А', величина угла ВВС равна я — ар. Так как треугольник АВС по условию рчгдопустимый, его угол а меньше чем я — ар., поэтому точка А расположена вне ограниченного окружностью У круга. С лрутой стороны, из рс1г-допустимости треугольника АВС вытекает также, что 3+ ас1 < х и 7+ ан < я, поэтому точка А лежит внутри угла ВА'С.
Поэтому отрезок АХ пересекает дуту 6 в некоторой внутренней точке, которая. очевидно, лежит также и внутри треугольника АВС. Обозначим эту точку через $. Так как угол С$Х равен углу СВА' и равен ас7, угол С$.4 равен я — ос7. По аналогичным соображениям, угол В$А равен я — ан. Обозначим через пл, пв и пс, единичные векторы, сонаправленные с векторами $А, $В и $С соответственно. Отложим на луче $В точку Р', а на луче $А' точку Я' так что ~$Р'~ = д, а ~Я;У~ = р. Поскольку угол Р'$Сд' равен ан, треугольник Р'Я'$ конгруэнтсн треугольнику РСдВ, в частности, ~Р'Я = г, а угол Р'Сд'$ равен ац, и поэтому равен углу с)'$С, откуда следует, что прямые Р'Ц' и $С параллельны, Отложим теперь на луче $С точку Р" так что ~$Р" ~ = г.
Ясно, что четырехугольник $Р" Сд'Р' параллелограмм, и векторы $Р' и $Р" Глава 4. Плоские локально минимальные деревья. 280 Равны вектоРам впн и тпс; соответственно. Далее, ЯР'+ ЗРЯ = Щ', но вектор Я(>' в свою очередь равен — рпл, поэтому получаем в итоге рпл +дпв+ гпп = О.
Последнее означает, что взвешенное 2-дерево, составленное из отрезков АЯ, ВВ и СЯ, взятых с весами р, ц и ~ соответственно, является минимальным взвешенным 2-деревом затягивающим вершины треугольника АВС. Итак, нами доказана следующий результат, дающий полное описание взвешенных минимальных й-деревьев, затягивающих вершины треугольников. Предложение 4.28 Е Пусть р, в и г положительные числа. Треугольник АВС, вершины которого затягаваюпься взветиенным минимальным 2-деревом состоящим из трех ребер АЯ, ВЯ и СЯ с весами р, д и т соответственно, существует тогда и только тогда, когда числа р, в и г удовлетворяют правилу треугольника.
2. Пусть р, в и г положительные числа, удовлетворяющие правилу треугольника, и АВС некоторый треугольник на плос: кости. Паве~венное минимальное 2-дерево затягивающее вер1аины треугольника АВС и состоящее из трех ребер АЯ, ВЯ и СЯ с весами р, о и г соответственно, существует если и только если треугольник АВС является рс1г-допустимым. з. Если взвешенное минимальное 2-дерево, затягивающее данный треугольник по данному граничному отображению существует, то оно единственно.
4. Вершина Я степени 3 взвешенной минимальной сети, затягивающей верилины треугольника АВС, совпадает с точкой пересечения всех соответствующих линий С мпсона треугольника АВС. В частности, для каждого рог-допустимого треугольника соответствующие три линии Симпсона пересекаются в одной точке.
б. Вершина 5 степени 3 взвешенной минимальной сета, затягивающей вершины треугольника АВС, совпадает с точкой пересечения окружностей, описанных вокруг построенных выше треугольников А'ВС, АВ'С и АВС'. В частности, для любого рсрдопустимого треугольника три соответствующие окружности имеют общую точку. 4.5. Взвешенные бинарные деревья. 281 Предложение 4.28 позволяет обобщить алгоритм Мелзака на случай построения минимального взвешенного 2-дерева, затягивающего вершины произвольного треугольника АВС.
Итак, нам даны положительные числа р, а и г, удовлетворяющие правилу треугольника, и треугольник АВС. На первом шаге мы определяем числа сяр, оО и он, которые равны углам при вершинах Р, сХ и Й соответственно треугольника РХХВ, такого что ~РЯ~ = т, ~РВ~ = а и ЦВ~ = р, и проверяем, является ли треугольник АВС ре1г-допустимым. Если не является, то взвешенной минимальной сети не существует, и алгоритм заканчивает работу, в противном случае переходим ко второму шагу. На втором шаге мы построим вне треугольника АВС и на какой- нибудь его стороне, скажем на ВС, треугольник А'ВС такой что углы А'ВС и ВСА' треугольника А'ВС равны пе1 и оа соответственно.
Опишем вокрут треугольника А'ВС окружность В1. Точка пересеченил окружности У с линией Симпсона А.4' отличная от А' и есть искомая вершина Я взвешенной минимальной сети. 4.5.3 Обобщенный алгоритм Мелзака: общий случай Пусть С -"- произвольное взвешенное бинарное топологическое дерево с положительными весами, ЛХо некоторое подмножество вершин из С, содержащее все его вершины степени 1, и пусть,З: ЛХо — ь Гяз произвольное граничное отображение, д~ЛХо) = ЛХ. Предположим, что веса любых трех ребер дерева С, инпидентных одной и той же его вершине степени 3, удовлетворяют правилу треутольника, т.е. выполнено необходимое условие существования взвешенного минимального дерева с такими весами.
Мы предъявим алгоритм обобщенный алгоритм Мелзака. позволяющий ответить на следующий вопрос: существует ли погруженная минимальная взвешенная сеть 1': С ь Ьа с границей Д, или, как мы будем говорить, существует ли у С минимальная реализацил с границей Д. Прежде всего, можно предполагать без ограничения общности, что ЛХп совпадает со множеством всех вершин степени 1 бинарного дерева С. Действительно, если 2-дерево С имеет минимальную реализацию с границей Д, то эта реализация единственна, см, предложение 5.8 главы 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
