«СЕТЕЙ ...»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М. В. ЛОМОНОСОВА

МЕХАНИКО–МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи

Карпунин Григорий Анатольевич

УДК 515.164.174+514.772+519.711.7

ТЕОРИЯ МОРСА МИНИМАЛЬНЫХ СЕТЕЙ

01.01.04 — геометрия и топология

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико–математических наук

Научный руководитель:

профессор, доктор физикоматематических наук, А. А. Тужилин Москва – 2001 Оглавление Введение 1 Актуальность темы....................... 2 Краткое содержание диссертации............... 3 Основные результаты диссертации.............. 1 Сети в метрических пространствах 1 Основные определения..................... 1.1 Сети, параметризующие графы, длина сети..... 1.2 Графы с границей, сети с границей.......... 1.3 Тип сети с границей, минимальные параметрические сети......................... 1.4 Операции редукции и расщепления.......... 1.5 Компоненты вырождения. Приведенные сети.... 2 Геометрические деревья..................... Определение множества геометрических деревьев 2.1 2.2 Кодировки сцеплениями................ Частичный порядок на множестве.........

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

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

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 Комплекс мощных расщеплений сети......... Критические подмножества функции и равенство 1 Минимальные сети в нормированных пространствах. Общие результаты......................... 1.1 Некоторые факты из выпуклого анализа....... 1.2 Общий критерий минимальности параметрической 1.3 Критерий минимальности параметрической сети с 2 Минимальные сети на римановых многообразиях. Общие 2.3 Абсолютно и локально минимальные сети...... Минимальные сети в евклидовом пространстве R..... 3.1 Локально минимальные сети как регулярные минимальные параметрические сети............ 3.2 Единственность минимальных параметрических сетей 4 Минимальные сети на полных односвязных многообразиях 4.1 Экстремальные параметрические сети на многообразии........................... 4.2 Локально минимальные сети на многообразии как Геодезические сети на многообразии как параметрические сети в метрическом пространстве.. 4.7 Оценки количества локально минимальных сетей с Минимальные сети на манхэттенской плоскости.....

5.4 Локальное устройство минимальной параметрической сети топологии звезда............... 5.5 Мощные расщепления минимальных параметрических сетей некоторых типов.............. Комбинаторная морсовость функции для случаев 5.7 Оценки количества локальных минимумов для случаев 3, 4 и 5 граничных точек............. Некоторые примеры для случая 6 граничных точек Введение 1 Актуальность темы Цель настоящей диссертации — разработать теорию Морса, применимую к изучению минимальных сетей в метрических пространствах. Источником большинства задач, связанных с минимальными сетями, является так называемая проблема Штейнера:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 Краткое содержание диссертации В главе 1 определяются базовые понятия и объекты данной диссертации: параметрическая сеть (или просто сеть) в общем метрическом пространстве; параметризующий граф сети; граничные и подвижные вершины, граничные и внутренние ребра сети и параметризующего графа;

граница сети; количество внутренних ребер называется рангом сети и параметризующего графа; длина сети; минимальная параметрическая сеть.

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

Далее, изучаются регулярные сети, т.е. сети без вырожденных внутренних ребер, параметризованные геометрическими деревьями. Строится конфигурационное пространство всех регулярных сетей с данной границей. На этом пространстве корректно определена функция длины сети. Пространство понадобится в главе 2 при реализации программы построения теории Морса минимальных сетей.

В главе 2 формулируется общая концепция построения теории Морса для произвольных множеств и произвольных функций на них. В рамках этой концепции кратко напоминается классическая теория Морса и теория Морса для симплициальных комплексов, основы которой заложены О. Р. Мусиным в работе [12]. Определение комплекса и индекса для критической точки из работы [12] послужили отправной точкой для разработанного в этой главе комбинаторного подхода к построению теории Морса для произвольных множеств и функций на них — комбинаторной теории Морса.

С помощью результатов комбинаторной теории Морса последовательно реализуется программа построения теории Морса минимальных сетей, изложенная в разделе 1 Введения. В качестве пары множествофункция берется из главы 1 конфигурационное пространство всех регулярных сетей с данной границей и функция длины сети. К пространству и функции применяется комбинаторный подход для определения критических значений, критических точек и их индексов. Выводится равенство Морса, связывающее индексы критических значений (точек) с “топологией” пространства. На пространстве вводится некоторая фильтрация подпространствами (), которая позволяет написать несколько равенств Морса. Показывается, что все критические точки функции можно интерпретировать как минимальные параметрические сети, и обратно. Для минимальной параметрической сети определяются мощные расщепления и доказывается, что индекс критической точки можно вычислить через мощные расщепления соответствующей минимальной параметрической сети. С помощью полученных равенств Морса выводятся формулы, позволяющие вычислить количество минимальных параметрических сетей ранга через мощные расщепления минимальных параметрических сетей с меньшим рангом (более точно этот результат сформулирован ниже).

Основная задача главы 3 — показать применимость теории Морса минимальных сетей для изучения минимальных сетей в различных метрических пространствах. Особое внимание уделяется следующим пространствам: евклидовы пространства R, полные односвязные римановы многообразия с неположительной секционной кривизной и манхэттенская плоскость. Результаты теории Морса минимальных сетей позволяют получить оценки на количество локально минимальных сетей, затягивающих фиксированную границу общего положения в одном из этих пространств. Оценки подобного рода получены для локально минимальных сетей, затягивающих границу общего положения, состоящую из 4, 5 точек (случай 3 граничных точек тривиален) на двумерных полных односвязных римановых многообразий с неположительной секционной кривизной (в частности для евклидовой плоскости R2 и плоскости Лобачевского 2 ). Для манхэттенской плоскости в случае границы общего положения из 4, 5 граничных точек получены оценки на количество локально минимальных критических множеств (здесь также случай граничных точек тривиален). Кроме того, показано, что степени вершин сетей из локально минимальных критических множеств в случаях границы общего положения из 4 или 5 точек не превосходят 3. Отметим, что для границ не общего положения степень вершин таких сетей может быть равна 4. Также в этой главе найдена универсальная граница, т.е. граница, которую затягивают все комбинаторно возможные локально минимальные сети.

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

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

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

Пусть — некоторое множество и — вещественнозначная функция на. Обозначим через подмножество точек из множества, в которых значение функции не превосходит числа. Главный вопрос, на который должна отвечать теория Морса для пары (, ), можно сформулировать следующим образом: Как меняется множество с изменением числа ?

В частности, в теории Морса для пары (, ) должно быть определено что означает слово “меняется”. Так, в классической теории Морса, где — гладкое многообразие и — гладкая функция на, под “изменением” множества, которое является топологическим пространством, жество является совокупностью вершин конечного симплициального комплекса и — произвольная вещественнозначная функции на.

Здесь под “изменением” множества понимается изменение комбинаторной структуры комплекса. Комплекс по определению состоит их всех симплексов, вершины которых суть вершины из множества. Эти два примера теорий Морса подробнее рассматриваются в разделах 2 и 3 главы 2.

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

Для этого нам понадобится ввести на множестве дополнительную структуру. Рассмотрим какое-нибудь конечное покрытие множества его подмножествами, =. Покрытие = { } далее будем называть комбинаторной топологией или, сокращенно, к-топологией пространства. Пространство, снабженное комбинаторной топологией назовем комбинаторным топологическим пространством или, сокращенно, к-топологическим пространством.

Определение. Нерв к-топологии (конечного покрытия) пространства мы будем называть к-топологическим типом пространства и обозначать через ().

Замечание. Выбор подобной терминологии объясняется двумя причинами: во-первых, из любого конечного покрытия можно изготовить (хотя нам это и не понадобиться) настоящую топологию, использовав его как предбазу; и, во-вторых, техника симплициальных комплексов (в частности нервов) является одним из основных инструментов изучения чисто топологических проблем в науке, называемой комбинаторная топология, см. например [1] и [13].

Подмножество также можно считать к-топологическим пространством с индуцированной к-топологией = { }. К-топологический тип пространства мы для сокращения записи будем обозначать через. Отметим, что при 1 2 комплекс 1 можно считать подкомплексом комплекса 2. Под изменением пространства мы будем понимать изменение его к-топологического типа. И далее, мы будем изучать именно изменение комплекса при изменении параметра.

Определение. Число называется критическим значением для функции, если при прохождении параметра через изменяется к-топологический тип пространства.

В силу конечности комплекса () функция имеет конечное число критических значений. Пусть — критическое значение функции. Тогда, для любого достаточно малого > 0 комплекс + ( ) остается неизменным. Обозначим этот комплекс через + ( ). Через обозначим замыкание множества симплексов + до симплициального комплекса.

Два следующих простых утверждения дают ответ на главный вопрос, стоящий перед теорией Морса (см. выше).

Утверждение 2.1 Пусть 1, 2,..., — все критические значения функции. Тогда эти значения разбивают всю прямую R на интервалы постоянства к-топологического типа пространства : (, 1 ), Утверждение 2.2 Пусть — критическое значение функции. Парой Морса, измеряющей изменение к-топологического типа пространства при прохождении через критическое значение, является пара Другими словами, имеет место равенство: = +.

