Теория Морса минимальных сетей

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМЕХАНИКО–МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТНа правах рукописиКарпунин Григорий АнатольевичУДК 515.164.174+514.772+519.711.7ТЕОРИЯ МОРСА МИНИМАЛЬНЫХ СЕТЕЙ01.01.04 — геометрия и топологияДИССЕРТАЦИЯна соискание ученой степеникандидата физико–математических наукНаучный руководитель:профессор, доктор физико-математических наук,А. А.

ТужилинМосква – 2001ОглавлениеВведение51Актуальность темы . . . . . . . . . . . . . . . . . . . . . . . 52Краткое содержание диссертации . . . . . . . . . . . . . . . 93Основные результаты диссертации . . . . . . . . . . . . . . 111 Сети в метрических пространствах1Основные определения . .

. . . . . . . . . . . . . . . . . . .1.1Сети, параметризующие графы, длина сети . . . . .1.2Графы с границей, сети с границей . . . . . . . . . .1.3Тип сети с границей, минимальные параметрические сети . . . . . . . . . . . . . . . . . . . . .

. . . .1.4Операции редукции и расщепления . . . . . . . . . .1.5Компоненты вырождения. Приведенные сети . . . .2Геометрические деревья . . . . . . . . . . . . . . . . . . . . .2.1Определение множества геометрических деревьев 2.2Кодировки сцеплениями . .

. . . . . . . . . . . . . .2.3Частичный порядок на множестве . . . . . . . . .2.4Перечисление геометрических деревьев . . . . . . . .3Конфигурационное пространство всех регулярных сетейс данной границей . . . . . . . . . . . . . . . . . . . . . . . .3.1Построение пространства и функции ℓ . .

. . . . .3.2Стратификация пространства . . . . . . . . . . . .3.3Примеры . . . . . . . . . . . . . . . . . . . . . . . . .292929302 Комбинаторная теория Морса1Общая концепция построения теории Морса . . . . . . . . .2Классический случай . . . . . . . . . . . . . . . . . . . . . .3Симплициальный случай .

. . . . . . . . . . . . . . . . . . .525253562313233333334383945454749345Комбинаторный подход к общему случаю . . . . . . . . . .4.1К-топологическое пространство . . . . . . . . . . .4.2Изменение множества уровня ≤ . . . . . . . . . . .4.3Понятие критического значения .

. . . . . . . . . . .4.4Стратификация пространства . . . . . . . . . . . .4.5Понятие критической точки . . . . . . . . . . . . . .4.6Комбинаторный потенциал точки из . . . . . . . .4.7Индексы критических значений и равенство Морса .4.8Неравенства Морса . . . . . . . . . . . . . . . . . . .4.9Комбинаторная функция Морса . . . . . . . . . . . .Теория Морса минимальных сетей . .

. . . . . . . . . . . . .5.1Пространство как к-топологическое пространство5.2Критические точки и критические значения функции ℓ . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.3Комбинаторные и геометрические расщепления сетей5.4Комплекс мощных расщеплений сети . . . . . . . . .5.5Критические подмножества функции ℓ и равенствоМорса .

. . . . . . . . . . . . . . . . . . . . . . . . . .5.6Пространства () ⊂ . . . . . . . . . . . . . . . . .5.7Основная формула . . . . . . . . . . . . . . . . . . . .5858606062636568697076767778798184883 Приложения901Минимальные сети в нормированных пространствах. Общие результаты . . . . . . .

. . . . . . . . . . . . . . . . . . 901.1Некоторые факты из выпуклого анализа . . . . . . . 901.2Общий критерий минимальности параметрическойсети . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911.3Критерий минимальности параметрической сети стопологией дерева . . . . . . . . . . . . .

. . . . . . . 932Минимальные сети на римановых многообразиях. Общиерезультаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972.1Топологические графы . . . . . . . . . . . . . . . . . 982.2Параметрические сети . . . . . . . . . . . . . . . . . . 992.3Абсолютно и локально минимальные сети . . . . . . 993Минимальные сети в евклидовом пространстве R . . . . . 1003.1Локально минимальные сети как регулярные минимальные параметрические сети .

. . . . . . . . . . . 1013.2Единственность минимальных параметрических сетей1024453.3Случай плоскости R2 . . . . . . . . . . . . . . . . . .3.4Задача об универсальной границе . . . . . . . . . . .Минимальные сети на полных односвязных многообразиях неположительной секционной кривизны . . . . . . . . .

.4.1Экстремальные параметрические сети на многообразии . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2Локально минимальные сети на многообразии какрегулярные экстремальные параметрические сети . .4.3Геодезические деформации сетей на многообразии .4.4Геодезические сети на многообразии как параметрические сети в метрическом пространстве .

.4.5Минимальные параметрические сети на многообразии . . . . . . . . . . . . . . . . . . . . . . . . . . .4.6Типичные границы на многообразии . . . . . . .4.7Оценки количества локально минимальных сетей сданной границей на многообразии . . . . . . . . .Минимальные сети на манхэттенской плоскости ℋ . . . . .5.1Манхэттенская плоскость . . . . .

. . . . . . . . . . .5.2Формулировка задачи . . . . . . . . . . . . . . . . . .5.3Комбинаторные локальные минимумы . . . . . . . .5.4Локальное устройство минимальной параметрической сети топологии звезда . . . . . . . . . . . . . . .5.5Мощные расщепления минимальных параметрических сетей некоторых типов . . . . . . . . . . . .

