Геометрические свойства локально минимальных сетей (1097521), страница 12
Текст из файла (страница 12)
Тогда, из следствия 1 вытекает, что дерево Г --. линейное, и геометрическая граница ддГ содержится во множестве М. Следствие 2 Пусгаь Г произвольное локально минимильнос взвешенное дерево тини С с положительной весовой функцией, зитягивающсс фиксированное конечное множество М точек плоскости. Тогда си Г < 12(дд(ддГ) — Ц + 6 < 12(дс(ЛХ) — Ц + 6. Если предполагать дополнительно, что (взвешенное) локально минимальное дерево Г является бинарным деревом, то приведенные только что результаты можно усилить.
Во-первых, в этом случае естественно предполагать, что М = ддГ, и легко показать, что неравенство из следствия 2 превращается в строгое. Кроме того, в этом случае можно естественно определить число вращения плоского бинарного (взвешенного) дерева исходя лишь из класса его планарной эквивалентности и весовой функции. Именно так было определено число вращения плоского бинарного дерева в работе автора и А. А. Тужилина [43).
Такой подход позволяет при переборе возможных топологий минимальных бинарных деревьев с данной границей отсеивать большое число вариантов исходя только из класса планарной эквивалентности дерева и весовой функции. Пусть Г плоское бинарное дерево, и (а, 6) произвольная упорядоченная пара его ребер. Рассмотрим единственный ориентированный путь у(а, Ь) в Г, начинающийся на а и заканчивающийся на Ь. Тогда, проходя через каждую внутреннк>ю вершину пути у(а, 6), мы сворачиваем или "налево" или "направо' (напомникц что предполагается фиксированной некоторая ориентация плоскости). Более формально, для каждой внутренней вершины Р пути у1а, 6) построим круговую окрестность 1Х, пересечение которой с Г состоит из трех ребер, стыкующихся в Р. Пусть 4 и В точки пересечения с окружностью дХХ входящего в Р и выходящего из Р ребер пути у(а,6) соответственно.
Если, двигаясь по окружности дХХ от точки .1 к точке В в положительном направлении, мы пройдем через точку пересечения дХХ с третьим инцидентным Р ребром из Г, то будем говорить, что в Р мы свернули "налево", а если нет то "направо". Числом вращения бн(а,Ь) упорядоченной пары (а, Ь) ребер бинарного дерева Г называется разность Введение. 48 между количеством левых и правых поворотов во всех внутренних вер- шинах пути у. Определение.
гХислом вращения слиГ плоского бинарного дерева Г называется максимум чисел вращения ни[а, 5), взятый по всевозможным упорядоченным парам ребер Г. Отметим, что если бинарное дерево Г является локально минимальным, то определенное так число вращения Фк Г совпадает с числом вращения дерева Г как линейного дерева, Следствие 3 Пусть Г произвольное лака ьно минимальное бинарное дерево, затягиваюи1ее фиксированное конечное множество ЛХ точек плоскости.
Тогда сиГ < 12(н(ЛХ) — 1) + 5, где через ФчгГ обозначено число вращения Г как плоского бинарного дерева. Замечание. В случае яс(ЛХ) = 1, т.е. если множество ЛХ лежит на границе своей выпукчой оболочки, из следствия 3 вытекает оценка си Г < 5. Автором и А. А. Тужилиным [42], [43], [45] получено полное описание плоских бинарных деревьев с не превосходящим 5 числом вращения и доказана обратная теорема: любое плоское бинарное дерево Г, си Г < 5, эквивалентно локально минимальному дереву с границей ЛХ, м[ЛХ) = 1, см. выше предложение В.10. Для н(ЛХ) ) 1 аналогичный результат не известен.
Перейдем к случаю взвешенных бинарных деревьев. Из следствия 1 вытекает, что веса каждых трех ребер вложенного взвешенного минимального бинарного дерева,инцидснтных одной и той же его вершине степени 3, удовлетворяют правилу ьчреугольникть т.е. сумма любых двух из них строго больше чем третий это необходимое условие существования такого вложенного взвешенного минимального бинарного дерева. Поэтому, говоря о взвешенных бинарных деревьях, мы в дальнейшем всегда будем предполагать, что веса каждой тройки ребер бинарного дерева, иниадснтныг одной и той же его вершине стееасни 3, удовлетворяют правилу треугольника. Рассмотрим произвольную вершину Р степени 3 из Г, и пусть е„ 1 = 1, 2, 3, ребра соти Г, инцидснтныс Р, а ш; вес ребра еь Рассмотрим на плоскости треугольник, длины сторон которого равны шо 1 = 1, 2, 3, и обозначим через еи угол этого треугольника, противолежащии стороне длины ьл Упорядоченной паре (еб е ), 1 ф Х, сопоставим число хая(ЗХк), где Й третье "дополнительное" значение индекса, т.е.
11,1,к) = 11,2,3). 4. Краткое содержание диссертации. Знак "плюс" выбирается., если при движении по пути е;е. через вершину Р мы сворачиваем налево, а знак 'минус" - — в противном случае. Это чиссю назовем твистингом от ребра е; к ребру ег Рассмотрим теперь произвольную пару (а, Ь) ребер дерева Г, и пусть у(а., Ь) --. единственный ориентированный путь в у, начинающийся на а и заканчивающийся на Ь. Пусть а = ем..,,е„= Ь вЂ” последовательные ребра пути "Да, Ь). Числом вращения ск(а, Ь) уиорядоченной пары (а, Ь) ребер из Г назовем сумму твистингов последовательных пар ребер (е,, е,ес)., ю,' = 1,..., и — 1. Определение. Максимум чисел вращония ьис(а, Ь), взятый по всевозможным упорядоченным паралс ребер дерева Г, называется числом вращения Ьк Г взвешенного бинарного дереви Г. Отметим, что если плоское взвешенное бинарное дерево является минимальным, то его число вращения как плоского взвешенного бинарного дерева совпадает с его числом вращения как линейного дерева.
Следствие 4 ХХусть Г минимальное взвешенное бинарное дерево с полоокительными весими, затлгиваюсиее фиксированное канатное мнозкество ЛХ точек плоскости. Тогда ск Г ( 12(м(ЛХ) — 1) + 6, где через скГ обозначено число вращения Г как плоского взвешенного бинарного дерева. В диссертации также получено обобщение алгоритма Мелзака ~64) для случая взвешенных бинарных деревьев.
Пусть С -. произвольное топологическое взвешенное бинарное дерево с положительными весами, дС некоторая граница графа С, содержащая все его вершины степени 1, н пусть Д: дС -~ Кг произвольное граничное отображение, и 1У(дС) = ХеХ. Обобщенный алгоритм Мелзака позволяет вли построить вложенную минимальную взвешенная сеть Г: С -+ Б'.г с границей сд, или установить, что такой сети не существует.
Кроме того, найден аналог линий Симпсона., и доказано, что взвешенная длина каждой линии Симпсона равна взвешенной длине минилсального бинарного дерева. Замечание. Результаты следствий 3 и 4 были первоначально получены автором боз использования теоремы 4, исходя только из тсорслсы о локальной структуре таких сетей, разработанного автором обобщения алгоритма Мелзака для взвешенных минимальных бинарных деревьев, и геометрических построений, аналогичных доказательству теоремы 4. Введение. 50 В пятой главе изучаются семейства взаимно параллельных линейных сетей в евклидовом пространстве К', у которых предполагаются фиксированными топология и граница.
Полученныо результаты используются для описания множества всех локально минимальных (взвешенньсх) сетей в К" с фиксированной топологией и границей. Сеть Г: С -+ К" называется линейной, если все ее ребра ---прямолинейные отрезки. Пусть Г и Г' — две погруженных линейных сети одного и того жс типа С. Ориентирусм граф С произвольным образом.
Это позволит нам рассматривать образы ребер этого графа при отображениях Г и Г' как векторы в пространстве К". Мы скажем, что сети Г и Г' параллельны, если для каждого ребра е из С векторы Г(е) и Г'(е) сонаправлены. Пусть задана погруженная линейная сеть Г; С вЂ” ~ К" типа С с некоторой фиксированной границей д. Наша цель описать множество ~~С, „в)г всех параллельных Г линейных сетей того же типа С и с той же границей д, Разрежем граф С по всем граничным вершинам степени больше 1 и определим границу калсдой связнои компоненты С; как множество всех тех ее вершин степени 1, которые порождены вершинами из дС.
Полученное разбиение графа С назовем разбиением на невырвжйенные компоненты Сь Чтобы описать множество [С, Дг, мы построим следующую линейную систему уравнений. Фиксируем в пространстве К" некоторые евклидовы координаты. Фиксируем некоторую ориентацию сети Г, и будем называть эту ориентацию исходной. Если е произвольное ребро сети Г, ориентированное одним из двух возможных способов, то положим е(е) равным 1, если зта ориентация ребра е совпадает с исходной. В противном случае, положим е(е) = — 1. Пусть и(е) координаты единичного вектора направления ребра е сети Г в исходной ориентации. Разобьем граф С на невырожденные компоненты, и пусть Г; = Г~о, --. соответствующие компоненты сети Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
