Теория Морса минимальных сетей (1105006), страница 29
Текст из файла (страница 29)
Чтобы это показать нам необходимо подробнее рассмотреть приращение ˜ в каждом критическом значении˜.Лемма 3.35 Пусть ˜ — самое большое критическое значение функцииℓ. Тогда комплекс ˜ представляет собой симплекс, отвечающий геометрическому дереву типа звезда.Приложения157Доказательство. Согласно следствию 2.3, критические значения функции ℓ — это длины минимальных параметрических сетей. Посколькутипы всех минимальных параметрических сетей являются некоторымирасщеплениями геометрического дерева типа звезда, то, следовательно,длина минимальной параметрической сети типа звезда не меньше, чемдлина любой минимальной параметрической сети другого типа.
Для 3 граничных точек имеется всего один тип сетей — звезда. Поэтому для 3 граничных точек условие 2) из определения комбинаторнойфункции Морса выполнено.Для 4 граничных точек для максимального критического значения˜, в силу леммы 3.35, условие 2) также выполнено. Рассмотрим теперьостальные критические значения. Пусть — немаксимальное критическое значение. Тогда в критическом множестве Critℓ () нет регулярныхсетей типа звезда. Следовательно, типы регулярных сетей из Critℓ () —это бинарные деревья.
Таким образом, максимальные симплексы длякомплекса соответствуют стратам ⟨⟩, где — бинарное дерево, т.е.являются нульмерными симплексами. Нульмерные симплексы не пересекаются, поэтому для случая 4 граничных точек условие 2) из определения комбинаторной функции Морса полностью выполняется.Остался случай 5 граничных точек. Пусть — некоторое критическоезначение. Разберем структуру комплекса . В качестве максимальныхсимплексов в этот комплекс могут входить: симплекс, отвечающий страту типа звезда, — 14-мерный; симплексы, отвечающие типам деревьевс двумя подвижными вершинами, — 2-мерные; симплексы, отвечающиебинарным деревьям, — 0-мерные.Если в входит максимальный симплекс, отвечающий типу звезда, то никаких других максимальных симплексов в нет.
Поэтомудля данного критического значения условие 2) из определения комбинаторной функции Морса выполняется.Если в в качестве максимальных симплексов входят только симплексы отвечающие бинарным деревьям, то эти нульмерные симплексыне пересекаются, и для данного критического значения условие 2) изопределения комбинаторной функции Морса также выполняется.Разберем случай, когда в комплексе нет максимального симплекса, отвечающего типу звезда, но имеются максимальные симплексы, отвечающие деревьям с двумя подвижными вершинами. Без ограничения общности можно считать, что в нет максимальных нуль-Приложения158мерных симплексов. Пусть △1 и △2 — максимальные симплексы, отвечающие деревьям с двумя подвижными вершинами.
Покажем, что либо △ = △1 ∩ △2 ∈ < , либо в комплексе имеется максимальныйсимплекс, отвечающий типу звезда, т.е. получим противоречие. Такимобразом, и для случая 5 граничных точек условие 2) из определениякомбинаторной функции Морса также будет выполнено.Обозначим через 1 и 2 геометрические деревья, отвечающие симплексам △1 и △2 соответственно. Поскольку в комплексе симплексы△1 и △2 максимальны, то в критическом множестве Critℓ () существуют две регулярных минимальных параметрических сети Γ1 и Γ2 типов1 и 2 соответственно.
Все максимальные симплексы являются существенными, их пересечение, согласно лемме 2.4, также является существенным симплексом. Поскольку △1 и △2 — существенные симплексы,отвечающие деревьям с двумя подвижными вершинами, то их пересечение △ = △1 ∩ △2 — 0-мерный существенный симплекс, отвечающийнекоторому бинарному дереву . Предположим, что △ ̸∈ < . Это означает, что минимум функции ℓ на страте ⟨⟩ равен . Следовательно,множество минимумов minℓ ⟨⟩ содержит сети Γ1 и Γ2 . В силу выпуклости множества minℓ ⟨⟩, сети Γ1 и Γ2 можно соединить отрезком, целикомлежащим в minℓ ⟨⟩.
Имеется два варианта: либо на этом отрезке найдется регулярная минимальная параметрическая сеть Γ типа , либо нанем найдется регулярная минимальная параметрическая сеть Γ0 типа0 — звезда. Второй вариант противоречит нашему предположению, поскольку тогда бы в комплексе имелся бы максимальный 14-мерныйсимплекс, отвечающий типу звезда. Оказывается, что и для первого варианта в множестве minℓ ⟨⟩ (уже не на вышепостроенном отрезке) найдется регулярная минимальная параметрическая сеть Γ0 типа звезда.Предложение 3.13 Пусть — бинарное дерево, затягивающее 5 точек на манхэттенской плоскости.
Обозначим через 1 и 2 внутренниеребра дерева . Пусть Γ ∈ minℓ [] — минимальная параметрическаясеть без вырожденных внутренних ребер. Тогда, если в множествеminℓ [] существуют сеть Γ1 с вырожденным ребром 1 и невырожденным ребром 2 и сеть Γ2 с вырожденным ребром 2 и невырожденнымребром 1 , то множеству minℓ [] принадлежит и минимальная параметрическая сеть Γ0 с двумя вырожденными внутренними ребрами.Доказательство. При доказательстве данного предложения нам пона-Приложения159Рис.
3.16:добится лемма о локальной структуре в окрестности подвижной вершины степени 3 регулярной минимальной параметрической сети Γ[].Лемма 3.36 Регулярная минимальная параметрическая Γ[] в окрестности своей подвижной вершины степени 3 может быть устроена одним из следующих способов, изображенных на рис. 3.16.На рис. 3.16 звездочкой отмечена граничная вершина, а точкой —подвижная.Доказательство. Обозначим через подвижную вершину сети Γ, а через 1 , 2 , 3 — ребра, инцидентные этой вершине.
Поскольку сеть Γявляется минимальной параметрической сетью, то, в силу критерия 3.1,соответствующие субградиенты ребер 1 , 2 , 3 должны удовлетворятьуравнению 1 + 2 + 3 = 0. Это уравнение в каждом из рассматриваемых далее случае однозначно определяет взаимное расположение ребер1 , 2 , 3 (с точностью до отражений относительно координатных осей иповоротов на угол кратный 2 ).Пусть у сети Γ в подвижной вершине ∙ нет вырожденных ребер, инцидентных , иПриложения160– нет особых ребер, инцидентных . Такого случая быть не может, см.
лемму 3.29 (про локальную структуру звезды при = 3).– имеется одно особое ребро, инцидентное . Такого случая бытьне может, см. доказательство леммы 3.28 (про локальнуюструктуру звезды при = 3)– имеются два особых ребра и одно неособое ребро, инцидентные . В этом случае может быть единственный возможныйвариант, изображенный на рис 3.16 a).– имеются три особых ребра, инцидентных . В этом случае может быть единственный возможный вариант, изображенныйна рис 3.16 b).∙ есть вырожденные ребра (тогда такое ребро одно и оно являетсяграничным) и– нет особых ребер, инцидентных . В этом случае может бытьединственный возможный вариант, изображенный на рис 3.16c).– имеется одно особое ребро, инцидентное .
В этом случае может быть единственный возможный вариант, изображенныйна рис 3.16 d).– имеются два особых ребра, инцидентных . В этом случае может быть два возможных варианта, изображенных на рис 3.16e) и f).Следствие 3.4 Пусть — подвижная вершина регулярной минимальной параметрической сети Γ[], которой инцидентны два граничныхребра и одно внутреннее. Тогда локальная структура сети Γ в подвижной вершине может быть устроена одним из пяти способов, изображенных на рис. 3.17 (с точностью до отражений относительно координатных осей и поворотов на угол кратный 2 ).Пусть — подвижная вершина регулярной минимальной параметрической сети Γ[], которой инцидентны одно граничное ребро и двавнутренних.
Тогда локальная структура сети Γ в подвижной вершинеПриложения161Рис. 3.17:Рис. 3.18: может быть устроена одним из восьми способов, изображенных нарис. 3.18 (с точностью до отражений относительно координатныхосей и поворотов на угол кратный 2 ).Также нам будет нужна следующая очевидная геометрическая лемма.Лемма 3.37 Пусть [0 , 0 ] и [1 , 1 ] — отрезки на плоскости R2 .Предположим, что точки = () и = () движутся равномернои прямолинейно из точек 0 = (0) и 0 = (0) в точки 1 = (1) и1 = (1). ТогдаПриложения162∙ если прямые (0 , 0 ) и (1 , 1 ) параллельны, то и прямая( (), ()) в любой момент времени 0 < < 1 параллельна этимпрямым;∙ если прямые (0 , 0 ) и (1 , 1 ) не параллельны, то и прямая( (), ()) в любой момент времени 0 < < 1 не параллельнани одной из этих прямых.(Здесь мы полагаем, что “прямая” (, ) при = параллельна любойпрямой на плоскости R2 .)Следующая лемма описывает структуру множества minℓ [] минимальных параметрических сетей типа при определенных условиях.Лемма 3.38 Пусть в множестве minℓ [] имеется регулярная минимальная параметрическая сеть Γ, которая в окрестности своей подвижной вершины устроена так,1.
как показано на рис. 3.16 a), т.е. вершине инцидентны два особых невырожденных ребра 1 и 2 и одно невырожденное неособоеребро . Тогда у любой минимальной параметрической сети Γ′ изminℓ [] ребра ′1 и ′2 параллельны соответствующим ребрам 1 и2 сети Γ.2. как показано на рис. 3.16 c), т.е. вершине инцидентны два неособых невырожденных ребра и одно вырожденное граничное ребро(, ), где — граничная вершина и Γ() = , ∈ — граничнаяточка. Тогда у любой минимальной параметрической сети Γ′ изminℓ [] положение подвижной вершины совпадает с положением граничной вершины , т.е. Γ′ () = Γ′ () = .3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