. .5.6Комбинаторная морсовость функции ℓ для случаев3, 4, 5 граничных точек . . . . . . . . . . . . . . . . .5.7Оценки количества локальных минимумов для случаев 3, 4 и 5 граничных точек . . . . . . . . . . . . .5.8Некоторые примеры для случая 6 граничных точек107123132133134135136137138140141141142143144149156170173Список литературы174Список работ автора по теме диссертации178Введение1Актуальность темыЦель настоящей диссертации — разработать теорию Морса, применимуюк изучению минимальных сетей в метрических пространствах.

Источником большинства задач, связанных с минимальными сетями, являетсятак называемая проблема Штейнера:Среди всех сетей (связных одномерных континуумов), затягивающих данное конечное множество точек плоскости, найти сеть наименьшей длины.Решение этой задачи называется абсолютно минимальной сетью, затягивающей множество . Очевидно, что абсолютно минимальная сетьне может иметь циклов, поэтому в данной диссертации мы ограничимсярассмотрением сетей, являющихся деревьями.

Абсолютно минимальнуюсеть в литературе также называют деревом Штейнера для множества.Наверное, впервые в таком виде проблема Штейнера была сформулирована Ярником и Кесслером в 1934 году. Однако, свое название проблема Штейнера получила благодаря книге Куранта и Роббинса “Чтотакое математика? ”, написанной ими в 1941 году. Благодаря огромной популярности книги, название “проблема Штейнера” прочно вошло влексикон математиков.

Отметим, что книга Куранта и Роббинса породила не только недоразумение в авторстве, но, что более важно, привлеклак проблеме Штейнера интерес большого числа ученых.Неугасающий интерес к проблеме Штейнера объясняется несколькими причинами. Первая из них состоит в том, что, несмотря на простотупостановки, эта задача чрезвычайно нетривиальна. И хотя существуетнесложный алгоритм построения кратчайшей сети, затягивающей данное множество из точек плоскости, этот алгоритм связан с очень боль5Введение6шим перебором возможных типов сетей (т.е. графов, определяющих комбинаторную структуру сети).

В действительности, проблема Штейнераявляется NP-трудной, см. [26]. Последнее означает, что, скорее всего,для этой проблемы не существует полиномиального алгоритма, т.е. алгоритма, решающего задачу за время порядка не выше чем , где —некоторое фиксированное число.Другая причина связана с тем, что у проблемы Штейнера имеетсямного различных интерпретаций и приложений. Так, например, предположим, что возникла необходимость соединить некоторые города системой дорог. При этом желательно, чтобы затраты на прокладку дорог были наименьшими возможными.

Естественно, затраты пропорциональнысумме длин дорог, т.е. длине искомой сети. В идеальном случае, когда насеть больше не накладывается никаких ограничений (скажем, отсутствуют препятствия, и мы вольны прокладывать дороги там, где пожелаем),сеть дорог, минимизирующая затраты, является абсолютно минимальной сетью.В приведенном только что примере можно заменить города на пункты потребления, а дороги — на нефте- или газопроводы. В этом случаеабсолютно минимальная сеть — это оптимальная система нефте- или газоснабжения. Если под пунктами 1 , 2 , . . .

, понимать местонахождения абонентов, а под абсолютно минимальной сетью Γ — телефоннуюсеть, то мы получим модельную ситуацию, использующуюся в США привычислении федеральных тарифов за междугородные телефонные разговоры. В этом случае плата за разговор абонентов, находящихся в пунктах и , пропорциональна длине минимального пути в телефоннойсети Γ, соединяющего с .Существует много методов поиска абсолютно минимальной сети, затягивающей данную границу. Среди них различают точные и приближенные алгоритмы. В большинстве своем приближенные алгоритмыопираются на эвристические соображения и строго не обоснованы.

Однако, среди приближенных алгоритмов можно выделить следующий. Рассмотрим все сети, затягивающие множество , такие что каждая вершина сети принадлежит . Сеть наименьшей длины среди этого семействасетей называется минимальным остовным деревом. Примем теперь этодерево за дерево Штейнера (абсолютно минимальную сеть) для множества .

Ясно, что полученная сеть, вообще говоря, имеет большую длину,чем абсолютно минимальная сеть. Тем не менее, этот подход оказывается весьма эффективным по целому ряду причин. Во-первых, существуютВведение7быстрые алгоритмы построения минимальных остовных деревьев (например, алгоритм Краскала [31] или алгоритм Шеймоса [35]), во-вторых,длина минимального остовного дерева, оказывается, не может сильно отличаться от длины абсолютно минимального дерева (это связано с такназываемым отношением Штейнера, см. например [21]).Некоторые точные методы поиска абсолютно минимальной сети основаны на том, что для определенного класса граничных множеств, таких как вершины правильного многоугольника [24], зигзаги [23], точкина окружности со специальными свойствами [22, 34], “достаточно плотные” выпуклые многоугольники [36] и некоторые другие, абсолютно минимальные сети описаны явно.

Однако, большинство граничных множеств не входят в этот список. Остальные точные методы основаны напереборе так называемых локально минимальных сетей, т.е. сетей, у которых любой достаточно малый фрагмент абсолютно минимален. Имеется хорошо известная классическая теорема (для случая многообразийдоказанная Ивановым и Тужилиным в [28]), описывающая локальнуюструктуру локально минимальных сетей:Теорема Сеть Γ в римановом многообразии , затягивающая конечное множество точек из , является локально минимальной, еслии только если имеют место следующие свойства:∙ все ребра сети Γ — геодезические;∙ угол между любыми двумя ребрами, выходящими из одной вершины, не меньше 120∘ ; в частности, степень каждой вершины сетиΓ не превосходит 3;∙ все вершины степени 1 являются граничными, т.е.