Теория Морса минимальных сетей (1105006), страница 26
Текст из файла (страница 26)
параграф 3.3). Следовательно, остаютсясправедливыми и следующие оценки.Теорема 3.2 Пусть — двумерное односвязное полное многообразиес неположительной секционной кривизной,∙ и ⊂ — граница общего положения, состоящая из четырехточек. Тогда количество локально минимальных сетей на многообразии , затягивающих границу , равно либо 1, либо 2.Приложения141Рис. 3.12: Манхэттенская плоскость.∙ и ⊂ — граница общего положения, состоящая из пяти точек. Тогда количество локально минимальных сетей на многообразии , затягивающих границу , не превосходит 8.55.1Минимальные сети на манхэттенской плоскости ℋМанхэттенская плоскостьПусть на плоскости R2 задана некоторая система координат (, ).
Напомним, что манхэттенской нормой вектора = (, ) ∈ R2 называется сумма модулей его координат, т.е. () = || + ||. ПлоскостьR2 с введенной на ней манхэттенской нормой называется манхэттенской плоскостью. Манхэттенская плоскость также является метрическим пространством с метрикой, индуцированной нормой .Сферой Минковского для манхэттенской нормы , т.е. множествомвекторов из R2 , норма которых равна 1, является квадрат, изображенный на рис. 3.12 сплошной линией.
Назовем этот квадрат квадратомнормы . Пунктирной линией на рис. 3.12 изображена сфера Минковского конормы * (мы здесь пользуемся стандартным отождествлением* R2 и R2 ). Этот квадрат мы назовем квадратом конормы * .Из рис. 3.12 видно, что для почти всех векторов субградиентноемножество () состоит из одного вектора.
Исключение составляютвектора, имеющие вертикальное или горизонтальное направление, такиевектора мы назовем особыми.Приложения142Далее до конца раздела 5 для удобства будем считать, что все границы = { }=1 обладают следующими двумя условиями.1. Все точки множества различны;2. Пусть ( , ) — прямая, проведенная через пару граничных точек , . Потребуем, чтобы для каждой пары граничных точекпрямая ( , ) не имела ни вертикального, ни горизонтального направления.Совокупность всех границ, обладающих этими двумя свойствами, обозначим через A.
В совокупности всех границ R2 множество A являетсяоткрытым и всюду плотным подмножеством. Поэтому любую границу из A будем называть типичной границей или границей общего положения.До конца раздела 5 настоящей главы будем считать, что все сетизатягивают границы общего положения.5.2Формулировка задачиВ отличие от случая евклидовой плоскости, где каждое критическое подмножество ( ) состоит из одной точки (отсюда, в частности, следовала комбинаторная морсовость функции ℓ), для манхэттенской плоскости такой факт, вообще говоря, не имеет места. Поэтому для евклидовой плоскости задача подсчета количества локально минимальных сетейсвелась к подсчету критических подмножеств ранга − 3. Для манхэттенской плоскости таким образом задачу ставить не имеет смысла,поскольку даже при типичных конфигурациях граничных точек можетсуществовать бесконечно много локально минимальных сетей данноготипа.Заметим, что в евклидовом случае локально минимальные сети являлись локальными минимумами функции ℓ на пространстве .
Такимобразом, задача поиска локально минимальных сетей эквивалентна задаче поиска локальных минимумов функции ℓ на пространстве .Основное отличие случая манхэттенской плоскости от евклидовой состоит в том, что в типичной ситуации для манхэттенской плоскости локальные минимумы функции ℓ на неизолированы, или, другими словами, локальный минимум состоит не из одной точки, а из целого множества.Приложения143Определение.
Пусть для всех точек некоторого связного подмножества ⊂ значения функции ℓ одинаковы и равны . Подмножество назовем локальным минимумом функции ℓ в традиционном смысле, если в любой достаточно малой проколотой окрестности ( )∖значения функции ℓ во всех точках из ( )∖ строго больше .Итак, до конца этого раздела мы будем решать следующую задачу:для манхэттенской плоскости оценить количество локальных минимумовфункции ℓ на пространстве .5.3Комбинаторные локальные минимумыОказывается, что, если ℓ является комбинаторной функцией Морса, тоее локальные минимумы в традиционном смысле совпадают с некоторыми из критических подмножеств ( ).
Класс таких подмножествможно выделить с помощью следующего комбинаторного определения.Определение. Пусть ( ) — некоторое критическое подмножествофункции ℓ на пространстве , а Γ — его канонический представитель. Критическое подмножество ( ) называется комбинаторным локальным минимумом функции ℓ на пространстве , если к-потенциал− (Γ ) сети Γ пуст.Лемма 3.27 Пусть ℓ — комбинаторная функция Морса. Множество ⊂ является локальным минимумом функции ℓ в традиционномсмысле тогда и только тогда, когда совпадает с одним из комбинаторных локальных минимумов ( ).Доказательство.Необходимость.
Пусть подмножество ⊂ является локальнымминимумом функции ℓ в традиционном смысле и ℓ( ) = ˜. Покажемсначала, что ˜ — критическое значение. Рассмотрим какой-нибудь страт(△), пересекающийся с множеством . Покажем, что существенныйсимплекс △ присутствует в комплексе ≤˜ , но не присутствует в комплексе <˜ . В самом деле, пересечение ∩ (△) является локальнымминимумом для функции ℓ, ограниченной на страт (△).
И в силу выпуклости функции ℓ на страте (△) подмножество ∩ (△) является также глобальным минимумом для ℓ|(△) . Следовательно, множество<˜ не пересекается со стратом (△), и симплекс △ не принадлежитПриложения144комплексу <˜ . Поэтому при прохождении значения ˜ комплекс ≤ перестраивается, следовательно, ˜ — критическое значение.Из приведенных выше рассуждений также следует, что является подмножеством критического множества Critℓ (˜). Поэтому оно пересекается с одним из критических подмножеств ( ) ⊂ Critℓ (˜).В силу выпуклости функции ℓ, каждое из критических подмножеств( ) ⊂ Critℓ (˜) является связным, и в объединении эти непересекающиеся критические подмножества дают все критическое множество Critℓ (˜)(см.
лемму 2.17). Следовательно, имеет место равенство ( ) = .Покажем теперь, что критическое множество ( ) является комбинаторным локальным минимумом. В самом деле, в силу определения локального минимума , канонический представитель Γ критического подмножества ( ) является локальным минимумом (возможно нестрогим) функции ℓ в каждом из стратов, содержащих сеть Γ . Попричине выпуклости функции ℓ, в каждом из таких стратов сеть Γ является и абсолютным минимумом функции ℓ.
Следовательно, к-потенциал− (Γ ) пуст.Достаточность. Пусть ( ) — некоторый комбинаторный локальный минимум. Множество ( ) связно и ℓ(( )) = ˜. Согласно определению комбинаторного локального минимума, − (Γ ) = ∅. Поскольку,для любой сети Γ из критического подмножества ( ) ее к-потенциал− (Γ) содержится в к-потенциале − (Γ ) канонического представителяΓ , то − (Γ) также пуст. Это означает, что в любой достаточно малойпроколотой окрестности ( )∖ критического подмножества ( )нет точек, значение функции ℓ в которых строго меньше ˜.
Следовательно, — локальный минимум функции ℓ в традиционном смысле. Таким образом, лемма 3.27 сводит задачу нахождения локальных минимумов в традиционном смысле к нахождению комбинаторных локальных минимумов.5.4Локальное устройство минимальной параметрической сети топологии звездаДля получения оценок на количество комбинаторных локальных минимумов (критических подмножеств) с помощью теоремы 2.2 нам потребуется информация о мощных расщеплениях минимальных параметриче-Приложения145ских сетей.
Вся необходимая информация о мощных расщеплениях сети,согласно критерию 3.1, содержится в ее локальной структуре.Изучение локальной структуры минимальных параметрических сетей начнем со случая, когда минимальная параметрическая сеть Γ имееттопологию звезды , т.е. у геометрического дерева имеется граничных вершин и одна подвижная вершина . Ребра, вектора направленийкоторых являются особыми, также будем называть особыми ребрами.Пусть minℓ [] — множество минимальных параметрических сетей длякласса []. В дальнейшем нам будет полезно выделить из множестваminℓ [] какую-нибудь сеть с наименьшим количеством особых ребер; такую сеть назовем лучшим представителем множества minℓ [].В силу п.2) определения границы общего положения, два особых ребра не могут иметь совпадающие или противоположные направления.Следовательно, у любой сети особых ребер не более двух.Рассмотрим теперь случай минимальной параметрической сети с одним особым ребром.
Для каждого особого ребра субградиентное множество (, ) является одной из сторон квадрата конормы * , см. рис. 3.12.Средним значением субградиента для особого ребра назовем ковектор,являющийся серединой этой стороны, а крайними значениями субградиента для особого ребра назовем ковектора, являющиеся концами этойстороны. Заметим, что для каждого неособого ребра субградиентноемножество (, ) состоит из единственного ковектора, являющегося одной из вершин квадрата конормы * .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