Определим теперь индексы критических значений и найдем их связь с к-топологией пространства. Индексом критического значения функции назовем следующую разность где (·) — эйлерова характеристика.

Обозначим через 0 комплекс 0, где 0 — достаточно большое по модулю отрицательное число. Согласно утверждению 2.1 такое обозначение корректно. Тогда аналогом классического равенства Морса в нашем случае является следующее утверждение.

Утверждение 2.5 Пусть 1, 2,..., — все критические значения функции. Сумма индексов всех критических значений функции равняется эйлеровой характеристике комплекса () минус эйлерова характеристика комплекса 0, т.е.

На практике вычисление критических значений функции и соответствующих пар Морса по приведенным выше определениям, носящим “глобальный” характер, крайне неэффективно. Стремление “локализовать” вычисления как в классическом случае, так и в нашем, приводит к определению критической точки функции и к понятию функции Морса (в нашем случае комбинаторной функции Морса).

Назовем стратом пространства любое пересечение 0 1 · · · элементов к-топологии пространства. Каждому симплексу из комплекса () отвечает некоторый непустой страт пространства, который мы обозначим через ().

Утверждение 2.3 Число является критическим значением функции тогда и только тогда, когда существует страт (), на котором абсолютный минимум функции равен, т.е.

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

На первом этапе “локализации” нам понадобится аналог классической функции Морса (а также симплициальной функции Морса, см. раздел главы 2). Напомним, что в классическом случае для функции Морса изменение гомотопического типа множества при прохождении через критическое значение описывается относительно просто — приклеиваются “ручки” вида (, () ). Аналогичным свойством обладает и комбинаторная функция Морса.

Определение. Комбинаторной функцией Морса на к-топологическом пространстве называется функция, для которой выполнены следующие два условия:

1. На каждом страте () функция достигает своей точной нижней грани. Обозначим через min () множество точек страта (), на которых достигается эта точная нижняя грань.

2. Для каждого критического значения комплекс представляется в виде объединения симплексов, не лежащих в (здесь симплекс рассматривается как комплекс, т.е. вместе со всеми своими гранями), причем при = выполнено включение (Иллюстрацией к этому определению служит рис. 2.3 на стр. 70.) Имеет место следующее утверждение.

Утверждение 2.7 Пусть — критическое значение комбинаторной функции Морса. Парой Морса, измеряющей изменение к-топологического типа множества при прохождении через критическое значение, является объединение “ручек” (, ). Причем пересечение двух различных “ручек” и принадлежит комплексу Если определить индекс каждой ручки равенством ind := 1 ( ). Тогда, равенство Морса (утверждение 2.5) в более “локализованном” виде можно переписать следующим образом.

Утверждение 2.8 Пусть — комбинаторная функция Морса на к-топологическом пространстве. Обозначим через совокупность ручек функции. Тогда сумма индексов всех ручек функции равна эйлеровой характеристике комплекса (), т.е.

На втором этапе “локализации” мы каждой ручке сопоставим некоторую критическую точку, определим индекс у каждой точки и вычислим индекс каждой ручки через индекс соответствующей критической точки.

Пусть — некоторая ручка функции. Выберем произвольную точку из множества min ( ) и обозначим ее ; точка будет называться каноническим представителем ручки в пространстве.

Теперь определим для произвольной точки комбинаторный потенциал или, сокращенно, к-потенциал, который мы будем обозначать через (). Симплекс принадлежит комбинаторному потенциалу () тогда и только тогда, когда значение функции в точке не является абсолютным минимумом функции в страте (). Легко заметить, что () — симплициальный комплекс.

Определение. Индексом произвольной точки из пространства назовем следующую разность Отметим, что ненулевым индексом обладают только критические точки.

Оказывается, что индекс ручки совпадает с индексом ее канонического представителя. Поэтому имеет место теорема.

Теорема 2.1 Пусть — комбинаторная функция Морса на к-топологическом пространстве. Обозначим через { } совокупность ручек функции, а через — их канонических представителей. Тогда имеет 2) Реализация программы построения теории Морса минимальных сетей.

Начнем с пп. 1) и 2) — построим конфигурационное пространство сетей с данной границей и определим на нем функцию.

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

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

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

Пусть = (, ) — ребро сети. Длину ребра по определению положим равной ((), ()). Сумму длин всех ребер сети назовем длиной сети.

Если выделено некоторое конечное подмножество в пространстве, такое что оно содержится в образе Im сети, то говорят, что сеть затягивает множество, и называют границей сети.

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

Но эту границу они “по-разному затягивают”. Из приведенного примера мы видим, что для того, чтобы полностью определить комбинаторную структуру сети с границей, нужно задать соответствие точек из границы сети некоторым вершинам ее параметризующего графа. Эти вершины называются граничными для графа, а их совокупность обозначается через. Такое соответствие : называется граничным отображением для графа. Пара (, ) называется типом сети с границей. Обозначим через [, ] множество всех сетей типа (, ).

Отметим, что каждая сеть из [, ] задается лишь положениями своих подвижных вершин, поскольку положения граничных вершин уже заданы отображением.

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

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

Если точки из границы = { } сети занумерованы числами от 1 до, то оказываются занумерованными (помеченными) и граничные вершины дерева — граничной точке соответствует граничная вершина с пометкой. Таким образом, при фиксированной границе = { } тип сети, затягивающей эту границу, определяется деревом с занумерованными (помеченными) граничными вершинами. Поэтому далее при фиксированной границе = { } у всех параметризующих деревьев сетей с границей граничные вершины будут считаться помеченными различными числами от 1 до ; а также вместо обозначения [, ] будет использоваться сокращенное обозначение [].

Подводя итог вышесказанному, мы будем считать, если не оговорено противное, что при фиксированной границе = { } все параметризующие графы сетей, затягивающих границу, являются деревьями с вершинами степени 1, которые считаются граничными и которые помеченными различными числами от 1 до, и без вершин степени 2. Такие рических деревьев с граничными вершинами обозначим через (как правило параметр ясен из контекста, поэтому мы его будем опускать).

Приступим теперь непосредственно к построению конфигурационного пространства сетей с данной границей. Рассмотрим пространство, представляющее собой несвязную сумму = []. Пространства [] будем рассматривать как подмножества этой суммы. Зададим теперь на пространстве отношение эквивалентности следующим образом.

Для этого нам понадобится операция редукции сети : по вырожденному ребру. Пусть = (, ) — вырожденное ребро сети, т.е.

() = (). “Стянем” это ребро в графе в точку. На вновь образовавшейся вершине отображение положим равной (). На неизменившихся вершинах графа отображение оставим прежним. Такая операция называется редукцией сети по вырожденному ребру (, ).

Обратная операция к редукции по вырожденному ребру называется расщеплением вершины. Две точки (сети) 1 [1 ] и 2 [2 ] будем считать эквивалентными, если и только если, проредуцировав их по всем внутренним (т.е. соединяющим две подвижные вершины) вырожденным ребрам, мы получим одну и ту же сеть.

Построим фактор-пространство = /, где — описанная выше эквивалентность. Через обозначим стандартную проекцию на фактор-пространство. Пространство состоит из всех классов эквивалентности по отношению. Опишем теперь как устроены эти классы.

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

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

Это соответствие мотивирует следующее определение.

Определение. Пространство назовем конфигурационным пространством всех регулярных сетей с данной границей.

В дальнейшем, если не оговорено противное, элементы (классы эквивалентности) пространства будут рассматриваться как регулярные сети с данной границей.

Таким образом, пп. 1) и 2) реализованы.

Для того чтобы реализовать пп. 3), 4) и 5) воспользуемся определениями и результатами комбинаторной теории Морса (см. выше).

Сначала зададим к-топологию на пространстве. Поскольку проекция : не склеивает друг с другом никакие две различные сети 1 и 2, принадлежащие пространству [], то мы имеем вложение пространства [] в пространство. Образ пространства [] при этом вложении мы обозначим через. Ясно, что =. Оказывается, имеет место более сильное равенство: =, где (3) — множество всех геометрических деревьев ранга 3, т.е. бинарных деревьев. Таким образом, последнее равенство задает нам на пространстве к-топологию = {}(3). Теперь мы можем пользоваться всеми определениями и результатами комбинаторной теории Морса.

Следующее утверждение описывает критические точки функции на пространстве.

Утверждение 2.9 Регулярная сеть является критической точкой функции на пространстве тогда и только тогда, когда — регулярная минимальная параметрическая сеть.

Напомним, что в п. 3) программы построения теории Морса минимальных сетей требовалось, чтобы локально минимальные сети являлись критическими точками функции на конфигурационном пространстве. В отличие от большинства введенных выше определений и конструкций для общего метрического пространства понятие локально минимальной сети может быть бессодержательно. Однако, в случае когда есть евклидово пространство или, более общо, полное односвязное многообразие с неположительной секционной кривизной это понятие имеет смысл. В этом случае также можно показать (см. параграф 3.1 и раздел главы 3), что локально минимальные сети на можно интерпретировать как регулярные минимальные параметрические сети с топологией бинарного дерева. Поэтому локально минимальные сети на, в силу предыдущего утверждения, являются критическими точками.

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

