Теория Морса минимальных сетей (1105006), страница 22
Текст из файла (страница 22)
3.9:Вариант ) подходит, и при этом тройке (1, 2, 3) будет инцидентно двамощных расщепления из 2 (Γ0 ). Итак, в любом случае # 2 (Γ0 ) ≥ 4.Согласно предложению 3.5, если отщеплений ровно 5, т.е. срединих ровно 3 отщепления троек, а тогда из леммы 3.12 следует, что# 2 (Γ0 ) ≥ 3 ≥ 2. 2) У сети Γ0 нет вырожденных граничных ребер.Единственную подвижную вершину сети Γ0 мы обозначим через .Так как сеть Γ0 является минимальной параметрической сетью, то изкритерия 3.3 вытекает, что сумма единичных направляющих вектороввыходящих из вершины ребер 1 , 2 , 3 , 4 , 5 должна бытьравна 0.Подсчитаем количество элементарных геометрических расщепленийсети Γ0 .
Для этого необходимо, согласно критерию 3.3, чтобы суммаединичных направляющих векторов граничных ребер, инцидентных одной подвижной вершине элементарного геометрического расщепленияΓ ∈ 1 (Γ0 ), по модулю была строго больше 1. Мы будем говорить,что такая совокупность граничных ребер отщепляется. Заметим, что, вотличие от случая 1), для каждого элементарного геометрического расщепления Γ ∈ 1 (Γ0 ), в силу равенства нулю суммы единичных направляющих векторов граничных ребер, отщепляется как двойка, таки дополнительная ей тройка граничных ребер.
Поэтому для того, чтобы подсчитать количество элементарных геометрических расщеплений# 1 (Γ0 ) сети Γ0 , нужно подсчитать только количество двоек ребер,выходящих из вершины , сумма единичных направляющих векторовПриложения121которых по модулю строго больше 1. Для двойки ребер это условие эквивалентно тому, что угол между ними строго меньше 120∘ . Докажем,что и в случае 2) это количество не больше 6.Для краткости двойку ребер { , } будем обозначать просто (),а через обозначим единичный направляющий вектор ребра , =1, . .
. , 5.Лемма 3.14 В случае 2) количество отщеплений двоек ребер не превосходит 6.Доказательство. Пусть граничные вершины расположены так, что ихнумерация соответствует обходу против часовой стрелки вокруг подвижной вершины — точки , см. рис. 3.10.Если любой угол между не соседними ребрами не меньше 120∘ , тоотщепляющихся двоек ребер может быть не больше 5. Пусть теперь усети Γ0 есть угол между не соседними ребрами, градусная мера которогострого меньше 120∘ . Из таких углов возьмем наименьший.
Без ограничения общности можно считать, что это угол \1 3 . Проведем прямую\(), содержащую биссектрису угла 1 3 , и прямую ( ), содержа\щую биссектрису угла 2 , а также прямую (2 ), содержащую ребро\[\2 . Пусть 2 = 2, тогда = 2 = . Теперь обозначим через вектор равный 1 + 3 , а через вектор равный + 2 . Заметим, что|| > 1 и лежит на луче [ ), и || > 1, но про вектор можно лишь\сказать, что он лежит во внутренней области угла 2 . Поскольку5 + 4 = −, то ̂︂5 4 < 2. Поэтому векторы 5 и 4 лежат во внутренней\области угла 1 и составляют с лучом [ ) угол не больший 2. Таккак 2 < 60∘ , то следовательно отщепляться могут только двойки (12),(13), (23), (15), (14), (45), т.е.
не более 6 отщеплений двоек. Предложение 3.7 Если в случае 2) имеется 6 отщеплений двоек, т.е.# 1 (Γ0 ) = 6, то # 2 (Γ0 ) ≥ 4. Если в случае 2) имеется 5 отщеплений двоек, т.е. # 1 (Γ0 ) = 5, то # 2 (Γ0 ) ≥ 2.Доказательство. Сначала рассмотрим случай # 1 (Γ0 ) = 6.Для того чтобы двум парам отщепляющихся двоек ребер было инцидентно одно и то же мощное расщепление из 2 (Γ0 ) необходимо идостаточно, чтобы все эти четыре ребра были различными.
РассмотримПриложения122Рис. 3.10:пары отщепляющихся двоек, соответствующих какому-нибудь мощномурасщеплению из 2 (Γ0 ).Предположим, что среди 6 отщепляющихся двоек ребер имеется одна двойка, которая не имеет пары среди оставшихся пяти двоек. Пустьдля определенности это будет двойка (12). Тогда оставшиеся пять двоекдолжны выбираться из набора (13), (14), (15), (23), (24), (25).
Одна двойка лишняя, поэтому для определенности уберем двойку (13). Тогда формируются следующие пары двоек: {(23), (14)}, {(23), (15)}, {(14), (25)},{(24), (15)}. Таким образом # 2 (Γ0 ) = 4.Теперь разберем вариант, когда любая двойка имеет пару.
Тогда наихудший для нас случай, когда 6 двоек разбиваются на три пары и больше пар нет. Покажем, что так быть не может. В самом деле, возьмемкакую-нибудь пару, пусть для определенности это будет пара {(12), (34)}.Следовательно двойки (15), (25), (35), (45) не должны содержатся средиоставшихся четырех двоек, а поскольку комбинаторно число двоек реберравно 10 (число сочетаний из 5 по 2), то эти оставшиеся четыре двойки есть (13), (14), (23), (24). То есть получается, что ребро 5 образует слюбым другим ребром угол не меньший 120∘ , чего быть не может.Теперь рассмотрим случай # 1 (Γ0 ) = 5.Предположим, что, как и в предыдущем случае, среди 5 отщепляющихся двоек имеется одно, не имеющая пары.
Пусть для определенности это будет двойка (12). Тогда оставшиеся четыре двойки должнывыбираться из набора (13), (14), (15), (23), (24), (25). Есть три принципиальные, т.е. с точностью до переобозначений, возможности откинутьиз этого набора две двойки.Приложения123∙ Две двойки либо с 1, либо с 2. Тогда остаются (15), (23), (24), (25)и формируются две пары {(15), (23)}, {(15), (24)}.∙ Одну двойку с 1 и одну двойку с 2, но с одинаковыми вторымиребрами. Тогда остаются (14), (15), (24), (25) и формируются двепары {(14), (25)}, {(24), (15)}.∙ Одну двойку с 1 и одну двойку с 2, но с разными вторыми ребрами. Тогда остаются (14), (15), (23), (25) и формируются три пары{(14), (23)}, {(15), (23)}, {(14), (25)}.Таким образом, при наличии отщепляющейся двойки без пары предложение для случая # 1 (Γ0 ) = 5 доказано.Если же любая отщепляющаяся двойка имеет пару среди оставшихсячетырех, то очевидно, что не менее двух пар у нас найдется.
Вывод основного утверждения.Напомним, что мы вывели оценку: |2 | ≤ 2 · # 1 (Γ0 ) − # 2 (Γ0 ). Суммируя теперь результаты случаев 1) и 2), из предложений 3.6 и 3.7 получаем, что правая часть 2 · # 1 (Γ0 ) − # 2 (Γ0 ) этой оценки не превосходит 8. Таким образом, мы доказали следующее утверждение.Утверждение 3.7 Количество локально минимальных сетей, затягивающих типичную границу из 5 точек на евклидовой плоскости, не превосходит 8.3.4Задача об универсальной границеВ параграфе 3.3 мы видели, что нетривиальные оценки на количестволокально минимальных сетей, затягивающих данную границу на евклидовой плоскости R2 , являются следствием того, что не все комбинаторно возможные расщепления минимальных параметрических сетейс границей могут уменьшить их длину.
Естественно возникают дватесно связанных между собой вопроса:1. Найдется ли граница (естественно уже не на евклидовой плоскости), такая что для любой минимальной параметрической сетиΓ, затягивающей границу , любое ее комбинаторное расщеплениеможет уменьшить длину сети Γ.Приложения1242. Найдется ли граница (естественно уже не на евклидовой плоскости), такая что для любого бинарного дерева , затягивающегограницу , существует локально минимальная сеть типа .Второй вопрос известен как задача об универсальной границе, которая была сформулирована А.
О. Ивановым и А. А. Тужилиным в работе [7].Сформулируем теперь основную теорему настоящего параграфа.Теорема 3.1 Для любого геометрического дерева , затягивающеговершины правильного -мерного симплекса, соответствующая минимальная параметрическая сеть типа невырождена.Покажем, что эта теорема дает ответ на оба вопроса, поставленныхвыше, о границе и, более того, предъявляет конкретный пример такойграницы — вершины правильного -мерного симплекса.Итак, пусть граница — это совокупность вершин правильного мерного симплекса.1) Рассмотрим некоторую минимальную параметрическую сеть Γ, затягивающую границу , и некоторое ее комбинаторное расщепление Γ′ .Поскольку у сети Γ′ имеется хотя бы одно вырожденное ребро, то она является вырожденной, и, согласно теореме 3.1, не является минимальнойпараметрической сетью в своем классе.
Следовательно, комбинаторноерасщепление Γ′ может уменьшить длину сети Γ.2) Поскольку, как следует из леммы 3.2, в случае бинарных деревьевневырожденная минимальная параметрическая сеть является локальноминимальной, то из теоремы 3.1 мы получаем ответ на второй вопрос.Следствие 3.2 Для любого бинарного дерева , затягивающего вершины правильного -мерного симплекса, существует локально минимальная сеть типа .Доказательство теоремы 3.1§1.
Приведем здесь идею доказательства, детали которого излагаютсяначиная с §2. Очевидно, что для любого геометрического дерева существует соответствующая минимальная параметрическая сеть типа .Однако, у такой сети, вообще говоря, могли бы быть вырожденные ребра.Приложения125Покажем, что в случае когда граничное множество состоит из вершинправильного -мерного симплекса, все ребра невырожденные.Доказательство будет вестись от противного. Пусть Γ — некотораяминимальная параметрическая сеть, затягивающая вершины правильного -мерного симплекса △.
Предположим, что у сети Γ имеются вырожденные ребра, через = () обозначим одно из них. Рассмотримдве ветки Γ ∋ и Γ ∋ , инцидентные этому ребру. Через △ обозначим грань симплекса △, образованную граничными вершинами, принадлежащими ветке Γ , а через △ обозначим грань симплекса △, образованную граничными вершинами, принадлежащими ветке Γ . Единичныенаправляющие вектора невырожденных ребер, принадлежащих ветке Γи инцидентных компоненте вырождения ребра , “смотрят” в грань △ , аединичные направляющие вектора невырожденных ребер, принадлежащих ветке Γ и инцидентных компоненте вырождения ребра , “смотрят”в грань △ (лемма 3.15). Одна из сумм этих единичных векторов, соответствующих вершине или вершине , по модулю будет строго больше 1(следствие леммы 3.18), что противоречит критерию 3.3 минимальностипараметрических сетей.§2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
