Геометрические свойства локально минимальных сетей (1097521), страница 60
Текст из файла (страница 60)
Отметим, что путь В пока вообще не изменялся. Ломаная В является путем в дервве Г', соединяющим его граничные вершины А и В. 14ак и выше, рассмотрим разбиение пути б на фрагменты Вы ., ., Л» р+з (по отношению к границе дерева Г'), и обозначим через А, и В, начальную и конечную вершины фрагмвнта Ь,.
Из построения следуст, что все внутренние вершины ломаной В являются внутренними вершинами дсрсва Г' (их степень в Г' больше 1). Поэтому путь б может не окаэатьсл хорошим в Г' только если некоторые из точек В,, 1 = 1,..., д — р+ 1, являются внутренними вершинами дерева ГС Напомним, что точка В, принадлежит границе выпуклой оболочки и' для (р+ 1 — 1)-го уровня выпуклости множества дяГС Сдвинем каждую из Глава 4. Плоские локально минимальные деревья.
272 таких внутренних вершин В;, внутрь соответствующего о'. Ясно, что при такой перестройке дерева Г' его гранина вообще не меняется, а кручение пути В можно изменить сколь угодно мало. Теперь путь В является хорошим, что и требовалось. Первое утверждение теорегиы 6 полностью доказано. Для доказательства точности полученной оценки достаточно рассмотреть ломаную, имеющую форму двойной спирали, и устроенную так, как показано на рисунке 4.16. На рис, 4.16 рассмотрен случай к = 2.
Все вершины изображенной ломаной являются граничнылеи, число уровней выпуклости граничного множества равно 2, число вращения равно 18. Общий случай получается из этого увеличением числа витков спиралей. Тем самым теорема полностью доказана. Рис. 4.16: Двойная спираль с числом вращения 18. 4.4.10 Некоторые следствия Продемонстрируем, как работает теорема 6 на примерах плоских локально минимальных деревьев-следов, локально минимальных параметрических деревьев и взвешенных локально минимальных деревьев.
Пусть Г локаяьно минимальнос дерево (след), затягивающее конечное множество М точек плоскости, и Г: С вЂ” з Кз его канонический представитель. Тогда, из теоремы о локальном устройстве таких сетей (см. главу 31 вытекает, что дерево Г --. линейное, и угол между любыми двумя соседними ребрами дерева Г больше ияи равен 120'. Легко показать, что геометрическая граница дяГ такого линейного дерева совпадает со множеством всех его вершин степени 1 и 2, из которого выброшены все фиктивные вершины степени 2. Кроме того, из теорем о локальном устройстве следует, что д Г с ЛХ. Поэтому, из теоремы 6 немедленно получается следующее обобщенно предложения 4.10. Следствие 4.18 Пусть Г произвольное (не облзительно бинарное) локально минимальное дерево, затягивающее фиксированное конечное 4.4.
Линейные деревья. 273 множество ЛХ точек плоскости, Тогда 1кГ < 12(зг(двГ) — 1) + 6 < 12(м(ЛХ) — 1) + 6. Замечание. Отметим, что геометрическая граница до Г не может быть определена исходя лишь из графа С и граничного отображения дГ, так как а рг1ог1 не понятно, какие из вершин степени 2 графа С становятся фиктивными вершинами минимального дерева Г.
Поэтому разумно дать промежу.точную оценку, определив, например, множество М', состоящее из всех точек из ЛХ, соответствующих при граничном отображении дГ вершинам степени 1 и 2 графа С. Из теоремы 6 получаем следующий результат. Следствие 4.19 Во введенных обозначениях, 1и Г < 12(зг(ЛХ') — 1)+6. Пусть Г: С ь п~ локально минимальное параметрическое дерево типа С с границей дГ, затягива1ощее конечное множество ЛХ точек плоскости.
Вершины дерева Г, не попавшие во множество ЛХ, будем, как обычно, называть подвижными. Тогда. из теоремы о локальном устройстве таких сетей (см. главу 3) вытекает, что дерево Г линейное, и в каждой подвижной вершине сети Г сумма направлений всех приходящих в эту вершину ребер равна О. Отсюда следует, что каждая подвижная вершина из Г является внутренней вершинои линейного дерева Г.
Иными словами, геометрическая граница дзГ содержится во множестве ЛХ. Поэтому, из теоремы 6 немедленно получается следующий результат. Следствие 4.20 Пусть Г произвольное лона ьно минимальное параметрическое дерево, затягивающее фиксированное конечное множество М точек плоскошпи. Тогда 1кГ < 12(зг(двГ) — 1) + 6 < 12(зг(ЛХ) — 1) + 6. Пусть теперь Г -- взвешенное локально минимальное параметрическое дерево типа С с границей 6, затягивающее конечное множество М точек плоскости.
Предположим, как обычно, что веса всех ребер сети Г положительны. Тогда, из теоремы о локальном устройстве взвешенных локально минимальных сетей (см. главу 3), вытекает, что дерево Г линсйнос, и в каждой подвижной вершине сети Г линейная комбинация направлений всех приходящих в нее ребер с коэффициентами, равными весам этих ребер, равна О. Отсюда, гак как все веса положительны, следует, что каждая подвижная вершина из Г является внутренней вершиной линейного дерева Г. Иными словальи, геометрическая граница дзГ содержится во Глава 4.
Плоские локально минимальные деревья. 274 множестве М. Поэтому, из теоремы 6 немедленно получается следующее утверждение, обобщающее результаты из (49, 39] для минимальных взвешонных бинарных деревьев. Следствие 4.21 Пушнь Г произвольное взвешенное локально миними ьнов дерево с положительными весами, гапьягаваюшгс. фиксированное конечное множество ЛХ точек плоскости. Тогда ЬяГ < 12(дд(ддГ) 1) + 6 < 12(дг(ЛХ) 1) + 6 Замечание.
В работах [49, 39) этот результат был| получен для минимальных взвешенных бинарныг деревьев без использования теоремы 6, исходя только из теоремы о локальной структуре таких сетей и разработанном автором обобщении алгоритма Мелзака для взвешенных локально минимальных бинарных деревьев, см. ниже. 4.5 Геометрия плоских минимальных взвешенных бинарных деревьев Оказывается, для плоского взвешенного бинарного дерева можно определить число вращения исходя только из плоской топологии дерева (т.е.класса его планарной эквивалентности) и функционала взвешенной длины, Другими словами, можно определить чисдю вращения для класса планарно эквивалентных плоских взвешенных деревьев.
Аналогичная конструкция была изложена в разделе 4.2 для классов планарной эквивалентности плоских бинарных деревьев. Напомним, что определение числа вращения в разделе 4.2 было подобрано так, что для каждого локально минимального бинарного дерева его число вращения как плоского линейного дерева совпадает с его числом вращения как плоского бинарного дерева. Это дает возможность при поиске, локально минимальных деревьев с данной границей для каждой топологии сразу вычислить число вращения (плоского бинарного дерева), что в сочетании со следствием 4.21, позволяет отсеивать многие нереазизующиеся топологии нс строя соответствующей минимальной реализации (с помощью алгоритма Мелзака или его аналогов). Определяемое в данном разделе число вращения взвешенного бинарного дерева обладает аналогичным свойством; для каждого минимального взвешенного бинарного дерева его чисто вращения как плоского взвешенного бинарного дерева совпадает с его числом вращения как плоского линейного дерева.
Поэтому это понятие играет аналогичную роль, а именно, позволяет отсеивать многие топологии а ргуот, нс строя соответствующих минимальных реализаций. Кроме того, 4.5. Взвешенные бинарные деревья. 275 в данном разделе строится обобщение алгоритма Мелзака на случай взвешенных бинарных деревьев, позволяющий строить такие деревья с помощью компьютера, и доказываотся результат об "общем положении" таких деревьев, имен>щая на наш взгляд самостоятельный интерес (аналог предложения 4.9).
Замечание. Отметим, что плоские бинарные деревья в данном контексте предполагаются вложенными (речь идет о классе планарной эквивалентности). 4.5.1 'Число вращения плоского взвешенного бинарного дерева Локальное устройство взвешенных минимальных бинарных деревьев (или. для краткости, 2-деревьев) описано в теореме 2. Из теоремы 2 вытекает, напомним, что все ребра плоского минимального взвешенного дерева Г прямолинейные отрезки, и линейная комбинация единичных векторов направлений ребер из Г, входящих в произвольную его подвижную вершину, с коэффициентами --. весами этих ребер равна нулю.
Отсюда и из предположения о положительности весов, очевидно, вытекает, что веса каждых трех ребер взвсшенного минимального 2- дерева.,инцидентньсс одной и той же его точке Штейнера, удовлетворяют сшедуюшеыу правилу: сумма любых двух из них не меньше чем третий —.— это необходимое условие существования такого взвешенного минимального 2-дерева.
При этом, если имеет место равенство, то одно из ребер меньшего веса необходимо содержится в другом, т.е, в этом случае минимальное дерево не может быть вложенным. Поэтому, говоря о взвешенных 2-деревьях, мы в дальнейшем всегда будем предполагать, ито в каждой вершине И степени 3 вьтолнено следующее правило треугольника; сумма весов любых двух инцидентных и ребер строго больше веса третьего инцпдентного и ребрш Обобщим теперь понятие числа вращения на случай взвешенных 2- деревьев. Для этого сначала рассмотрим произвольную точку Штейнера Р взвешенного 2-дерева Г, и пусть е„1 = 1, 2, 3, — ребра сети Г, инцидентные Р.
Обозначим через ш, вес ребра е,. Рассмотрим на плоскости треугольник Р~РяРз, такой что для любых трех различных 1, у' и й, где 1 < 1, у, й < 3 длина стороны Р;Р. равна шю Этот треугольник существует, так как веса ш„1 = 1, '2, 3, удовлетворяньт. по предположению, правилу треугольника. Треугольник Р1 РхРз называется характлеристииескиль треугольником вершины Р. Обозначим через еи угол характеристического треугольника в вершине Р,. Глава 4. Плоские локально минимальные деревья. 276 Рассмотрим теперь произвольную упорядоченную пару (е,,е ), составленную из ребер еь 1 = 1, 2, З,инцидентных Р.
Пусть 67 -- некоторая хорошая окрестность вершины Р сети Г, т.е.,напомним, такая окрестность П С м~ точки Р,что ее пересечение с деревом Г представляет собой звезду с центром в Р и вершинами степени 1, лежащими на окружности дс7.
Тогда пересечение дП О Г границы окрестности П с сетью состоит из трех точек Ап 1 = 1, .2, 3. Будем считать., для опредеченности, что А~ 6 еь Обозначим через б дугу из ОП, ограниченную точками .4, и А. и содержащую Аь, где 6 ~ 1 и 6 ~ уд Если движение вдоль б от .4, к А происходит по часовой стрелке, то сопоставим паре (еп е.) число — оь/(я/3), В противном случае, сопоставим паре (е,, е.) число +оь)(х)3).
Это число называется твистингом от ребра е; к ребру е;. Рассмотрим теперь произвольную пару (а, 6) ребер дерева Г, и пусть единственный путь в ",~ соединяющий зти ребра. Ориентируем путь 3 от а к 6, и пусть а = еы,.,,ее = 6 -- последовательные ребра пути у, а Ро, Р„...,Ре его последовательные вершины. Для каждой внутренней вершины Р, пути у рассмотрим пару последовательных ребер (е„еьы) из у, инцидентных вершине Р,. Твистинг от ребра е, к ребру е,в, называется твистингом вершины Р, ориентированного идти у, Определение. Сумма твистингов всех внутренних вершин ориентированного пути 7, идущего от ребра а к ребру Ь во взвешенном 2-дереве Г„называется числом вращения Ьч (а, 6) упорядоченной нары (а, 6) ребер из Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