Сеть называется расщеплением сети, если она получена с помощью последовательности операций расщепления подвижных вершин сети ;

другими словами, сеть отличается от сети несколькими дополнительными вырожденными внутренними ребрами 1,...,. Если = 1, то расщепление называется элементарным. Каждое расщепление порождает набор так называемых производных расщеплений сети :

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

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

Пример сети с не элементарно порожденными геометрическими расщеплениями приведен в книге [29]. Следующее утверждение (в основном тексте диссертации как следствие) позволяет выразить индекс критической сети через ее мощные расщепления.

Следствие 2.4 Пусть — регулярная минимальная параметрическая сеть ранга с элементарно порожденными расщеплениями. Тогда Пусть теперь функция на пространстве является комбинаторной функцией Морса. Перепишем также равенство Морса (теорема 2.1) в терминах теории минимальных сетей. Напомним, что в равенстве Морса фигурировали индексы канонических представителей ручек.

Оказывается, каждой ручке можно сопоставить некоторое подмножество критических точек, которое обозначается через ( ), где — тип канонического представителя. Критические подмножества ( ) попарно не пересекаются и в объединении дают все множество критических точек. Подробное описание множеств ( ) без привлечения языка комбинаторной теории Морса см. в разделе 5 главы 2. Отметим здесь лишь то, что для рассматриваемых в главе 3 примеров множества ( ) являются связными компонентами множества критических точек, а сеть является в множестве ( ) сетью минимального ранга. Рангом критического подмножества ( ) называется ранг сети. Обозначим через совокупность критических подмножеств ранга. Тогда равенство Морса выглядит следующим образом.

Предложение 2.6 Пусть — комбинаторная функция Морса на пространстве, и пусть все канонические представители критических подмножеств ( ) являются сетями с элементарно порожденными расщеплениями. Тогда имеет место формула число. Аналогично, через будем обозначать комплекс, где > 0 — любое достаточно малое число.

Из определения критического значения и предложения 2.1 вытекает следующее утверждение, являющееся аналогом первой части основного результата классической теории Морса (теорема C1):

Утверждение 2.1 Пусть 1, 2,..., — все критические значения функции. Тогда эти значения разбивают всю прямую R на интервалы постоянства к-топологического типа пространства : (, 1 ), Согласно определению приращения в критической точке и введенных обозначений комплекс равен +. И поскольку +, то имеет место равенство Таким образом, получаем аналог второй части основного результата классической теории Морса (теорема C2) Утверждение 2.2 Пусть — критическое значение функции. Парой Морса, измеряющей изменение к-топологического типа пространства при прохождении через критическое значение, является пара Другими словами, имеет место равенство: = +.

Стратификация пространства 4. Определение. Назовем стратом к-топологического пространства любое пересечение 0 1 · · · элементов к-топологии пространства. Каждому симплексу = (0, 1,..., ) из комплекса () отвечает некоторый непустой страт 0 1 · · ·, который мы обозначим через ().

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

Лемма 2.2 Пусть ( ) и ( ) — два страта множества, причем их пересечение ( ) ( ) не пусто. Тогда в комплексе () существует симплекс, такой что симплексы и являются его гранями и () ( ) ( ).

Доказательство. Пусть симплексу отвечает непустое пересечение 0 1 · · ·, а симплексу — непустое пересечение · · ·. Согласно условию леммы, пересечение 0 · · · · · · не пусто, и поэтому оно задает некоторый симплекс из комплекса ().

Ясно, что симплекс — искомый.

Следствие 2.1 Пусть () — некоторый страт множества. Тогда существует симплекс, такой что любой симплекс, для которого ( ) = (), является гранью Для страта () симплекс из следствия 2.1 назовем максимальным симплексом, задающим страт ().

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

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

Лемма 2.4 Пересечение двух существенных симплексов комплекса () также является существенным симплексом.

Доказательство. Пусть — существенный симплекс, которому отвечает страт (непустое пересечение) () = 1 · · ·. Из определения максимального симплекса следует, что при добавлении к этому пересечению еще одного элемента общее пересечение уменьшится. Рассмотрим еще одни существенный симплекс, которому отвечает страт (непустое пересечение) ( ) = 1 · · · Тогда симплексу = отвечает некоторый страт (), являющийся пересечением элементов, входящих как в симплекс, так и в симплекс. Для определенности положим, что это пересечение () = 1 · · · = 1 · · ·.

Допустим, что симплекс не является максимальным для страта ().

Тогда существует элемент из покрытия множества, не входящий в какое-то из двух начальных пересечений, скажем в первое, и такой что Это означает, что симплекс не является максимальным симплексом для страта () = 1 · · ·, что противоречит исходному предположению.

Таким образом, симплекс = является максимальным симплексом для страта (), и, следовательно, является существенным симплексом для комплекса ().

4.5 Понятие критической точки Введем теперь понятие критической точки для функции.

Согласно лемме 2.1, мы считаем комплекс подкомплексом комплекса (). Очевидно, что симплекс () будет принадлежать комплексу тогда и только тогда, когда пересечение множества со стратом () не пусто.

Пусть — критическое значение функции. Это означает, что в комплексе + появился симплекс, которого не было в комплексе.

Другими словами, пересечение страта () с множеством +, не пусто, а с множеством — пусто, где — достаточно малое положительное число. Таким образом, получаем лемму Лемма 2.5 Критическое значение является точной нижней гранью функции в стратах, отвечающих симплексам из +.

и, как следствие, утверждение Утверждение 2.3 Число является критическим значением функции тогда и только тогда, когда существует страт (), на котором абсолютный минимум функции равен, т.е.

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

Критическим множеством Crit () для функции, отвечающим критическому значению, назовем объединение критических точек, таких что () =.

Замечание. Вообще говоря, критическое множество Crit () может быть и пустым.

Утверждение 2.4 Точка является критической точкой функции тогда и только тогда, когда она является точкой абсолютного минимума функции на минимальном страте для этой точки.

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

В обратную сторону утверждение следует из определения критической точки.

Комбинаторный потенциал точки из 4. Определим для произвольной точки комбинаторный потенциал () или, сокращенно, к-потенциал ().

Определение. Симплекс принадлежит комбинаторному потенциалу () тогда и только тогда, когда значение функции в точке не является точной нижней гранью функции в страте (), т.е.

Мы будем говорить, что для точки по страту () можно уменьшить функцию.

Легко заметить, что () — симплициальный комплекс.

Определение. Индексом произвольной точки из пространства назовем следующую разность (ср. с определением индекса вершины из раздела 3 настоящей главы).

Лемма 2.6 Пусть () — минимальный страт для точки, () =, а — максимальный симплекс, задающий этот страт. Тогда В последнем равенстве симплекс рассматривается как симплициальный комплекс, т.е. вместе со всеми своими гранями.

Доказательство. Сначала докажем включение ().

Пусть — некоторый симплекс из к-потенциала (). Тогда, согласно определению к-потенциала, в страте ( ) имеется некоторая точка, такая что ( ) <. Следовательно, симплекс принадлежит комплексу. С другой стороны, страт ( ) содержит точку, а значит и минимальный страт () для точки. Поэтому, согласно лемме 2.2 и определению максимального симплекса, симплекс является гранью симплекса. Таким образом, включение () доказано.

Докажем обратное включение (). Пусть симплекс принадлежит пересечению. Из принадлежности симплекса комплексу следует, что ( ) (). С другой стороны, поскольку принадлежит комплексу, то в страте ( ) существует точка, такая что ( ) <. Теперь из определения к-потенциала () вытекает (). Таким образом, обратное включение также доказано.

Предложение 2.2 Пусть — некоторая точка из множества, и — максимальный симплекс, задающий минимальный страт для точки. Точка является критической точкой функции тогда и только тогда, когда ().

Доказательство. Пусть — критическая точка функции. Тогда, согласно лемме 2.6, комплекс () является подкомплексом симплекса (как комплекса). С другой стороны, симплекс (как симплекс) не принадлежит к-потенциалу (). В самом деле, значение функции в критической точке равно точной нижней грани функции в страте (), следовательно,.

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

Следствие 2.2 Пусть — некритическая точка функции, и — максимальный симплекс, задающий минимальный страт для точки.

Вычисление ( ) В разделе 5 настоящей главы нам понадобится вычислять индексы критических точек или, эквивалентно, эйлеровы характеристики их к-потенциалов. Напомним, что по определению, эйлерова характеристика комплекса равна следующей альтернированной сумме: количество 0мерных симплексов – количество одномерных симплексов + количество 2-мерных симплексов и т.д. Из этого определения видно, что мы вынуждены знать количество -мерных симплексов комплекса для любого.

