Геометрические свойства локально минимальных сетей

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА МЕХАНИКΠ— МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ На правах рукописи Иванов Александр Олегович УДК 514.77+512.816.4+517.924.8 ГЕОМЕТРИЧЕСКИЕ СВОЙСТВА ЛОКАЛЬНО МИНИМАЛЬНЫХ СЕТЕЙ 01.01.04 геометрия и топология Д И С С Е Р Т А Н И Я на соискание ученой степени доктора физико †математическ наук Москва — 1997 Содержание Введ 1 2 1 2 ение Исторический обзор Основные результаты теории абсолютно ыинимадьных сетей 2.1 Общие факты из теории абсолютно минимальных сетей 2.2 Оба ючки Штейнера 2.3 Гексогональная система координат ....

2.4 Абсолютно минимальные деревья, затягивающие множества специального вида 2.5 Минимальные остовные деревья как приближенные решения проблемы Штейнера Основные результаты теории локааьно минимальных сетей 3.1 Плоские локально минимальные бинарные деревья с выпуклой границей 3.2 Невырожденные плоские локально минимальные сети с выпуклой границей 3.3 Локально минимальные сети в других объемлющих пространствах Краткое содержание диссертации 8 9 12 14 23 27 29 35 57 57 58 60 61 62 64 65 66 1 Обобщенные сети на многообразиях 1.1 Графы: топологический подход 1.1.1 Топологические графы,их эквивалентность 1.1.2 Маршруты, пути, циклы 1.1.3 Подграфы, остовы 1.1.4 Операции над графами.........

1.1.5 Граница графа, локальный граф 1.1.6 Взвешенные графы, остовы минимального веса 1.2 Общее определение сети 70 70 71 75 75 77 "8 89 89 90 91 92 93 99 102 2 Минимальные сети: естественные обобщения проблемы Штейнера 105 '2.1 2.2 2.3 108 110 110 111 111 113 1.3 1.4 Параметрические сети 1.3.1 Параметрические сети, приведенные параметрические сети, компоненты вырождения 1.3.2 Гладкие, кусочно-гладкие, вложенные и погруженные параметрические сети 1.3.3 Граница параметрической сети. Замкнутые параметрические сети 1.3.4 Эквивалентности параметрических сетей 1.3.5 Длина параметрической сети на римановом многообразии 1.3,6 Взвешенная длина параметрической сети 1.3.7 Деформации параметрических сетей ........ 1.3.8 Формулы первой и второй вариации длины кривой 1.3.9 Формула первой вариации длины геодезической параметрической сети 1.3,10 Вторая локальная геодезическая вариация погруженных параметрических сетей 1.3.11 Формула первой вариации взвешенной длины геодезической парамотрической сети Сети — следы ..

1.4.1 Следы 1.4,2 Граница следа. Замкнутые следы.......... 1.4.3 Длина следа 1.4.4 Канонический представитель 1.4.5 Деформации следов 1.4.6 Локальное устройство следов Глобальная и локальная минимальность .......... 105 Локально минимальные параметрические сети и следы . 107 2.2.1 Слабо локально минимальные параметрические сети107 2.2.2 Сильно локально минимальные параметрические сети .. 2.2.3 Локально минимальные взвешенные параметрические сети .. Локально минимальные сети — следы Общая задача о поиске локально минимальных сетей Разные классы сетей разные минимизационные задачи 2.3.1 Замкнутые параметрические сети фиксированного типа ..

