Геометрические свойства локально минимальных сетей (1097521), страница 41
Текст из файла (страница 41)
Теперь, складывая первые два равенства и используя сделанные выше оценки, получаем требуемое, Следствие доказано. 4.2 Геометрия плоских локально минималь- ных бинарных деревьев В данном разделе мы изучим устройство локально минимальных не- вырожденных деревьев Штейнера или бинарных деревьев. Напомним, Глава 4. Плоские локально минимальные деревья.
190 что невырожденное дерево Штейнера --- это след плоской вложенной сети, параметризованной некоторым бинарным деревом. Мы будем изучать невырожденные деревья Штсинора с точностью до планарной эквивалентности. Для краткости, будем называть бинарные деревья 2-деревьями, а локально минимальные деревья просто минимальными деревьями. Пусть Г некоторое плоское 2-дерево, затягивающее конечное множество М точек плоскости. Из общих результатов о локальном устройстве (см, главу 3), вытекает, что сеть Г минимальна с границей Л1, если и только если все ребра из Г прямолинейные отрезки. стыкун>шиеся в вершинах степени три под углами в 120', и все вершины степени 1 из Г принадлежат множеству М. Заметим, что если Р е ЛХ некоторая вершина степени 3 сети Г, то Г также является минимальным 2-деревом с границей Л1 '1 (Р).
Поэтому можно предполагать без ограничения общности, что мы в дальнейшем и будем делать, что граница минимального 2-дерева состоит из всех его вершин степени 1 и только из них, 4.2.1 'Число вращения плоского бинарного дерева Рассмотрим произвольное плоское 2-дерево Г, выберем некоторую пару (а, Л) его ребер, и пусть у единственный путь в Г, соединяющий эти ребра.
Ориентируем путь у от а к Ь, и пусть Р --. произвольная вершина степени 3 дерева Г, лежащая внутри сб т.е. не совпадающая ни с одной из его концевых вершин. Выберем хорошую круговую окрестность 11 вершины Р, т.е., напомним, такую окрестность 11 С К~ точки Р, что ее пересечение с деревом Г представляет собой звезду с центром в Р и вершинами степени 1, лежащими на окружности дП, Пересечение дб Г> Г состоит из трех точек. которые мы обозначим через Ао 1 = 1, 2, 3. Пусть а> — первое, и аз последнее ребро из у.
инцидентное Р, и пусть А, ч а„1 = 1, 2. Рассмотрим дугу б окружности д11, лежащую между А> и Аз и содержащую Аз. Если движение по дуге б от А> к Аз происходит по часовой стрелке, то будем говорить, что мы поворачиваем направо в точке Р, и припишем Р число — 1. В противном случае, скажем,. что мы поворачиваем налево в точке Р и припишем Р чисю +1. Число, приписанное вершине Р, называется тпвистингом вершины Р»утаи у.
'1ислом вращени 1>н(а,б) унорядоченнои г>ары (а,)>) ребер 2-дерева Г называется сумма твистингов во всех внутренних вершинах пути ",~. По определению, положим 1>ч(а,а) = О. Определение. >1ислом вращения 1иГ бинарного дерева Г называется 4.2. Бинарные деревья. максимум чисел вращения Ф»е(а, 6), взятый по всевозможным упорядо- ченным парам ребер Г. Легко проворить, что число вращения обладает следующими свойствами. Утверждение 4.2 Пусть Г произвольное плоское бинарное дерево. ° »»»»(а,6) = — »щ(Ь,а) для любых ребер а и Ь дерева Г (косая симмешрия); ° 1ж(а,Ь)+Ьж16, с) = Ы(а, с) для любых ребер а, Ь и с из Г лежащих на одном путин в дереве Г (адди»пивносп»ь вдоль путей); ° если 1»еГ = Съ (а,Ь), то ребра а и 6 иниидентны вершинам шаеп,ени 1.
Доказательство. Первые два пункта очевидны. Для доказательства последнего у.тверждения, предположим противное, и пусть., для определенности, ребро Ь не инцидентно вершине степени 1, Тогда оно инцидентно вершинам степени 3. Обозначим через В последнюю вершину пути у(а, 6), а через с' и со ребра из Г, инцидентные В и не лежащие в 1(а,Ь). Рассмотрим пути»' и у", полученные из у добавлением к пути у ребра с'и со соответственно. Тогда,в силу второго пункта, Си(а, с') = гл(а, 6) + Фи (Ь,с'), а»»е(а,со) = Ск1а, Ь) + Ф»е(Ь,со). Кроме того, ясно что»»е(Ь, с') = — »е»(6, со), Поэтол»у или»ъ(а, с'), или 1и»(а,со) больше чем Сж(а,Ь), что противоречит выбору ребер а и Ь. Доказательство закончено.
Непосредственно из определения числа, врашения вытекает следующий факт. Утверждение 4.3 Если Гв и Г» - два планарно эквивалент»»ых бинарных дерева, »по сжГо — — 1ч»Г». Доказательство. Действительно, планарная эквивалентность сетей Штейнера Гв и Г» означает, что существует непрерывная деформация Г», 1 Е»»0,1), сети Го в сеть Г» в классе вложенных сетей. Пусть уо произвольный путь в Го. Деформация Г» порождает деформацию т» кУсочно глаДкой вложенной кРивой Тв в классе вложенных кРивых.
Ясно, что деформация Г» может быть продолжена на малые хорошие окрестности всех вершин степени три сетей Г», поэтому, очевидно, твистинги вершин пути ",» не зависят от параметра деформации 1., что и означает постоянность числа вращения для любой пары ребер из Г». Доказательство закончено. Глава 4. Плоские локально минимальные деревья. Число вращения между ребрами минимального бинарного дерева имеет прозрачный геометрический смысл. Утверждение 4.4 Пугть Г минчмильнов бинарное дерево, и а и й произвольные его ребра.
Обозначим через с единственный 'папи в дереве, начинающийся но, а и заканчивающийся на о. Тогда число вращения ск(а, о) между а и д равно кручению сну ориентированной от а к 6 ломаной у. Доказательство. Это немедленно вытекает из определений и того факта, что ребра минимального 2-дерева стыкуются под углами в 120', 4.2.2 Свойства минимальных 2-деревьев В настоящем пункте мы щзиведем несколько важных для дальнейшего свойств плоских минимальных 2-деревьев.
Пусть Г -- пюское минимальное 2-дерево с границей Лй, и пусть 0 -- некоторый ориентированный путь в нем. Определение. Путь у называется сетевой геодезической на Г, если твистинги любых двух его соседних внутренних вершин имеют противоположные знаки. Пусть Р произвольная вершина минимального 2-дсрева Г, и е некоторое ребро из Г, инцидентное Р. Рассмотрим максимальные сетевые геодезические, начинающиеся в Р и содержащие е (таких существует не более чем две). 1саждая такая сетевая геодезическая называется свпсевслм геодезическим лучом с началом в Р, выпущенным в направлении е. Ясно, что концевая вершина сетевого геодезического луча, отличная от Р, лвлястся граничной вершиной дерева Г. Рассмотриьс на плоскости угол о величиной 120' с вершиной в точке Р и такой, что его биссектриса содержит ребро е.
Внутренность угла сс, к которой добавлена точка Р, называется хараксперистическим клином пары (Р., е) и обозначается через ЪКдй(Р, е). Следующее предложение немедленно следу.ет из определений. Предложение 4.5 Пуспсь Р вершина минимального 2-дерева Г, и е иниидентное ей ребро. Тогда каждый сетевой геодезический луч, вьтущгнный из Р в направлении е, содержится в характеристическом клине Ъчс!~(Р, е). В частности, каждый характеристический клин содержит граничную вершину дерева Г.
Следующее предложение также будет нам полезно. 4.2. Бинарные деревья. 193 Предложение 4.6 Пусть Г --. минимальное 2-дерево, затягивающее конечное множество М точек плоскости, 1 -- некоторый путь в Г, и и некоторый выпуклый,многоугольник, ограниченный ломаной Н, находящейсл с Л в общем положении.. Рассмотрим каноническое разбиение Л = 0Ц ломаной Л относшаельно Н, и пусть Ь, некоторая щапочкщ образованная Т по отношению к Н, Тогда, если соответствующая Н-область Н(Е,) содержит точку пути Ь, то Н(й;) содержит также и точку из граничного множества М.
Доказательство. Пусть некоторая точка Р б Х, принадлежит Н(рм). Если Р не является вершиной сети Г, то рассмотрим ребро е из Г, которому она принадлежит. Так как о выпуклый многоутольник, и Р ф и, одна из вершин сети Г, инцидентных е, так же не лежит в о, По ребро е не может пересекать Ь;, так как иначе дерево Г содержало бы цикл, поэтому эта вершина лежит в Н(й,). Таким образом, не ограничивая общности, мы сразу можем предполагать, что Р вершина сети Г. Если Р й М, то предложение имеет место, Пусть теперь Р -.- некоторая внутренняя вершина дерева Г, т.е.
его точка Штейнера, и е,, 1 = 1, 2, 3 ребра дерева Г, инцидентные Р. Рассмотрим характеристические клинья, порожденные Р. В силу выпуклости многоугольника о, существует две возможности: или один из кяиньев не пересекает многоугольник о, или все клинья пересекают о, но один из ограничива|оших их лучей не пересекает о (а два других -- пересекают) . Рассмотрим первыи случай, и пусть, скажем, клин %с)ф(Р,е1) не пересекает и. 'Тогда, в силу предложения 4.5, сетевые геодезические лучи, выпущенные из Р в направлении еы содержатся в %'Ай(Р,еь) и, поэтому, также не пересекают о. Поскольку эти лучи начинаются внутри области Н(Т,), граница которой состоит из Ь, и части границы многоугольника, и эти лучи не пересекают о и не могут пересекать | о они заканчиваются внутри области Н(1;), ко сорвя поэтому содержит граничные точки. В первом случае предложение доказано.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