Такая информация часто бывает трудно вычислима. Поэтому мы поступим следующим образом. Представим комплекс в виде объединения стягиваемых (в геометрическом смысле) подкомплексов, так что все пересечения этих подкомплексов также стягиваемы, тогда () = количество подкомплексов – количество их одинарных пересечений + количество двойных пересечений и т.д.

Уточним эту идею. Рассмотрим некоторый комплекс. Симплекс назовем наибольшим симплексом комплекса, если не является гранью никакого другого симплекса из комплекса. Возьмем теперь в качестве совокупности стягиваемых комплексов набор наибольших симплексов комплекса. Этот набор { } образует покрытие комплекса. Двойственным комплексом * к комплексу назовем нерв покрытия комплекса его наибольшими симплексами. Из алгебраической топологии известно, см. например [16], что комплексы и * когомологичны; в частности, () = ( * ).

Обратимся теперь к комплексам, являющимся подкомплексами комплекса (), и изучим как устроен двойственный к комплекс.

Определение. Двойственный комплекс () к к-потенциалу () будем называть ко-потенциалом точки.

Вершины комплекса суть наибольшие симплексы комплекса.

Обозначим через страт ( ), соответствующий наибольшему симплексу комплекса (). Поскольку (), то по страту для точки можно уменьшить функцию. В силу того, что симплекс — наибольший симплекс в комплексе (), страт не содержит в себе как собственное подмножество никакого другого страта, по которому для точки можно уменьшить функцию.

Рассмотрим наибольшие симплексы 1,..., комплекса ().

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

По лемме 2.4, пересечение существенных симплексов 1,..., также будет существенным симплексом, т.е. максимальным симплексом для (). Поскольку симплекс является гранью каждого из симплексов 1,...,, то страт () содержит в себе страты 1,...,. Причем () — наименьший по включению страт, содержащий в себе страты Теперь можно считать, что вершинами ко-потенциала () являются наименьшие по включению страты, по которым для точки можно уменьшить функцию. А ( 1)-мерным симплексом с вершинами 1,..., является наименьший по включению страт, содержащий страты 1,...,. Обозначим совокупность ( 1)-мерных симплексов (стратов) через. Таким образом, учитывая, что ( ()) = ( ()), получаем предложение Предложение 2.3 Имеет место равенство 4.7 Индексы критических значений и равенство Определение. Индексом критического значения назовем следующую где (·) — эйлерова характеристика.

Обозначим через 0 комплекс 0, где 0 — достаточно большое по модулю отрицательное число. Согласно утверждению 2.1 такое обозначение корректно.

Утверждение 2.5 Пусть 1, 2,..., — все критические значения функции. Сумма индексов всех критических значений функции равняется эйлеровой характеристике комплекса () минус эйлерова характеристика комплекса 0, т.е.

Доказательство. В силу равенства из утверждения 2.2 и аддитивного свойства эйлеровой характеристики, для каждого критического значения имеем Учитывая определение индекса критического значения и утверждение 2.1, просуммируем это равенство по от 1 до и получим Осталось заметить, что + = () и 1 = 0.

4.8 Неравенства Морса Равенство из утверждения 2.5 носит название равенство Морса. Имеется, однако, более сильная теорема (см. ниже), использующая технику полиномов Пуанкаре. Эта техника позволяет помимо равенства Морса получать также и неравенства Морса (подробнее см. [19]).

Пусть — критическое значение функции. Рассмотрим группы гомологий * ( +, ). И рассмотрим целые числа Определение. Полиномом Пуанкаре функции на назовем полином Утверждение 2.6 Пусть (, ) и (( (), 0 ), ) — полиномы Пуанкаре функции и пары комплексов ( (), 0 ). Тогда разность делится на 1 + и отношение полиномов ( )/(1 + ) является полиномом с неотрицательными целыми коэффициентами.

Доказательство этого утверждения проводится по той же схеме, что и доказательство аналогичной теоремы Морса-Смейла из [19], сс. 405–407.

Из утверждения 2.6 можно вывести утверждение 2.5 следующим образом. Запишем равенство (1 + )() = () (). Подставляя в это равенство = 1, получим Утверждение 2.6 можно рассматривать как обобщение классических неравенств Морса. Мы в дальнейшем не будем пользоваться этим утверждением, а приводим его здесь лишь для полноты картины.

4.9 Комбинаторная функция Морса Определение. Комбинаторной функцией Морса на к-топологическом пространстве называется функция, для которой выполнены следующие два условия:

1. На каждом страте () функция достигает своей точной нижней грани. Обозначим через min () множество точек страта (), на которых достигается эта точная нижняя грань.

2. Для каждого критического значения комплекс представляется в виде объединения симплексов, не лежащих в (здесь симплекс рассматривается как комплекс, т.е. вместе со всеми своими гранями), причем при = выполнено включение Иллюстрацией к этому определению служит рис. 2.3.

Также как в классическом и симплициальном случаях, комбинаторная функция Морса позволяет в некотором смысле локализовать описание изменений, происходящих с комбинаторным типом множества при прохождении через критическое значение. Перепишем утверждение 2.2 в более “локализованном” виде Утверждение 2.7 Пусть — критическое значение комбинаторной функции Морса. Парой Морса, измеряющей изменение к-топологического типа множества при прохождении через критическое значение, является объединение “ручек” (, ). Причем пересечение двух различных “ручек” и принадлежит комплексу Определение. Симплексы назовем ручками комбинаторной функции Морса, а пересечение назовем подошвой ручки. Иногда под ручкой мы будем понимать пару (, ).

Замечание. Ручки комбинаторной функции Морса — суть максимальные симплексы совокупности, на которой индуцируется естественное отношение частичного порядка между симплексами “являться гранью”.

Лемма 2.7 Если для каждого страта () к-топологического пространства множество минимумов min () одноточечно, то функция на пространстве является комбинаторной функцией Морса.

Доказательство. Очевидно, для функции первое условие из определения комбинаторной функции Морса выполняется.

Пусть — критическое значение функции. Рассмотрим два максимальных симплекса 1 и 2 из. Обозначим, через 1 и точки из min (1 ) и min (2 ) соответственно. Заметим, что 1 = 2.

В самом деле, если бы точки 1 и 2 совпадали, то пересечение стратов (1 ) и (2 ) было бы не пусто. Поэтому, согласно лемме 2.2 существовал бы симплекс, такой что 1 и 2 являются его гранями и ( ) = (1 ) (2 ). С другой стороны, принадлежит совокупности, поскольку inf () =. Следовательно, 1 и 2 не были бы максимальными симплексами.

Покажем теперь, что пересечение = 1 2 этих симплексов не принадлежит совокупности. Предположим противное, т.е. что. Тогда точная нижняя грань функции на страте () равна. Более того, поскольку () содержит в себе как страт (1 ), так и страт (2 ), то множество минимумов min () для этого страта содержит по крайне мере две точки. Последнее противоречит условию леммы. Таким образом, для функции второе условие из определения комбинаторной функции Морса также выполняется.

По определению, индекс каждой ручки положим равным единице минус эйлерова характеристика ее подошвы, т.е. ind = 1 ( ). Тогда имеет место следующее утверждение.

Утверждение 2.8 Пусть — комбинаторная функция Морса на к-топологическом пространстве. Обозначим через совокупность ручек функции. Тогда сумма индексов всех ручек функции равна эйлеровой характеристике комплекса (), т.е.

Доказательство. Пусть — критическое значение функции. Тогда из определения ручек функции и аддитивности эйлеровой характеристики следует равенство Просуммировав это равенство по всем критическим значениям функции и воспользовавшись утверждением 2.5, получим По условию, является комбинаторной функцией Морса, и поэтому достигает своей точной нижней грани на каждом страте пространства. Следовательно, достигает своей точной нижней грани и на всем пространстве. Таким образом, комплекс 0 пуст и мы имеем доказываемое равенство.

Напомним, что в классической теории Морса каждому критическому значению функции Морса соответствовала только одна ручка. Это обуславливалось тем, что функции Морса всюду плотны в пространстве гладких функций, т.е. любую гладкую функцию можно немного пошевелить, чтобы она превратилась в функцию Морса. В нашем же случае, при комбинаторном подходе к построению теории Морса приходится рассматривать функции, для которых критическому значению отвечает несколько ручек. Для изучаемых в главе 3 примеров малым шевелением функции удается ее сделать лишь комбинаторной функцией Морса (в смысле данного определения). А дальнейшее “разнесение” ручек по разным критическим значением, по-видимому является достаточно трудной теоремой.

Однако, наличие нескольких ручек для одного критического значения ничему не препятствует, поскольку, как правило, критические значения изучаются посредством изучения соответствующих критических точек и поведения функции в окрестности этих критических точек. Переход от критических значений к критическим точкам сводит изучение поведения функции “в большом” к изучению поведения функции “в малом”, в частности, сводит вычисление индексов критических значений и ручек к вычислению индексов критических точек. Напомним также, что в классической теории Морса каждой ручке функции Морса соответствовала единственная критическая точка. В нашем случае это для некоторых примеров выполняется, а для некоторых нет, см. главу 3. Перейдем теперь к описанию множества критических точек комбинаторной функции Морса.

