Теория морса минимальных сетей тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Введение

1. Актуальность темы.

2. Краткое содержание диссертации.

3. Основные результаты диссертации.

1. Сети в метрических пространствах

1. Основные определения

1.1. Сети, параметризующие графы, длина сети.

1.2. Графы с границей, сети с границей.

1.3. Тип сети с границей, минимальные параметрические сети.

1.4. Операции редукции f , расщепления.

1.5. Компоненты вырождения. Приведенные сети

2. Геометрические деревья

2.1. Определение множества геометрических деревьев Q

2.2. Кодировки сцеплениями

2.3. Частичный порядок на множестве Q.

2.4. Перечисление геометрических деревьев

3. Конфигурационное пространство Т всех регулярных сетей с данной границей

3.1. Построение пространства Т и функции I.

3.2. Стратификация пространства Т.

3.3. Примеры.

2. Комбинаторная теория Морса

1. Общая концепция построения теории Морса.

2. Классический случай.

3. Симплициальный случай.

4. Комбинаторный подход к общему случаю.

4.1. К-топологическое пространство /С

4.2. Изменение множества уровня /С<с.

4.3. Понятие критического значения.

4.4. Стратификация пространства /С

4.5. Понятие критической точки.

4.6. Комбинаторный потенциал точки из /С.

4.7. Индексы критических значений и равенство Морса

4.8. Неравенства Морса.

4.9. Комбинаторная функция Морса.

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

5.1. Пространство Т как к-топологическое пространство

5.2. Критические точки и критические значения функции £.

5.3. Комбинаторные и геометрические расщепления сетей

5.4. Комплекс мощных расщеплений сети.

5.5. Критические подмножества функции I и равенство Морса.

5.6. Пространства Т(к) С Т.

5.7. Основная формула.

1. Актуальность темы

Цель настоящей диссертации — разработать теорию Морса, применимую к изучению минимальных сетей в метрических пространствах. Источником большинства задач, связанных с минимальными сетями, является так называемая проблема Штейнера:

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

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

Л.

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

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

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

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

Существует много методов поиска абсолютно минимальной сети, затягивающей данную границу. Среди них различают точные и приближенные алгоритмы. В большинстве своем приближенные алгоритмы опираются на эвристические соображения и строго не обоснованы. Однако, среди приближенных алгоритмов можно выделить следующий. Рассмотрим все сети, затягивающие множество А, такие что каждая вершина сети принадлежит А. Сеть наименьшей длины среди этого семейства сетей называется минимальным остовным деревом. Примем теперь это дерево за дерево Штейнера (абсолютно минимальную сеть) для множества А. Ясно, что полученная сеть, вообще говоря, имеет большую длину, чем абсолютно минимальная сеть. Тем не менее, этот подход оказывается весьма эффективным по целому ряду причин. Во-первых, существуют быстрые алгоритмы построения минимальных остовных деревьев (например, алгоритм Краскала [31] или алгоритм Шеймоса [35]), во-вторых, длина минимального остовного дерева, оказывается, не может сильно отличаться от длины абсолютно минимального дерева (это связано с так называемым отношением Штейнера, см. например [21]).

Некоторые точные методы поиска абсолютно минимальной сети основаны на том, что для определенного класса граничных множеств, таких как вершины правильного многоугольника [24], зигзаги [23], точки на окружности со специальными свойствами [22, 34], "достаточно плотные" выпуклые многоугольники [36] и некоторые другие, абсолютно минимальные сети описаны явно. Однако, большинство граничных множеств не входят в этот список. Остальные точные методы основаны на переборе так называемых локально минимальных сетей, т.е. сетей, у которых любой достаточно малый фрагмент абсолютно минимален. Имеется хорошо известная классическая теорема (для случая многообразий доказанная Ивановым и Тужилиным в [28]), описывающая локальную структуру локально минимальных сетей:

Теорема. Сеть Г в римановом многообразии W, затягивающая конечное множество А точек из W, является локально минимальной, если и только если имеют место следующие свойства:

• все ребра сети Г — геодезические;

• угол между любыми двумя ребрами, выходящими из одной вершины, не меньше 120°; в частности, степень каждой вершины сети Г не превосходит 3;

• все вершины степени 1 являются граничными, т.е. лежат в Л;

• если вершина степени 2 не граничная, то угол между выходящими из нее ребрами равен 180°.

Из этой теоремы следует, что мы можем, не изменяя локально минимальной сети Г как подмножества многообразия W, добавлять и удалять из Г неграничные вершины степени 2 (также сделав естественную перестройку ребер). Полученная при этом сеть останется локально минимальной.

Вышесказанное приводит к следующему соглашению: в дальнейшем, не ограничивая общности, будем всегда считать, что рассматриваемые сети не имеют неграничных вершин степени 2.

Таким образом, можно считать, что все вершины степени 1 и 2 локально минимальной сети Г принадлежат ее границе. Теперь видно, что по модулю этого соглашения имеется конечное число типов локально минимальных сетей. Мелзак [32] в I960 году придумал алгоритм построения локально минимальной сети по заданному типу, являющемуся деревом, и заданной границе Л. Однако, этот алгоритм имеет экспоненциальную сложность. Хванг [27] в 1986 году сократил время работы этого алгоритма до линейного.

Ясно, что любая абсолютно минимальная сеть является локально минимальным деревом. Поэтому, строя все локально минимальные деревья с помощью алгоритма Мелзака-Хванга и выбирая затем из них сеть с наименьшей длиной, мы найдем абсолютно минимальную сеть. Таким образом, основная сложность этого метода заключается в большом переборе возможных типов локально минимальных сетей. Как мы уже отмечали, проблема Штейнера является NP-трудной.

Возникает вопрос: насколько a priori мы можем ограничить перебор возможных типов локально минимальных сетей, затягивающих данную границу? В работах [5] и [17] А. О. Иванов и А. А. Тужилин изучали влияние геометрии границы на такие априорные ограничения. Другими словами этот вопрос можно сформулировать следующим образом: какое максимальное количество локально минимальных сетей может затягивать данную (но произвольную) границу?

А. Т. Фоменко, А. О. Иванов и А. А. ТУжилин предположили, что для ответа на этот вопрос мог бы быть полезен некий аналог теории Морса для минимальных сетей. Более развернуто их идея применения теории Морса для оценки количества локально минимальных сетей, затягивающих данную границу, изложена в следующей программе:

1) Построить конфигурационное пространство /С, точки которого можно было бы интерпретировать как сети с данной границей.

2) Задать на пространстве /С функцию /.

3) Определить критические точки и критические значения функции /. Причем сделать это так, чтобы некоторые из критических точек можно было бы интерпретировать как локально минимальные сети с данной границей.

4) Определить аналог индекса из классической теории Морса для критических точек функции /.

5) Найти связь между индексами критических точек функции / и некоторыми характеристиками (например, топологией) пространства к.

Оценивая индексы критических точек, с помощью п. 5) вышеизложенной программы можно оценивать и количество некоторых критических точек, в частности, локально минимальных сетей с данной границей, которые, согласно п. 3), также являются критическими точками.

В настоящей диссертации построена теория Морса минимальных сетей, удовлетворяющая всем пяти пунктам вышеприведенной программы, и продемонстрировано приложение построенной теории Морса для получения оценок на количество локально минимальных сетей, затягивающих данную границу.