Геометрические свойства локально минимальных сетей (1097521), страница 46
Текст из файла (страница 46)
Пусть теперь В, лежит внутри Ф', и предположим, для определенности, что конец ломаной Е~ принадлежит И'1 (напомним, что ломаная Ь, и значит все элементы канонического разбиения, ориентированы от А к В). Тогда первый концовой элемент разбиения В по отношению к И'1 не содержит шапочки. Однако, так как ломаная Л находится в общем положении с И', следующий элемент Еа канонического разбиения ломаной В относительно И'г лежит вне ао, поэтому образует шапочку, которая по нашему предположению не пустая.
Наконец, ясно что первый элемент канонического разбиения ломаной В по отношению к РИз в этом случае содержит Ь1 Ойю поэтому он содержит непустую шапочку, т.е. шапочку из Я, откуда пу < 1. Таким образом. вне зависимости от расположения первого элемента ломаной Ь, имеет место неравенство пу < 1. Аналогично можно показать, что и( < 1, откуда окончательно получаем: пу + и( < 2. Предложение доказано. Обозначим через н,'( количество не содержащих шапочек из 'Н концевых А-элементов разбиения ломаной Ь по отношению к И'„и, аналогично, через п~ количество не содержащих шапочек из 'Н концевых В-элементов разбиения ломаной В по отношению к И~ь Очевидно, пл1 + п~' = н„и тс~ + н~~' = па, поэтому имеет место следующее утверждение.
Следствие 4.8 В сделанных выше обозначениях, н~ +на +и( +па <'2. Замечание. Из определений немедленно вытекает, что количество А- элементов, образованных ломаной В по отношению к ломаной И'и не 4.2. Бинарные деревья. 211 превосходит п~ + ф('йл), а количество В-элементов, образованных ломаной Ь по отношению к ломаной Иь не пРевосходит пи+ ф(24н), где через $1Х) обозначается количество элементов во множестве Х. Рассмотрим тспсрь канонические разбисния ломаной Л по отношению к И'ь и воспользуемся следствием 4,3 для опенки индекса, Имеются следующие возможности. (1.) Разбиение ломаной В относительно И; содержит К-элемент.
Этот Е-элемент, очевидно, содержит как шапочку из 'Нл так и из 'Нн (возможно, одну и ту же). Тогда, в силу предложения 4.11, общее количество А- и В-элементов не превосходит 2(р — 2) + пь откуда имеем; ~ шо(ь', 11",) ~ < 2(р — 2) + и; + 1 = 2р — 3 + и,. (2.) Разбиение ломаной Л относительно И', не содержит Е-элемента. Тогда как количество А-областей, так и количество В-областей, не превосходит (р — 1) + шах(п~, пн). Здесь возможно два случая. (2а.) После редукции ломаной В по отношению к И; каноническое разбиение родуцированной ломаной снова нс содержит Е-элемента. Тогда, в силу следствия 4.3, имеем: ~ шс1(Л, Ис)~ < р — 1+ шах(п~, пп) < 2р — 3+ шах(н~, п~), прир>2.
(2б.) После редукции ломаной Ь по отношению к И;; каноническое разбиение редуцированной ломаной содержит Г-элемент. Тогда, в силу следствия 4.3, имеем; ~ пн1(Ь, И', ) ~ < р — 1 + а ~' + р — 1 + пи — 1 < 2р — 3 + и,. Оценим сумму ~ 1ш1(Л, И'~) + 1пс1(В, И~~) ~, для чего икьким соответствующие оценки. Напомним, что, в сашу предложения 4.13, па+не < 2. Далее. очевидно, шах( ~,нв) + шах(пзз, п~) < п~ + пз < 2. Наконец, точно так же и; + шах(п .
и, ) < и, + пз < '2. Итак, во всех случаях л в получаем,что ~ шо(Ь, И~) + шс1(Е,Иэ)~ < 2(2р — 3) + 2 = 41р — 1). Теперь, воспользовавшись следствием 4.4, имеем; )спВ) < 3 )1пс1(Е,И'~) +пнЦЛ,И )(+6 < 3 4(р — 1) +6 = 12(р — 1) + 6, или ~ сп Ь~ < 121р — 1) + 5, так как число вращения минимального 2- дерева целое.
Предложение 4.10 доказано в рассматриваемом случае р=ч Глава 4. Плоские локально минимальные деревья. 212 Случай р < у Итак, пусть теперь р < ф Разобьем ломаную Е следующим образом. Первый фрагмент Е», это часть ломаной Ь между точкой А = А» и такой первой точкой В» Е Е, что вся оставшаяся часть ломаной Е между В» и В лежит внутри ог. Другими словами, Л» это минимальная связная часть ломаной Х, содержащая А и такая, что Е», Ь» целиком содержится в и". Отметим, что фрагмент Е» может быть пустым. Второй фрагмент Ьд ломаной Ь это часть ломаной Е между точкой .4з = В» и такой первой точкои Вд, что вся оставшаяся часть ломаной Л, начиная с Вд лежит в о"т .
Другими словами, Вз это т» первая точка на Л,такая что Е »,(Ь» О Л ) С огд'. Далее, длл » > 1 и такого что р + » — 1 < »1, т.е. д < у — р + 1, определим фрагмент Ь» ломаной Е как часть Х между Ад = Вд » и такой первой точкой В,,что оставшаяся часть ломаной Л от В, до В содержится в о"+» Последнии фрагмент разбиения Ьд ртд совпадает с оставшейся частью ломаной Л, если она нс пуста.
Итак. мы построили разбиение ломаной Е на участки Е», Ез, ..., Ьд р д, такие что каждыи фрагмент Ь» соединяет точки А, и В„где А», В» Е Иг", А, = В, » Е И'"т' д,и В, Е И'"д' » при 1 < » < у — р+ 1, причем Е» с о"т' д при 1 <» <»1 — р+ 1. Кроме того, Ад „лд и Вд пРинадлежат И", и Ьд тд С од. Обозначим чеРез а, и Ьд концевые ребра ломаной Е», инцидентныс точкам А; и Вд соответственно.
Кручение ломаной Ь» можно опенить с помощью результатов про дыдущего пункта, а именно, ~ »и Ь» ~ < 12(р — 1) + 5. Далее, мы оненим кручение каждого из Е„2 < д < у — р + 1, доказав следующее предложение. Предложение 4.14 В сделоннь»х оьпие обозначениях, если 2 <» < у — р+1, то ~»»»Ь,~ <9. Наконец, мы докажем следующий результат. Предложение 4.15 Если участок Ьд тд не пуст, пю ~ Ф»» Ед р,. » + »п Ед р) з~ 12.
Ясно, что предложения 4.14 и 4.15 завершают доказательство предложения 4.10. Действительно, так как ломаная Ь находится в общем положении по отношению ко всем многоугольникам И", для кручения 4.2. Бинарные деревья. 213 ломаной Х получаем: ч г Фпй = СП51+ ~1лйп+1п7.„„,,1+ тпТд откуда 1п 5 < 12(р — 1) + 5 + 9(д — р — 1) + 12 = = 99 + Зр — 4 < 9д + 3(4 — 1) — 4 = 12д — 7 = 12(д — 1) + 5,. что и требовалось. Перейдем теперь к доказательству предложений 4.
14 и 4.15. Доказательство предложения 4.14. Прежде всего отметим, что если Ь; состоит меньше чем из 4 ребер, то предложение 4.14, очевидно, имеет место. Итак, предположим. что Е, состоит по крайней мере из 4 ребер. Ориентируем В, от А, к В,, и обозначим три последних ребра ломаной Т„, через Ь", Ь' и Ь,, соответственно. Вершину, инцидентную ребрам Ь" и Ь' обозначим через В". а вершину инцидентную Ь' и Ь, —.— через В'. Кроме того, обозначим через с" и с' ребра сети Г, инцидентные соответственно вершинам В" и В' и не лежащие на пути Т,, см. рис.
4.9. Напомним, что из каждой вершины сети в направлении каждого инцидентного ей ребра выходит не более двух различных сетевых геодезических лучей. Пусть 71 и бв два таких сетовых геодезических луча, выходящих из точки В' в направлении с', которые, вообще говоря, могут совпадать. Рассмотрим первую точку Сс пересечения геодезического луча у., у = 1, 2, с многоугольннками Йх'ч Ясно, что поскольку точка В' лежит в Вгч ' ', точка Сс лежит или на Ихгт' з, или на Ихге' 1. Если ~с лежит на Их~, будем говорить, что геодезический луч у приходит сначала на И~~.
Существует две возможности: или хотя бы один из геодезических лучей, скажем 7ы приходит сначала на И'гт' -', или оба луча 71 и Тз приходят сначала на И'"т' Рассмотрим первый случай, см. рис. 4.9. Обозначим снова через 71 отрезок сетевого геодезического луча 71 между точками В' и С,'.
Ориентируем 71 от В' к С1, и пусть с| -- последнее ребро отрезка уг Обозначим через 7, 'путь в Г, соединяющий точки А; и С~. Эта ломаная линия лежит внутри и"т' з, находится в общем положении с И'и+' з = дн"+' з и соединяет две точки, лежащие на И'и+' з.
Таким образом, в силу леммы 4.13, ~1ъ(абс1)~ < 5, В силу аддитивности числа вращения вдоль пути, имеем: тн(аб с' ) = 1н(а„д)+тн(Ь', с )+1н(с', с',) = 1н(а„Ьь) +тн(Ь', с)-~тп(71). Глава 4. Плоские локально минимальные деревья. 214 Рис. 4,9: Средний элемент разбиения пути В. Но, так как у~ --- отрезок сетевой геодезической, ~ Сп ус ~ < 1.
Итак, (СжСап 6 )( = )СжСа„с~) — СЯСЬ',с) — СпС7с)( < 5+ 1+ 1 = 7, и., поэтомУ, )си(поьс)! = )сне;! < 8. В пеРвом слУчае пРедложение доказано. Рассмотрим второй случай, а именно, пусть оба геодезических луча 'у~ и уз приходят сначала на И" Сс с, см. рис. 4.9. Обозначим через Оч вершину ребра с', отличную от В'. Легко видеть, что или само ребро с', или его продолжение приходит сначала на И'е " с, причем приходит трансверсально. Таким образом, лучи, выпущенные из точки В' вдоль ребер Ь, и с' и образующие угол величиной в 120', который мы обозначим через сп приходят сначала на И'"+' '. Отсюда следует, что характеристический клин 1тЧ8СВ',6') не пересекает пасс с, поскольку он ограничен лучами, противонаправленными лучам, образующим утол а.
Поэтому обе сетевых геодезических луча, выпущенных из В' в направлении Ь' приходят сначала на Иге'сс -. Ясно, что один из этих геодезических лучей содержит геодезический луч выпущенный из точки В" в направлении с", Ваяв этот последний геодезический луч в качестве "П и повторив рассуждения, примененные в первом случае, мы получим оценку ~ СжСа„Ьс) ~ = ~ Сп Е;~ ~< 9, так как между ребрами Ь" и Ьс расположено две вершины, а не одна как в первом случае.
Предложение 4.14 доказано. Итак, если последний фрагмент В „зз разбиения пути В пуст, то теорема 4.10 вытекает из только что доказанного предложения 4.14, Если же он нс пуст, нам потребуется с помощью чуть более тонких рассуждений получить оценку на кручение сразу двух последних фраг- 4.2. Бинарные деревья. 215 ментов разбиения. Эта оценка и приведена в предложении 4.15, к до- казательству которого мы переходим. Доказательство предложения 4.15. Как и в доказательстве предложения 4.14 предположим, что Вд .ре1 состоит по крайней мере из 4 звеньев.
Мы сохраним обозначения из доказательства предложения 4.14, положив д = д — р+ 1. Однако теперь мы рассмотрим три возможности; (1) оба геодезических луча уу, у = 1, 2, приходят сначала на И' д 1„(2) один из них приходит сначала на И'д 1, а второй на 1Ид, и, наконец, (3) оба геодезических луча у, д = 1, 2, приходят сна'чала на И д. Как и выше, обозначив через ч,' путь в Г соединяющий точки Ад и Сс, получим следующее равенство: дн(ад реы с' ) = ск(а ре ы Ь ) + 1ж(Ь, с ) + Фк(с', с' ) — сед(ад — р 1 Ьд) + Ск(ЬБ сд) + Сп у Рассмотрим первый случай.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