Для каждой грани симплекса, которая не принадлежит комплексу, точная нижняя грань функции в страте () равна.

Поскольку является комбинаторной функцией Морса, то точная нижняя грань в страте () достигается. Обозначим через ( ) объединение критических точек из множеств min () по всем симплексам Лемма 2.8 Множества ( ) при разных попарно не пересекаются и в объединении дают все критическое множество Crit ().

Доказательство. Предположим, что при = множества ( ) и ( ) пересекаются, т.е. существуют симплексы и, такие что пересечение соответствующих множеств минимумов min ( ) и min ( ) не пусто. Пусть — некоторая точка из этого пересечения. Обозначим через () минимальный страт для точки, где — максимальный симплекс, задающий страт (). Согласно следствию 2.1, симплексы и являются гранями симплекса. Поскольку () ( ) ( ), то точная нижняя грань функции на страте () равна = (). Следовательно, симплекс, для которого и — грани, принадлежит комплексу.

Этот факт противоречит определению симплексов и. Вторая часть леммы доказывается следующим образом. Пусть — критическая точка из критического множества Crit (). Тогда, по определению критической точки, она принадлежит некоторому множеству min (). Поскольку () =, то. Следовательно, симплекс является гранью для некоторого симплекса. Таким образом, Итак, каждой ручке отвечает критическое подмножество ( ) Crit (). Однако, для вычисления индекса ручки не требуется вычислять индексы всех критических точек из ( ); достаточно выбрать лишь одного представителя критического подмножества ( ). Выберем произвольную точку из множества min ( ) ( ) и обозначим ее ; точка будет называться каноническим представителем ручки в критическом множестве Crit ().

Лемма 2.9 Страт ( ) является минимальным стратом для любого канонического представителя ручки в критическом множестве Crit (), а симплекс является максимальным симплексом, задающим страт ( ).

Доказательство. Пусть — некоторый канонический представитель ручки. Предположим, что ( ) — не минимальный страт для точки. Тогда, воспользовавшись определением минимального страта и леммой 2.2, можно утверждать, что существует некоторый страт (), такой что () ( ) и — грань симплекса. Поскольку — критическая точка, то значение функции в этой точке, согласно лемме 2.5, является абсолютным минимумом функции в страте ( ), а значит является абсолютным минимумом и в страте (). Следовательно, симплекс, для которого — грань, принадлежит совокупности +. Но этого быть не может, поскольку — комбинаторная функция Морса.

Из аналогичных рассуждений вытекает и вторая часть леммы.

Лемма 2.10 Минимальный страт для любой точки из критического подмножества ( ) содержит страт ( ).

Доказательство. Пусть ( ), т.е. точка принадлежит некоторому множеству min (), где — грань симплекса. Обозначим через ( ) минимальный страт для точки. Поскольку () ( ) и min (), то принадлежит множеству min ( ). Следовательно, симплекс должен принадлежать совокупности, т.е.

одной из ручек функции, а множество min ( ) одному из соответствующих этим ручкам критических подмножеств. Но пересечение min ( ) ( ) содержит точку. Следовательно, симплекс является гранью симплекса и имеет место включение ( ) ( ).

Предложение 2.4 Пусть — канонический представитель ручки в критическом множестве Crit (). Тогда к-потенциал ( ) точки совпадает с подошвой ручки и имеет место равенство ind = ind.

Доказательство. Совпадение к-потенциала ( ) с подошвой вытекает из лемм 2.9 и 2.6. В свою очередь, равенство ind = ind следует из этого совпадения и определений соответствующих индексов.

Таким образом, для комбинаторной функции Морса, чтобы описывать изменение к-топологического типа множества при прохождении числа через критическое значение, достаточно знать лишь нескольких критических точек из множества Crit (), а именно — канонических представителей. В самом деле, согласно утверждению 2.7, изменение комплекса при прохождении через определяется приклейкой ручек к комплексу по своим подошвам. Каждая ручка, согласно лемме 2.9, определяется как максимальный симплекс, задающий минимальный страт для точки, а подошва этой ручки, согласно предложению 2.4, — как к-потенциал ( ). Вычисление к-потенциалов точек для многих интересных случаев, см. главу 3 представляет собой локальную процедуру.

Теперь из утверждения 2.8 и предложения 2.4 вытекает следующая теорема Теорема 2.1 Пусть — комбинаторная функция Морса на к-топологическом пространстве. Обозначим через { } совокупность ручек функции, а через — их канонических представителей. Тогда имеет 5 Теория Морса минимальных сетей В этом разделе мы реализуем программу построения теории Морса для минимальных сетей, сформулированную во Введении. В качестве пространства мы возьмем конфигурационное пространство всех регулярных сетей, затягивающих данную границу, а в качестве функции — функцию длины сети. Напомним, что пространство и функция были построены в разделе 3 главы 1. В настоящем разделе мы превратим пространство в к-топологическое пространство и воспользуемся результатами комбинаторной теории Морса из предыдущего раздела. В частности, ее количественным результатом — равенством Морса. Оказывается, что для пространства можно написать несколько равенств Морса, связывающих его к-топологический тип с критическими точками. Этот набор равенств Морса мы перепишем в более естественных для теории минимальных сетей терминах и выведем полезные для этой теории формулы.

Пространство как к-топологическое пространство К-топология на пространстве Пусть (, ) — некоторое метрическое пространство и = { } — фиксированная граница в пространстве. Рассмотрим конфигурационное пространство всех регулярных сетей, затягивающих данную границу, и функцию длины сети. Напомним, что пара (, ) была построена в разделе 3 главы 1. Также напомним, см. следствие 1.2, что пространство обладает конечным покрытием = {}(3), где (3) — множество геометрических бинарных деревьев с граничными вершинами. Покрытие задает на пространстве к-топологию.

Теперь мы можем воспользоваться результатами комбинаторной теории Морса из раздела 4 настоящей главы, где в качестве множества берется пространство, а в качестве функции — функция.

Комбинаторные свойства комплекса ( ) Изучим теперь комбинаторные свойства к-топологического типа пространства.

Лемма 2.11 Комплекс ( ) является симплексом размерности (2(2))!

22 (2)!

Доказательство. Поскольку каждый лист (элемент покрытия ) содержит в себе страт 0, где 0 — геометрическое дерево топологии звезда, то пересечение всех листов пространства не пусто. Следовательно, комплекс ( ) является симплексом. Вершины этого симплекса суть листы пространства, количество которых равно |(3) | и, по утверждению 1.2, равно 2(2(2))!.

Поскольку по утверждению 1.3 и лемме 2.3 имеются взаимнооднозначные соответствия между стратами пространства и геометрическими деревьями из множества и между стратами пространства и существенными симплексами комплекса ( ), то мы получаем лемму Лемма 2.12 Имеется взаимнооднозначное соответствие между существенными симплексами комплекса ( ) и геометрическими деревьями из.

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

Доказательство. Включение выполняется тогда и только тогда, когда когда выполняется обратное включение = ( ) () =. В свою очередь, последнее включение выполняется тогда и только тогда, когда верно неравенство.

5.2 Критические точки и критические значения Утверждение 2.9 Регулярная сеть является критической точкой функции на пространстве тогда и только тогда, когда — регулярная минимальная параметрическая сеть.

Доказательство. Пусть — критическая точка (регулярная сеть) функции. Обозначим через минимальный страт для точки. Согласно лемме 1.10, сеть имеет тип. По утверждению 2.4, в точке функция достигает своего абсолютного минимума на страте, т.е.

() = inf ( ). Следовательно, для сети выполняется равенство () = inf ( ). Таким образом, регулярная сеть является минимальной параметрической сетью типа.

Обратно. Пусть регулярная сеть типа является минимальной параметрической сетью, т.е. () = inf ( ). Тогда, по лемме 1.10, страт является минимальным стратом для сети, и выполнено равенство () = inf ( ). Следовательно, согласно утверждению 2.4, регулярная сеть — критическая точка функции.

Следствие 2.3 Пусть метрическое пространство и граница таковы, что для любого типа существует соответствующая минимальная параметрическая сеть []. Тогда критические значения функции — это длины минимальных параметрических сетей.

5.3 Комбинаторные и геометрические расщепления Определение. Пусть — некоторая параметрическая сеть. Любая сеть, полученная из сети некоторой последовательностью расщеплений подвижных вершин, называется комбинаторным расщеплением сети.

Элементарным расщеплением сети назовем расщепление, которое отличается от сети лишь одним дополнительным ребром (см. замечание на стр. 38). Пусть — некоторое комбинаторное расщепление сети. Обозначим через 1,..., ребра сети, которых нет в сети. Этот набор ребер порождает набор элементарных расщеплений 1,..., сети следующим образом: у сети по сравнению с сетью одно новое ребро. Элементарные расщепления 1,..., сети назовем производными расщеплениями для расщепления сети.

Определение. Пусть [ ] — комбинаторное расщепление сети.

