Геометрические свойства локально минимальных сетей (1097521), страница 45
Текст из файла (страница 45)
Эта оценка является точной в следуюиьем смысле: для любого и и 1 < я < [[п+ 2)/3), существует минимальное 2-дерево Г с границей ЛХ, состоящей иэ и точек и имеющей к уровней выпуклости, причем ° если й < ~[и + 5)/12, то Хля Г = 12[6 — Ц + 5, ° если же [п+ 5)/12 < я < [[п + 2)/3), то 1к Г = и — 2. Эта теорема обобщает следующий реву.льтат автора и А. А. Тужилин [42, 43, 45, 46) относительно числа вращения минимальных 2- деревьев с выпуклой границей [т.е. й = Ц. Следствие 4.7 Число враи1ения плоского минимального бинарного де- рева с выпуклой границей не превосходит 5. Замечание. В случае выпуклых границ автором и А.
А, Тужияиным была доказана и обратная теорема [42, 43, 45, 46), а именно: если число вращения плоского 2-дерева Г не превосходит 5, то существует планарно эквивалентное ему минимальное 2-дерсво с выпуклой границей. Конструктивное доказательство этого факта, полученное в [43, 45, 46), существенно опирается на полное описание всех плоских бинарных деревьев с числом вращения не превосходяшиле 5, см.
там жс, а также Введение. Оказалось, что л1ножество всех таких бинарных деревьев 4.2. Бинарные деревья. 207 допускает конечное, в некотором смысле, описание на языке триангуляций специального вида. Уже в случае бинарных деревьев с числом вращения 6 такой конечности нет, что существенно усложняет ситуацию. К сожалению, автору неизвестно. справедлива ли аналогичная обратная теорема в рассматриваемом здесь общем случае. Замечание. Ниже мы докажем общую теорему о связи числа уровней выпуклости геометрической границы плоского линейного дерева и числа вращения этого дерева, см. теорему 6. Предложение 4,10 может быть получено как следствие иэ этои теоремы.
Однако мы приведем здесь независимое доказательство предложения 4.10 из ~38~, чтобы разработать необходимую для доказательства теоремы 6 технику. Пусть а и б некоторые ребра из Г, такие что ви Г = 1и(а, Л). Напомним, что в этом случае ребра а и Ь .-- граничные. Обозначим через Ь единственный путь в 1, соединяющий а и Л, и ориентирусм В от а к Л. Тогда лп В = сит Г.
Обозначим через А и В концевые вершины Г, инцидентные а и Л соответственно. Ясно, что обе точки А и В принадлежат ЛХ. Пусть М' — 1-ый уровень выпуклости множества М. Предположим, что А Е М", В Е МЯ, и пусть р < а. Обозначим через а' выпуклую оболочку множества Л4', и через И'т границу множества ат: дал = И'.
Для краткости положим а = а~, и И' = И'т Пусть У = и' лт а' ~. Ксли множество аьы не пусто, то множество У два-связно (т.е, гомотопно окружности), и ограничено И' и Ит'+~, причем И" С У, а И""' О У = 0. В силу предложения 4.9 можно не ограничивая общности предполагать, что сеть Г находится в общем положении. Всюду ниже мы предполагаем, что это предположение имеет место. Мы отдельно рассмотриът две возможности: или р = 9, или р < д.
Начнем с первого случая. Случай р = 9 Пусть сначала р = д = 1. Хорошо известно, см, например [30, 46~, что минимальное дерево всегда лежит в выпуклой оболочке своего граничного множества (в следующем разделе мы докажем более общее утверждение, см. предложение 4.20). Поэтому путь В целиком лежит внутри выпуклого многоугольника а. Мы находимся в условиях следствия 4.4, где в качестве замкнутой ломаной выступает граница Иг многоугольника а.
Обозначив через Ит' и И™ компоненты, на которые разбивают Глава 4. Плоские локально минимальные деревья. 208 точки А и В ломаную И',получим ~ 1п Т ~ < 3~ шс1(А, И") + шс1(ь, И'о) ~ + 6 = 6, так как шс1(ь, И") = — пп1(Т., И™), поскольку ломаная В образует ровно одну П область по отношению к каждой из ломаных И" и И™, причем знаки этих областей, очевидно противоположны. Остаюсь заметить, что. в силу утверждения 4.4, 1и(а, Ь) = гп1,, и, кроме того, 1к(а, Ь) целое число, поэтому неравенства 1ъ(а, Ь) < 6 и 1ъ(а, Ь) < 5 равносильны.
Итак, для случая р = у = 1 предложение 4.10 доказано. Полученное утверждение понадобится нам так же в виде следующей леммы. Лемма 4.13 Пусть И' замкнутая ломаная, ограничивающая выпуклый многоугольник и, и пусть В ломаная, соединяющая точки А Е И' и В Е И', лежащая в и и находящаяся с И' в общем положении. Обозначим через а и Ь концевые ребра В, инцидентныс А и В соответственно.
Тогда ~1пб~ < 6. В частности, если В путь в минимальном 2-дереве, то )1ж(а, Ь)) = ! СпТ! < 5. Предположим теперь что р > 2. Обозначим через И'~ и И~г те части ломаной 1Г~, на которые ее разбивают точки А и В. Рассмотрим каноническое разбиение В = ОЕ, ломаной В относительно И'". Пусть Ял и 'Нв множества, состоящие из всех р-шапочск, образованных Т,, таких что замыкание их оснований содержит точки А и В соответственно. Поскольку, очевидно, основания шапочек,принадлежащих 'Нл 1соответственно,'Нв) упорядочены по включению, тоже самое имеет место и для соответствующих Н-областей.
Тогда из следствия 4.6 вытекает следующий результат. Предложение 4.11 Каждое из множеств 'Нл и 'Нв состоит не бо- лее чем из р — 1 элемента. Отметим, что все осгальные р.шапочки, порожденные В (т.с. шапочки, замыкания оснований которых не содержат ни А, ни В), явллются пустыми элементами относительно И~~ или И'~. Отметим также, что каждый внутренний не пустой элемент, образованный В относительно И'~ или И'~, содержит, как подмножество, некоторую шапочку из 'Н = Ял О Яв, а разные такие непустыс элементы соотвстствуют разным шапочкам из Я. Ужо отсюда можно было бы получить оценку на количество А- и В-элементов, образованных ломаной Е по отношению к И;.,и, следовательно,на индексы шс1(Ь, И',), однако эта оценка оказывается слишком грубой для доказательства теоремы. Поэтому необходимы немного более тонкие рассуждения.
4.2. Бинарные деревья. 209 Рассмотрим произвольную шапочку, соответствующую произвольной пустой области Й, образованной В по отношению к И;. Мы назовем такую шапочку пустой и»апочкой. Так же как и выше, в доказательстве предложения 4.3, можно найти строго пустуя> область Й', содержащуюся в Й..Ясно, что Й' также является пустой шапочкой по отношению к Игь Применяя элементарную деформацию к Й', перестроим В так, чтобы полученная ломаная образовывала одной шапочкой и одной пустой областью меньше по отношению к И',.
Ясно, что при такой элементарной деформации не меняются ни направления концевых ребер пути Те ни шапочки, принадлежащие 'Н (последнее имеет место так как элементы разбиения смежные с элементом Ь', соответствующим Й', лежат внутри И'" и, поэтому, не принадлежат р-шапочкам из 'Н). Повторяя этот процесс до тех пор, пока все пустые шапочки не будут у.ничтожены, и используя тот факт, что кручение ломаной В не меняется при элементарных деформациях, получим с»едующее предложение.
Предложение 4.12 Суи»ествует деформация ломаной Е, неподвижная на всех непус»пых шапочках и на граничных ребрах ломаной Ь, »паке»я опо полученная в результип»е ломиная не обризует пустых ишт»очек. Кручение ломаной Т также не меняется при этой деформации.
Таким образом, можно предполагать, что Е не образует пустых шапочек. Определим теперь числа и,, »' = 1,2, так. Положим и; равным количсству нс содержащих шапочек из 'Н концевых областей. образованных ломаной В по отношению к И;. Очевидно, и, < 2 по определению. Далее, напомним, что ломаная В ориентирована от А к В. Обозначим через пу общее количество не содержащих шапочек из 'Н первых элементов разбиений В относитечьно как И'», так и И'».
Аналогично, через п» обозначим количество не содержащих шапочек из 'Н последних, не совпадающих с первыми. элементов этих разбиений. Очевидно, пу < 2, и» < 2., и и» + пэ = пу + и». Оказывается, если ломаная Ь не образует пустых шапочек, то имеет место следующая более сильная оценка. Предложение 4.13 Пусть ломаная Ь не обризуеп» пустых шапочек, по отношению к И»е. Тогда, в сделанных выше обозначениях, имееп» ,место следующее неравенство: и» +пг = ну+и» < 2. Доказательство.
В тривиальнол» случае, когда лоь»аная В пересекает ломаную И'" лишь в точках А и В, имеем очевидно две возможности: Глава 4. Плоские локально минимальные деревья. 210 или ломаная Х целиком лежит в о'", и тогда н1 — — па = 1., пу = 2, п( = 0 (для каждой И'; имеется всего одна (первая) концевая область, не содержащая шапочку), поэтому пч + нз = 2; или ломаная Г.
попиком лежит вне о", и тогда и, = и = пу = и( = 0 (для каждой И; имеется всего одна концевая область, содержащая шапочку), поэтому н1 + па = О. Предположим теперь, что имеется хотя бы одна точка пересечения ломаных В и Иг", отличная от А и В. Рассмотрим первый элемент Ь1 канонического разбиения ломаной В относительно ломаной И'". Предположим сначала, что В1 лежит вне многоугольника ог. В этом случае, очевидно, первые элементы разбиения В по отношению к ломаным И;. содержат шапочки из 'Н, поэтому каждое из чисел н„( = 1,2, нс превосходит единицы, откуда а, + пз < 2. 1~роме того, очевидно, в этом случае (и = ().
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
