Теория Морса минимальных сетей (1105006), страница 2
Текст из файла (страница 2)
лежат в ;∙ если вершина степени 2 не граничная, то угол между выходящимииз нее ребрами равен 180∘ .Из этой теоремы следует, что мы можем, не изменяя локально минимальной сети Γ как подмножества многообразия , добавлять и удалять из Γ неграничные вершины степени 2 (также сделав естественнуюперестройку ребер). Полученная при этом сеть останется локально минимальной.Вышесказанное приводит к следующему соглашению: в дальнейшем,не ограничивая общности, будем всегда считать, что рассматриваемыесети не имеют неграничных вершин степени 2.Введение8Таким образом, можно считать, что все вершины степени 1 и 2 локально минимальной сети Γ принадлежат ее границе.
Теперь видно, чтопо модулю этого соглашения имеется конечное число типов локально минимальных сетей. Мелзак [32] в 1960 году придумал алгоритм построениялокально минимальной сети по заданному типу, являющемуся деревом,и заданной границе . Однако, этот алгоритм имеет экспоненциальнуюсложность. Хванг [27] в 1986 году сократил время работы этого алгоритма до линейного.Ясно, что любая абсолютно минимальная сеть является локально минимальным деревом.
Поэтому, строя все локально минимальные деревьяс помощью алгоритма Мелзака-Хванга и выбирая затем из них сеть снаименьшей длиной, мы найдем абсолютно минимальную сеть. Такимобразом, основная сложность этого метода заключается в большом переборе возможных типов локально минимальных сетей. Как мы уже отмечали, проблема Штейнера является NP-трудной.Возникает вопрос: насколько a priori мы можем ограничить переборвозможных типов локально минимальных сетей, затягивающих даннуюграницу? В работах [5] и [17] А. О. Иванов и А. А.
Тужилин изучаливлияние геометрии границы на такие априорные ограничения. Другимисловами этот вопрос можно сформулировать следующим образом: какоемаксимальное количество локально минимальных сетей может затягивать данную (но произвольную) границу?А. Т. Фоменко, А. О. Иванов и А. А. Тужилин предположили, что дляответа на этот вопрос мог бы быть полезен некий аналог теории Морсадля минимальных сетей.
Более развернуто их идея применения теорииМорса для оценки количества локально минимальных сетей, затягивающих данную границу, изложена в следующей программе:1. Построить конфигурационное пространство , точки которогоможно было бы интерпретировать как сети с данной границей.2. Задать на пространстве функцию .3. Определить критические точки и критические значения функции .
Причем сделать это так, чтобы некоторые из критических точекможно было бы интерпретировать как локально минимальные сетис данной границей.4. Определить аналог индекса из классической теории Морса для критических точек функции .Введение95. Найти связь между индексами критических точек функции инекоторыми характеристиками (например, топологией) пространства .Оценивая индексы критических точек, с помощью п. 5) вышеизложенной программы можно оценивать и количество некоторых критических точек, в частности, локально минимальных сетей с данной границей, которые, согласно п. 3), также являются критическими точками.В настоящей диссертации построена теория Морса минимальных сетей, удовлетворяющая всем пяти пунктам вышеприведенной программы, и продемонстрировано приложение построенной теории Морса дляполучения оценок на количество локально минимальных сетей, затягивающих данную границу.2Краткое содержание диссертацииВ главе 1 определяются базовые понятия и объекты данной диссертации: параметрическая сеть (или просто сеть) в общем метрическом пространстве; параметризующий граф сети; граничные и подвижные вершины, граничные и внутренние ребра сети и параметризующего графа;граница сети; количество внутренних ребер называется рангом сети и параметризующего графа; длина сети; минимальная параметрическая сеть.Вводится понятие геометрического дерева как дерева, имеющего вершин степени 1, которые считаются граничными и помечены различнымичислами от 1 до , и не имеющего вершин степени 2.
Ниже, в разделе 3Введения и более формально в главе 3, показывается, что для нашихцелей в качестве параметризующих графов сетей имеет смысл ограничиться рассмотрением только геометрических деревьев. Множество всехгеометрических деревьев с граничными вершинами обозначается через . На этом множестве задается отношение частичного порядка ивыясняются некоторые свойства множества , связанные с этим отношением. Выводятся формулы, вычисляющие количество геометрическихдеревьев с фиксированным числом граничных и подвижных вершин.Далее, изучаются регулярные сети, т.е.
сети без вырожденных внутренних ребер, параметризованные геометрическими деревьями. Строится конфигурационное пространство всех регулярных сетей с даннойграницей. На этом пространстве корректно определена функция ℓ длиныВведение10сети. Пространство понадобится в главе 2 при реализации программыпостроения теории Морса минимальных сетей.В главе 2 формулируется общая концепция построения теории Морса для произвольных множеств и произвольных функций на них. В рамках этой концепции кратко напоминается классическая теория Морса итеория Морса для симплициальных комплексов, основы которой заложены О.
Р. Мусиным в работе [12]. Определение комплекса − и индекса длякритической точки из работы [12] послужили отправной точкой для разработанного в этой главе комбинаторного подхода к построению теорииМорса для произвольных множеств и функций на них — комбинаторнойтеории Морса.С помощью результатов комбинаторной теории Морса последовательно реализуется программа построения теории Морса минимальных сетей, изложенная в разделе 1 Введения. В качестве пары множествофункция берется из главы 1 конфигурационное пространство всехрегулярных сетей с данной границей и функция длины сети ℓ.
К пространству и функции ℓ применяется комбинаторный подход для определения критических значений, критических точек и их индексов. Выводится равенство Морса, связывающее индексы критических значений(точек) с “топологией” пространства . На пространстве вводитсянекоторая фильтрация подпространствами () , которая позволяет написать несколько равенств Морса.
Показывается, что все критическиеточки функции ℓ можно интерпретировать как минимальные параметрические сети, и обратно. Для минимальной параметрической сети определяются мощные расщепления и доказывается, что индекс критическойточки можно вычислить через мощные расщепления соответствующейминимальной параметрической сети. С помощью полученных равенствМорса выводятся формулы, позволяющие вычислить количество минимальных параметрических сетей ранга через мощные расщепления минимальных параметрических сетей с меньшим рангом (более точно этотрезультат сформулирован ниже).Основная задача главы 3 — показать применимость теории Морсаминимальных сетей для изучения минимальных сетей в различных метрических пространствах. Особое внимание уделяется следующим пространствам: евклидовы пространства R , полные односвязные римановы многообразия с неположительной секционной кривизной и манхэттенская плоскость.
Результаты теории Морса минимальных сетей позволяют получить оценки на количество локально минимальных сетей,Введение11затягивающих фиксированную границу общего положения в одном изэтих пространств. Оценки подобного рода получены для локально минимальных сетей, затягивающих границу общего положения, состоящую из4, 5 точек (случай 3 граничных точек тривиален) на двумерных полныходносвязных римановых многообразий с неположительной секционнойкривизной (в частности для евклидовой плоскости R2 и плоскости Лобачевского 2 ). Для манхэттенской плоскости в случае границы общего положения из 4, 5 граничных точек получены оценки на количестволокально минимальных критических множеств (здесь также случай 3граничных точек тривиален). Кроме того, показано, что степени вершинсетей из локально минимальных критических множеств в случаях границы общего положения из 4 или 5 точек не превосходят 3.
Отметим,что для границ не общего положения степень вершин таких сетей может быть равна 4. Также в этой главе найдена универсальная граница,т.е. граница, которую затягивают все комбинаторно возможные локальноминимальные сети.3Основные результаты диссертацииПриведем основные определения и результаты диссертации.1) Комбинаторная теория Морса.Мы начнем изложение основных результатов и определений диссертации с комбинаторной теории Морса, идеи которой затем используютсяпри реализации программы построения теории Морса для минимальныхсетей из раздела 1 Введения.Пусть — некоторое множество и — вещественнозначная функцияна . Обозначим через ≤ подмножество точек из множества , в которых значение функции не превосходит числа . Главный вопрос, накоторый должна отвечать теория Морса для пары (, ), можно сформулировать следующим образом: Как меняется множество ≤ с изменением числа ?В частности, в теории Морса для пары (, ) должно быть определено что означает слово “меняется”.
Так, в классической теории Морса, где — гладкое многообразие и — гладкая функция на , под “изменением” множества ≤ , которое является топологическим пространством,понимают изменение его гомотопического типа. В симплициальной теории Морса, основы которой заложены О. Р. Мусиным в работе [12], мно-Введение12жество является совокупностью вершин конечного симплициальногокомплекса ℳ и — произвольная вещественнозначная функции на .Здесь под “изменением” множества ≤ понимается изменение комбинаторной структуры комплекса ℳ≤ . Комплекс ℳ≤ по определениюсостоит их всех симплексов, вершины которых суть вершины из множества ≤ . Эти два примера теорий Морса подробнее рассматриваются вразделах 2 и 3 главы 2.В диссертации предлагается комбинаторный подход к построениютеории Морса для общего случая: — произвольное множество, —произвольная вещественнозначная функция на .Для этого нам понадобится ввести на множестве дополнительнуюструктуру. Рассмотрим какое-нибудь конечное покрытие Σ множества его подмножествами , = ∪ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