Если сеть не является минимальной параметрической сетью в классе [ ], тогда эту сеть назовем геометрическим расщеплением сети. Также будем говорить, что расщепление может уменьшить длину сети Определение. Комбинаторное расщепление сети назовем мощным расщеплением, если все его производные расщепления являются геометрическими (могут уменьшить длину сети ).

Пусть — некоторая сеть с границей в пространстве. Рассмотрим какое-либо геометрическое расщепление. Если для сети у каждого ее геометрического расщепления существует производное расщепление, которое является геометрическим, то тогда мы будем называть сеть сетью с элементарно порожденными геометрическими расщеплениями. Пример сети с не элементарно порожденными геометрическими расщеплениями приведен в книге [29].

5.4 Комплекс мощных расщеплений сети Пусть — некоторая параметрическая сеть. Построим комплекс мощных расщеплений сети, который мы обозначим через (). Обозначим через 1,..., все элементарные геометрические расщепления сети. По определению положим геометрические расщепления 1,..., вершинами комплекса (). Также по определению комплекс () содержит ( 1)-мерный симплекс (1,..., ), если и только если существует мощное расщепление сети, такое что сети 1,..., образуют полный набор производных расщеплений для сети. Таким образом, (1)мерные симплексы комплекса () — это мощные расщепления сети с дополнительными внутренними ребрами.

Предложение 2.5 Пусть — регулярная минимальная параметрическая сеть с элементарно порожденными геометрическими расщеплениями. Тогда комплекс мощных расщеплений () сети изоморфен ее ко-потенциалу ().

Доказательство. Поскольку — регулярная минимальная параметрическая сеть, то, согласно утверждению 2.9, сеть является критической точкой функции длины на пространстве. Напомним (см. параграф 4.6), что вершинами ко-потенциала () критической точки являются наименьшие по включению страты, по которым можно уменьшить длину сети. Покажем, что каждый страт определяет элементарное геометрическое расщепление [ ] сети. Предположим, что расщепление [ ] получено из добавлением нескольких (более одного) ребер. Рассмотрим все производные расщепления,..., для расщепления. Поскольку — сеть с элементарно порожденными расщеплениями, то среди расщеплений,..., найдется одно, скажем [ ], которое может уменьшить длину сети. Тогда соответствующий страт, по которому можно уменьшить длину сети, строго содержится в страте. Следовательно, страт не является наименьшим по включению стратом, по которому можно уменьшить длину сети, что противоречит определению страта. Таким образом, страт определяет элементарное геометрическое расщепление Верно и обратное. Обозначим через тип сети. Каждое элементарное геометрическое расщепление [ ] сети определяет некоторый наименьший по включению страт, по которому можно уменьшить длину сети. В самом деле, не существует геометрического дерева для которого выполняются строгие неравенства > >. Следовательно, не существует страта, для которого были бы выполнены строгие включения.

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

Напомним также, что ( 1)-мерным симплексом с вершинами 1,..., ко-потенциала () является наименьший по включению страт, содержащий страты 1,...,. Из этого определения страта и из леммы 1.8 следует, что дерево содержит ровно дополнительных ребер (по сравнению с деревом ), определяемых деревьями 1,...,. Другими словами, геометрические расщепления 1 [1 ],..., [ ] образуют полный набор производных расщеплений для комбинаторного расщепления [ ] сети. Таким образом, комбинаторное расщепление является мощным расщеплением сети.

Следовательно, каждому (1)-мерному симплексу ко-потенциала () соответствует ( 1)-мерный симплекс комплекса (). Проведя вышеизложенное рассуждение в обратном порядке, мы получим, что это соответствие взаимнооднозначное.

Рассмотрим снова регулярную минимальную параметрическую сеть с элементарно порожденными расщеплениями. Пусть ранг сети равен. Обозначим через () совокупность всех мощных расщеплений сети, ранг которых равен. Тогда из предложения 2.5 вытекает следующая лемма Лемма 2.14 Количество ( 1)-мерных симплексов ко-потенциала () равно количеству мощных расщеплений сети, ранг которых равен +, т.е.

Из этой леммы и предложения 2.3 получаем следствие Следствие 2.4 Пусть — регулярная минимальная параметрическая сеть ранга с элементарно порожденными расщеплениями. Тогда 5.5 Критические подмножества функции и равенство Морса Опишем теперь как устроены критические подмножества критических множеств Crit (). В параграфе 4.9 раздела 4 настоящей главы для комбинаторных функций Морса критические подмножества отвечали ручкам рассматриваемой функции. В данном пункте мы для случая пространства и функции дадим описание критических подмножеств в терминах, более близких к теории минимальных сетей.

Разбиение критического множества Crit () на критические подмножества ( ) можно описать другим, более непосредственным, способом, не апеллируя к ручкам функции.

Рассмотрим множество всех регулярных минимальных параметрических сетей длины. Согласно утверждению 2.9, это множество совпадает с критическим множеством Crit (). Рассмотрим также совокупность () всех геометрических деревьев, параметризующих сети из Crit (). Выделим в совокупности (), как в частично упорядоченном множестве, максимальные элементы. Для каждого максимального дерева рассмотрим множество ( ) всех сетей из Crit (), параметризующее дерево которых меньше или равно дереву. Сеть из Crit () типа назовем каноническим представителем множества ( ). Очевидно, что объединение всех множеств ( ) по всем максимальным деревьям совпадает с критическим множеством Crit (). Лемма 2.15 Пусть функция в каждом страте () достигает своего минимума. Тогда максимальные симплексы в совокупности взаимнооднозначно соответствуют максимальным деревьям из ().

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

Рассмотрим множество минимумов min (). По условию, оно не пусто. Возьмем какую-нибудь сеть из min (). Поскольку, симплекс является максимальным симплексом в совокупности, то страт () = является минимальным стратом для сети. Следовательно, по лемме 1.10, тип сети равен. Таким образом, дерево принадлежит совокупности ().

Покажем, что — максимальное дерево в совокупности (). В самом деле, предположим, что не является максимальным деревом, т.е. в критическом множестве Crit () существует сеть типа, такого что <. Тогда существенный симплекс, соответствующий дереву, принадлежит совокупности и строго содержит симплекс, что противоречит максимальности симплекса.

Проведя рассуждения в обратную сторону, получим окончательное утверждение леммы.

Лемма 2.16 Функция на пространстве является комбинаторной функцией Морса тогда и только тогда, когда функция на каждом страте достигает своего минимума и критические подмножества ( ) критических множеств Crit () попарно не пересекаются.

Доказательство. Согласно лемме 2.15, максимальные симплексы в совокупности взаимнооднозначно соответствуют максимальным деревьям из (). Пусть 1 и 2 — два произвольных максимальных симплекса в совокупности. Обозначим через 1 и 2 соответствующие этим симплексам максимальные деревья из (). По определению, функция является комбинаторной функцией Морса тогда и только тогда, когда в каждом страте функция достигает своего минимума и пересечение любых двух максимальных симплексов 1 и 2 из совокупности либо пусто, либо принадлежит комплексу. Последнее означает, что в совокупности не существует существенного симплекса, принадлежащего как 1, так и 2. Это равносильно следующему условию: в критическом множестве Crit () не существует сети с параметризующим деревом, таким что 1 и 2. Что, в свою очередь, равносильно непересечению критических подмножеств (1 ) и (2 ).

Лемма 2.17 Если — комбинаторная функция Морса, то разбиение критического множества Crit () на критические подмножества ( ) совпадает с разбиением Crit () на критические подмножества ( ). Причем, если ( ) = ( ), то является геометрическим деревом, соответствующим симплексу (в смысле леммы 2.12).

Доказательство. Пусть — максимальный симплекс из совокупности. По лемме 2.15, симплексу соответствует максимальное дерево из ().

Сеть принадлежит критическому подмножеству ( ) тогда и только тогда, когда найдется существенный симплекс, такой что min () и страт () является минимальным стратом для сети. Последнее, в свою очередь, согласно определению критического множества Crit () и утверждению 2.4, выполняется тогда и только тогда, когда тип сети, соответствующий симплексу, меньше либо равен дереву и Crit (), т.е. ( ).

Назовем рангом критического подмножества ( ) ранг дерева.

Это число равно наименьшему рангу представителей (сетей) из ( ) — рангу канонического представителя. Обозначим через совокупность критических подмножеств ранга, взятую по всем критическим множествам Crit () функции. Следующее предложение в теории Морса минимальных сетей можно считать аналогом равенства Морса.

Предложение 2.6 Пусть — комбинаторная функция Морса на пространстве, и пусть все канонические представители критических подмножеств ( ) являются сетями с элементарно порожденными расщеплениями. Тогда имеет место формула образом мы показали, что |1 + 2 + 3 | < 1, если прямой, относительно которой все вектора 1, 2, 3 лежат по одну сторону, не существует.

Отсюда следует необходимость.

Подсчитаем теперь количество элементарных геометрических расщеплений сети 0. Могут быть два случая.