111 114 114 115 116 117 118 118 120 122 122 123 124 2.4 3 Локальная структура минимальных сетей 127 127 128 мальности параметрических сетеи , ...... 132 3.1.3 Необходимые факты из теории выпуклых функций 134 4 Глобальная структура плоских локально минимальных деревьев 165 4.1 Плоские ломаные 1: случаи общего положения ...... 168 3.1 3.2 3.3 3.4 2.3,2 Параметрические сети с границей 2.3.3 Множество всех параметрических сетей 2.3.4 Параметрические сети, гомотопные данной.... 2.3.5 Следы 2.3.6 Другие важные семейства сетей Теоремы существования 2.4.1 Параметрические сети с фиксированной границей 2.4.2 Замкнутые параметрические сети 2.4.3 Взвешенные параметрические сети 2,4.4 Следы с фиксированной границей 231,5 Замкнутые следы 2.4.6 Теорема существования Локальная отру.кту.ра минимальных параметрических се- тей 3.1.1 Критерий локальной минимальности погруженных параметрических сетей 3.1.2 Общий случай: критерий слабой локальной мини- 3.1.4 Общий случай: сильно локально минил1альные параметрические сети 3.1.5 Критерий сильной локальной минимальности параметрической сети в евклидовом пространстве .

Локальная структура взвешенных локально минимальных параметрических сетей . 3.2.1 Критерий локальной минимальности взвешенных погруженных параметрических сетей 3.2.2 Общий случаи: условия слабой и сильной локальной минимальности взвешенных параметрических сетей 3.2.3 Сильно локально минимальные взвешенные параметрические сети в евкяидовом пространстве 3.2.4 Общие теоремы о локальной структуре параметрических сетей . Локальная структура минимальных следов Локальная единственность 139 150 151 152 154 155 159 4.2 4.3 4.4 4.5 169 172 183 186 4.4.9 Завершение доказательства теоремы в общем случае270 4.4,10 Некоторые следствия 272 Геометрия плоских минимальных взвешенных бинарных деревьев . 274 4.5.1 Число вращения плоского взвешенного бинарного дерева .

275 4.5.2 Обобщенный алгоритм Мелзака: случай трех точек277 4.5.3 Обобщенный алгоритм Мелзака: общий случай . 281 4.1.1 Твистинги и кручение 4.1.2 Пара ломаных в общем положении 4.1.3 Некоторые следствия и оценки 4.1.4 Шапочки Геометрия плоских локально минимальных бинарных деревьев . 4.2.1 Число вращения плоского бинарного дерева 4.2.2 Свойства минимальных 2-деревьев .. 4.2.3 Алгоритм Мелзака 4.2,4 Алгоритм Хванга 422.5 Следствия из алгоритмов Мелзака и Хванга 4.2.6 Теорема об общем положении . 4.2.7 Теорема о связи числа вращения плоского минимального бинарного дерева и количества уровней выпуклости его граничного множества Плоские ломаные П: общий случай Геометрия плоских линейных деревьев .. 4.4.1 Число вращения плоского линейного дерева ....

4.4.2 Геометрическая граница линейного дерева 4.4.3 Правильныс линсйныс деревья 4.4.4 14вази-геодезические 4А.5 Шапочки 4.4.6 Доказательство теоремы 6.............. 4.4.7 Случай р — д....... 4.4.8 Случай р ( д 189 190 192 195 198 201 203 205 217 236 238 239 240 246 250 255 256 262 5 Геометрия множества взвешенных локально минимальных сетей с фиксированными типом и границей в й~ 289 5.1 Геодезические сети. Линейные сети ............

290 5.2 Взвешенные минимальные сети в Гт~............ 296 522.1 Структура множества взвешенных локально минимальных сетей 300 Формы Максвелла 307 Усы 309 5.2.4 Доказательства теоремы 8.............. 310 5,3 Взвешенные минимальные сети Штейнера на плоскости 312 5.3.1 Оснащение вращения 313 5.3.2 сРункцня Х1аксвелла. 318 5.3.3 Построение деформации невырожденной минимальной сети ........................ 320 Общий список работ Список работ по теме диссертации 333 Введение Цель настоящей диссертации изучение геометрических свойств локально минимальных сетей на римановых многообразиях. С точки зрения римановой геометрии, локально минимальные сети являются естественным обобщением обычных геодезических. Напомним, что соединяющая пару фиксированных точек риманова многообразия геодезическая обладает следующим определяющим свойством; каждый ее фрагмент между достаточно близкими точками А и В является кратчайшей кривой среди всех кривых, соединяющих .4 и В.

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

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

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

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

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