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