1) У сети 0 есть вырожденное граничное ребро. Пусть, без ограничения общности, это ребро будет инцидентно граничной вершине 1 (см.

рис. 3.2).

Так как 0 является минимальной параметрической сетью, то из критерия 3.3 вытекает, что сумма единичных направляющих векторов выходящих из вершины 1 ребер 1 2, 1 3, 1 4 по модулю меньше либо равна 1. Выберем среди трех углов 2 1 3, 2 1 4, 3 1 4 наименьший. Пусть для определенности это будет угол 2 1 3. Его градусная мера должна быть меньше 120 (равенства быть не может, так как мы рассматриваем только типичные границы). Проведем через точку 1 две прямые (2 ) и (3 ), тогда, как следует из леммы 3.8, ребро должно лежать в замыкании внутренности угла 1. Может быть два варианта (см. рис. 3.2).

) Оба угла 2 1 4, 3 1 4 120. Тогда, используя критерий 3.3 и лемму 3.7, получаем, что только расщепление не является минимальной параметрической сетью, а значит может уменьшить длину сети 0.

Следовательно, в данном случае сеть 0 имеет только одно элементарное геометрическое расщепление.

) Один из углов, например 2 1 4, меньше 120, а другой 3 1 4 — больше 120. Тогда, используя критерий 3.3 и лемму 3.7, получаем, что сети и не являются минимальными параметрическими сетями, а сеть 0 — является. Следовательно, в данном случае сеть 0 имеет ровно два элементарных геометрических расщепления.

2) У сети 0 нет вырожденных граничных ребер.

ходящих из подвижной вершины ребер 1, 2, 3, 4 равна 0. Тогда эти четыре ребра разбиваются на пары ребер, лежащих на одной прямой, например так, как показано на рис. 3.3. Может быть два варианта (см. рис. 3.3).

) Среди четырех углов +1 (здесь считаем, что 5 = 1 ) есть угол, например 3 4, градусная мера которого меньше или равна 60.

Тогда, используя критерий 3.3 и лемму 3.7, получаем, что только сеть 0 не является минимальной параметрической сетью, а остальные — и, — являются. Следовательно, в данном случае сеть 0 имеет только одно элементарное геометрическое расщепление.

) Среди четырех углов +1 (здесь считаем, что 5 = 1 ) нет угла, градусная мера которого меньше или равна 60, т.е. градусная мера всех этих углов строго меньше 120. Тогда, используя критерий 3.3 и метрическими сетями, а сеть — является. Следовательно, в данном случае сеть 0 имеет ровно два элементарных геометрических расщепления.

Итак, суммируя результаты случаев 1) и 2), получаем, что сеть имеет либо 1, либо 2 элементарных геометрических расщепления. Следовательно, имеется либо 1, либо 2 регулярных минимальных параметрических сети с бинарной топологией. Таким образом, из леммы 3.2 вытекает следующее утверждение Утверждение 3.6 Количество локально минимальных сетей, затягивающих типичную границу из 4 точек на евклидовой плоскости, может быть равно либо 1, либо 2.

Случай пяти граничных точек В последнем рассматриваемом нами случае граница будет состоять из пяти точек общего положения, = { }5. В этом случае, согласно таблице на стр. 45, имеется 1 геометрическое дерево 0 ранга ноль, геометрических деревьев ранга 1 и 15 геометрических деревьев ранга 2.

Последние являются бинарными деревьями. Топологии всех этих деревьев изображены на рис. 1.4.

Соответственно всегда имеется одна регулярная минимальная параметрическая сеть 0 [0 ] ранга 0; она составляет совокупность 0. Потенциально могут быть 10 регулярных минимальных параметрических сетей ранга 1, составляющих совокупность 1, и 15 регулярных минимальных параметрических сетей ранга 2, составляющих совокупность 2. Напомним, см. параграф 3.1, что сети из 2 можно интерпретировать как локально минимальные сети, затягивающие границу. Таким образом, комбинаторно количество локально минимальных сетей, затягивающих данную границу из 5 точек, может быть не более 15. Далее мы понизим эту очевидную оценку до 8.

Итак, нам нужно вычислить (точнее оценить) количество сетей в совокупности 2. Теорема 2.2 дает нам при = 5 две формулы:

У регулярных минимальных параметрических сетей из 1 имеются две подвижные вершины: одна подвижная вершина степени 3 и одна подвижная вершина степени 4, см. рис. 1.4. Расщепляться сеть из может только в своей подвижной вершине степени 4, поэтому для сети комплекс мощных расщеплений нульмерен, также как и для сети 0 в случае 4 граничных точек. Точно также, как и в случае 4 граничных точек оценивается и количество мощных расщеплений # 2 ( ), и, следовательно, оно не превосходит 2. Таким образом, можно написать оценку Из этого неравенства мы видим, что количество сетей в совокупности 2 оценивается через мощные расщепления одной лишь сети 0. Комбинаторные расщепления сети 0 могут иметь ранг 1 или 2, поэтому комплекс (0 ) мощных расщеплений сети 0 одномерен. Вершинами этого комплекса являются элементарные геометрические расщепления сети 0.

Эти расщепления имеют ранг 1, и их совокупность совпадает с 1 (0 ).

В свою очередь, ребра комплекса (0 ) — это мощные расщепления ранга 2 сети 0, т.е. их совокупность совпадает с 2 (0 ).

Попытаемся изучить комплекс (0 ) и рассмотрим два случая.

1) У сети 0 есть вырожденное граничное ребро.

Пусть, без ограничения общности, это ребро будет инцидентно граничной вершине 1 (см. рис. 3.4).

Так как сеть 0 является минимальной параметрической сетью, то из критерия 3.3 вытекает, что сумма единичных направляющих векторов выходящих из вершины 1 ребер 1 2, 1 3, 1 4, 1 5 по модулю меньше либо равна 1.

Подсчитаем количество элементарных геометрических расщеплений сети 0. Их ранг равен 1, и топология изображена на рис. 1.4 ). Для этого необходимо, согласно критерию 3.3, чтобы сумма единичных направляющих векторов граничных ребер инцидентных одной подвижной вершине, среди которых нет ребра 1, по модулю была строго больше 1. Мы будем говорить, что такая совокупность граничных ребер отщепляется. Таким образом, любое элементарное геометрическое расщепление сети 0 однозначно задается либо двойкой, либо тройкой отщепляющихся граничных ребер. Поэтому для того, чтобы подсчитать количество элементарных геометрических расщеплений сети 0, нужно подсчитать количество двоек и троек ребер, выходящих из вершины 1, сумма единичных направляющих векторов которых по модулю строго больше 1.

Для двойки ребер это условие эквивалентно тому, что угол между ними строго меньше 120, а для тройки ребер эквивалентное условие содержится в лемме 3.8. Докажем, что это количество не больше 6.

Отщепляющиеся двойки граничных ребер.

Разберемся сначала с отщеплениями двоек ребер. Всего двоек ребер (число сочетаний из 4 по 2). Покажем, что ни все 6, ни какие-либо двоек не могут отщепиться, тем самым будет показано, что число отщеплений двоек ребер не более 4. В самом деле, если не менее 5 двоек отщепляются, то существует ребро, пусть это будет 1 2, которое составляет с оставшимися ребрами 1 3, 1 4, 1 5 угол строго меньше 120.

Проведем два разных луча [1 ) и [1 ): 2 1 = 2 1 = 120.

Тогда все три ребра 1 3, 1 4, 1 5 содержатся в открытом секторе 2 объединенным с точкой 1. Достаточно проанализировать только две ситуации: или все три ребра 1 3, 1 4, 1 5 лежат по одну сторону от прямой (1 2 ) или нет, см. рис. 3.4 и рис. 3.4.

Ситуации, изображенной на рис. 3.4 быть не может, так как в этом случае выходящие из 1 единичные направляющие векторы всех четырех ребер, лежащих в одном круговом секторе с углом равным 120, дают в сумме вектор, длина которого больше 1.

Теперь рассмотрим ситуацию, изображенную на рис. 3.4. Покажем, что и в этом случае длина суммы выходящих из вершины 1 единичных направляющих векторов ребер 1 2, 1 3, 1 4, 1 5 будет строго больше 1. Разобьем эти четыре ребра на две пары: (1 2, 1 5 ) и (1 3, 1 4 ). Угол 2 1 5 меньше 120, в соответствии с выбором ребра 1 2. И угол 3 1 4 тоже меньше 120, так как если бы был больше, то и угол 3 1 5 был бы больше 120, а это противоречит тому, что у нас по условию не менее 5 отщеплений. Пусть = 3 +4 и = 2 +5, где — единичный направляющий вектор ребра 1, тогда || > 1, || > и угол меньше 120. Следовательно |1 + 2 + 3 + 4 | = | + | > 1.

Этот случай заканчивает доказательство следующей леммы.

Лемма 3.9 В случае 1) количество отщепляющихся двоек не больше Отщепляющиеся тройки граничных ребер.

Теперь разберемся сколько может быть отщеплений по три ребра. Комбинаторных вариантов имеется всего 4 (число сочетаний из 4 по 3).

Лемма 3.10 Рассмотрим 4 произвольных неколинеарных отрезка 1 2, 1 3, 1 4, 1 5. Тогда количество отщеплений по три отрезка равно либо 2, либо 4. Причем в последнем случае все отрезки 1 2, 1 3, 1 4, 1 5 лежат по одну сторону от некоторой прямой, проходящей через точку 1.

Доказательство. Пусть угол 2 1 3 наименьший среди всех пар отрезков. Проведем прямые (2 1 ) и (3 1 ), они разобьют плоскость на четыре сектора. Четыре принципиально различных случая расположения остальных отрезков 1 4 и 1 5 в этих секторах показаны на рис. 3.5.

Для завершения доказательства достаточно воспользоваться леммой 3.8.

Лемма 3.11 Пусть в случае 1) имеется 4 отщепления троек ребер.

Тогда количество отщеплений двоек ровно 2.

Доказательство. Как следует из леммы 3.10, все ребра 1 2, 1 3, 1 4, 1 5 лежат по одну сторону от некоторой прямой, проходящей через 1. Пусть расположение ребер такое, как показано на рис. 3.6.

Покажем, что угол 3 1 4 > 120. Если бы выполнялось неравенство 3 1 4 < 120, тогда длина вектора = 3 + 4 была бы больше 1.

Положим = 2 + 5, тогда < 90, следовательно | + | = |2 + 3 + 4 + 5 | > 1, чего быть не может. Итак, 3 1 4 > 120, а значит отщеплений двоек ровно 2.

Суммируя результаты лемм 3.9, 3.10 и 3.11, для случая 1) получаем следующее предложение Предложение 3.5 В случае 1) имеется не более 6 отщеплений.

Если имеется всего 6 отщеплений, то может быть только два варианта:

2 отщепления двоек ребер и 4 отщепления троек ребер;

4 отщепления двоек ребер и 2 отщепления троек ребер.

Если имеется всего 5 отщеплений, то может быть только один вариант:

3 отщепления двоек ребер и 2 отщепления троек ребер.

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

Лемма 3.12 Каждой отщепляющейся тройке ребер инцидентно не менее одного мощного расщепления из 2 (0 ). Причем, разным тройкам инцидентны разные ребра.

Доказательство. Докажем первое утверждение. Пусть для определенности отщепляется тройка {1 2, 1 3, 1 4 }. Тогда, как следует из леммы 3.8, все эти отрезки лежат по одну сторону от некоторой прямой, проходящей через точку 1, и значит существует двойка ребер, скажем {1 2, 1 3 }, такая что 2 1 3 < 120, т.е. эта двойка отщепляется. Таким образом, мы имеем два элементарных геометрических расщепления 1 и 2 сети 0. Типы 1 и 2 этих двух расщеплений изображены на рис. 3.7. Из этого рис. 3.7 видно, что 1 и 2 образуют полный набор производных расщеплений для расщепления, тип которого изображен на том же рисунке. Поэтому является мощным расщеплением сети 0, инцидентным элементарному расщеплению 1 (отщепляющаяся тройка).

Докажем второе утверждение. Для того, чтобы двум отщепляющимся тройкам было инцидентно одно и то же мощное расщепление из 2 (0 ), см. рис. 3.7, нужно, чтобы эти тройки пересекались лишь по одному ребру, чего в случае 1) быть не может.

Лемма 3.13 Среди 4 отщеплений двоек ребер найдется по крайней мере одна пара двоек, которым инцидентно одно и то же мощное расщепление из 2 (0 ).

Доказательство. Если имеется 4 отщепления двоек ребер, то среди этих четырех двоек обязательно найдется пара двоек, скажем {1 2, 1 3 } и {1 4, 1 5 }, все четыре ребра которых различны.

Тип инцидентного этим отщеплениям двоек мощного расщепления из 2 (0 ) показан на рис. 3.8.

Предложение 3.6 Если в случае 1) всего отщеплений 6, т.е. # 1 (0 ) = 6, то # 2 (0 ) 4. Если всего отщеплений 5, т.е.

Доказательство. Разберем сначала случай 6 отщеплений. Разбираемые далее варианты согласуются с предложением 3.5. Если имеется отщепления двоек ребер и 4 отщепления троек ребер, то предложение следует из леммы 3.12. Если же имеется 4 отщепления двоек ребер и отщепления троек ребер, то пока леммы 3.12 и 3.13 нам могут гарантировать только # 2 (0 ) 3, то есть нужна еще 1.

Пусть среди 4 отщеплений двоек ребер только одной паре двоек инцидентно мощное расщепление из 2 (0 ) (если больше, то и # 2 (0 ) 4). Обозначим невырожденные ребра сети 0 цифрами от 1 до 4, тогда с точностью до переобозначений имеется лишь единственная отвечающая данной ситуации возможность выбрать 4 двойки ребер, а именно, (1, 2), (1, 3), (2, 3), (1, 4). Есть только два варианта расположения ребер 2 и относительно ребра 1, см. рис. 3.9. Но вариант ) не подходит, поскольку тогда ребро 4 либо с ребром 2, либо с ребром 3 образует угол строго меньший 120, и тогда появляется дополнительная отщепляющаяся двойка.

Вариант ) подходит, и при этом тройке (1, 2, 3) будет инцидентно два мощных расщепления из 2 (0 ). Итак, в любом случае # 2 (0 ) 4.

Согласно предложению 3.5, если отщеплений ровно 5, т.е. среди них ровно 3 отщепления троек, а тогда из леммы 3.12 следует, что 2) У сети 0 нет вырожденных граничных ребер.

Единственную подвижную вершину сети 0 мы обозначим через.

Так как сеть 0 является минимальной параметрической сетью, то из критерия 3.3 вытекает, что сумма единичных направляющих векторов выходящих из вершины ребер 1, 2, 3, 4, 5 должна быть равна 0.

Подсчитаем количество элементарных геометрических расщеплений сети 0. Для этого необходимо, согласно критерию 3.3, чтобы сумма единичных направляющих векторов граничных ребер, инцидентных одной подвижной вершине элементарного геометрического расщепления 1 (0 ), по модулю была строго больше 1. Мы будем говорить, что такая совокупность граничных ребер отщепляется. Заметим, что, в отличие от случая 1), для каждого элементарного геометрического расщепления 1 (0 ), в силу равенства нулю суммы единичных направляющих векторов граничных ребер, отщепляется как двойка, так и дополнительная ей тройка граничных ребер. Поэтому для того, чтобы подсчитать количество элементарных геометрических расщеплений # 1 (0 ) сети 0, нужно подсчитать только количество двоек ребер, выходящих из вершины, сумма единичных направляющих векторов которых по модулю строго больше 1. Для двойки ребер это условие эквивалентно тому, что угол между ними строго меньше 120. Докажем, что и в случае 2) это количество не больше 6.

Для краткости двойку ребер {, } будем обозначать просто (), а через обозначим единичный направляющий вектор ребра, = 1,..., 5.

Лемма 3.14 В случае 2) количество отщеплений двоек ребер не превосходит 6.

Доказательство. Пусть граничные вершины расположены так, что их нумерация соответствует обходу против часовой стрелки вокруг подвижной вершины — точки, см. рис. 3.10.

Если любой угол между не соседними ребрами не меньше 120, то отщепляющихся двоек ребер может быть не больше 5. Пусть теперь у сети 0 есть угол между не соседними ребрами, градусная мера которого строго меньше 120. Из таких углов возьмем наименьший. Без ограничения общности можно считать, что это угол 1 3. Проведем прямую (), содержащую биссектрису угла 1 3, и прямую ( ), содержащую биссектрису угла 2, а также прямую (2 ), содержащую ребро 2. Пусть 2 = 2, тогда = 2 =. Теперь обозначим через вектор равный 1 + 3, а через вектор равный + 2. Заметим, что || > 1 и лежит на луче [ ), и || > 1, но про вектор можно лишь сказать, что он лежит во внутренней области угла 2. Поскольку 5 + 4 =, то 5 4 < 2. Поэтому векторы 5 и 4 лежат во внутренней области угла 1 и составляют с лучом [ ) угол не больший 2. Так как 2 < 60, то следовательно отщепляться могут только двойки (12), (13), (23), (15), (14), (45), т.е. не более 6 отщеплений двоек.

Предложение 3.7 Если в случае 2) имеется 6 отщеплений двоек, т.е.

# 1 (0 ) = 6, то # 2 (0 ) 4. Если в случае 2) имеется 5 отщеплений двоек, т.е. # 1 (0 ) = 5, то # 2 (0 ) 2.

Доказательство. Сначала рассмотрим случай # 1 (0 ) = 6.

Для того чтобы двум парам отщепляющихся двоек ребер было инцидентно одно и то же мощное расщепление из 2 (0 ) необходимо и достаточно, чтобы все эти четыре ребра были различными. Рассмотрим пары отщепляющихся двоек, соответствующих какому-нибудь мощному расщеплению из 2 (0 ).