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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

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

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

Иванов Александр Олегович

УДК 514.77+512.816.4+517.924.8

ГЕОМЕТРИЧЕСКИЕ СВОЙСТВА ЛОКАЛЬНО МИНИМАЛЬНЫХ СЕТЕЙ

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

ДИССЕРТАЦИЯ на соискание ученой степени доктора физико-математических наук

Москва - 1997

Содержание

Введение 1

1 Исторический обзор............................................2

2 Основные результаты теории абсолютно минимальных сетей ............................................................8

2.1 Общие факты из теории абсолютно минимальных сетей....................................................8

2.2 Оболочки Штейнера ..................................10

2.3 Гексогональная система координат..................12

2.4 Абсолютно минимальные деревья, затягивающие множества специального вида........................15

2.5 Минимальные остовные деревья как приближенные решения проблемы Штейнера..................19

3 Основные результаты теории локально минимальных сетей 24

3.1 Плоские локально минимальные бинарные деревья

с выпуклой границей..................................24

3.2 Невырожденные плоские локально минимальные сети с выпуклой границей............................28

3.3 Локально минимальные сети в других объемлющих пространствах ....................................29

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

1 Обобщенные сети на многообразиях 57

1.1 Графы: топологический подход ............................57

1.1.1 Топологические графы, их эквивалентность ... 58

1.1.2 Маршруты, пути, циклы ............................60

1.1.3 Подграфы, остовы ....................................61

1.1.4 Операции над графами................................62

1.1.5 Граница графа, локальный граф....................64

1.1.6 Взвешенные графы, остовы минимального веса . 65

1.2 Общее определение сети......................................66

1

1.3 Параметрические сети........................................68

1.3.1 Параметрические сети, приведенные параметрические сети, компоненты вырождения ............68

1.3.2 Гладкие, кусочно-гладкие, вложенные и погруженные параметрические сети ..........................70

1.3.3 Граница параметрической сети. Замкнутые параметрические сети......................................70

1.3.4 Эквивалентности параметрических сетей .... 71

1.3.5 Длина параметрической сети на римановом многообразии ..............................................75

1.3.6 Взвешенная длина параметрической сети..........75

1.3.7 Деформации параметрических сетей................77

1.3.8 Формулы первой и второй вариации длины кривой 78

1.3.9 Формула первой вариации длины геодезической параметрической сети..........................86

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

1.3.11 Формула первой вариации взвешенной длины геодезической параметрической сети..................89

1.4 Сети-следы......................................................89

1.4.1 Следы....................................................90

1.4.2 Граница следа. Замкнутые следы....................91

1.4.3 Длина следа............................................92

1.4.4 Канонический представитель........................93

1.4.5 Деформации следов.......................99

1.4.6 Локальное устройство следов........................102

2 Минимальные сети: естественные обобщения проблемы

Штейнера 105

2.1 Глобальная и локальная минимальность....................105

2.2 Локально минимальные параметрические сети и следы . 107

2.2.1 Слабо локально минимальные параметрические с.ети107

2.2.2 Сильно локально минимальные параметрические сети......................................................108

2.2.3 Локально минимальные взвешенные параметрические сети................................................110

2.2.4 Локально минимальные сети-следы ................110

2.2.5 Общая задача о поиске локально минимальных сетей ....................................111

2.3 Разные классы сетей — разные минимизационные задачи 111

2.3.1 Замкнутые параметрические сети фиксированного

типа......................................................113

2.3.2 Параметрические сети с границей..................114

2.3.3 Множество всех параметрических сетей ..........114

2.3.4 Параметрические сети, гомотопные данной .... 115

2.3.5 Следы....................................................116

2.3.6 Другие важные семейства сетей ....................116

2.4 Теоремы существования......................................118

2.4.1 Параметрические сети с фиксированной границей 118

2.4.2 Замкнутые параметрические сети..................120

2.4.3 Взвешенные параметрические сети ................122

2.4.4 Следы с фиксированной границей ..................122

2.4.5 Замкнутые следы......................................123

2.4.6 Теорема существования ..............................124

3 Локальная структура минимальных сетей 127

3.1 Локальная структура минимальных параметрических сетей ..............................................................127

3.1.1 Критерий локальной минимальности погруженных параметрических сетей ..............................128

3.1.2 Общий случай: критерий слабой локальной минимальности параметрических сетей..................132

3.1.3 Необходимые факты из теории выпуклых функций 134

3.1.4 Общий случай: сильно локально минимальные параметрические сети....................................139

3.1.5 Критерий сильной локальной минимальности параметрической сети в евклидовом пространстве . 150

3.2 Локальная структура взвешенных локально минимальных параметрических сетей.................... . 151

3.2.1 Критерий локальной минимальности взвешенных погруженных параметрических сетей..............151

3.2.2 Общий случай: условия слабой и сильной локальной минимальности взвешенных параметрических сетей....................................................152

3.2.3 Сильно локально минимальные взвешенные параметрические сети в евклидовом пространстве . . 154

3.2.4 Общие теоремы о локальной структуре параметрических сетей........................................154

3.3 Локальная структура минимальных следов................155

3.4 Локальная единственность ..................................159

4 Глобальная структура плоских локально минимальных деревьев 165

4.1 Плоские ломаные I: случай общего положения ............168

4.1.1 Твистинги и кручение................................169

4.1.2 Пара ломаных в общем положении..................172

4.1.3 Некоторые следствия и оценки......................183

4.1.4 Шапочки................................................186

4.2 Геометрия плоских локально минимальных бинарных деревьев ............................................................189

4.2.1 Число вращения плоского бинарного дерева . . . 190

4.2.2 Свойства минимальных 2-деревьев..................192

4.2.3 Алгоритм Мелзака....................................195

4.2.4 Алгоритм Хванга......................................198

4.2.5 Следствия из алгоритмов Мелзака и Хванга . . . 201

4.2.6 Теорема об общем положении........................203

4.2.7 Теорема о связи числа вращения плоского минимального бинарного дерева и количества уровней выпуклости его граничного множества............205

4.3 Плоские ломаные II: общий случай..........................218

4.4 Геометрия плоских линейных деревьев......................236

4.4.1 Число вращения плоского линейного дерева .... 238

4.4.2 Геометрическая граница линейного дерева .... 239

4.4.3 Правильные линейные деревья ......................240

4.4.4 Квази-геодезические..................................246

4.4.5 Шапочки................................................250

4.4.6 Доказательство теоремы 6............................255

4.4.7 Случай р = д............................................256

4.4.8 Случай р < д............................................262

4.4.9 Завершение доказательства теоремы в общем случае270

4.4.10 Некоторые следствия..................................272

4.5 Геометрия плоских минимальных взвешенных бинарных деревьев..........................................................274

4.5.1 Число вращения плоского взвешенного бинарного дерева....................................................275

4.5.2 Обобщенный алгоритм Мелзака: случай трех точек277

4.5.3 Обобщенный алгоритм Мелзака: общий случай . 281

5 Геометрия множества взвешенных локально минимальных сетей с фиксированными типом и границей в 289

5.1 Геодезические сети. Линейные сети........................290

5.2 Взвешенные минимальные сети в ........................296

5.2.1 Структура множества взвешенных локально минимальных сетей......................................300

5.2.2 Формы Максвелла......................................307

5.2.3 Усы......................................................309

5.2.4 Доказательство теоремы 8............................310

5.3 Взвешенные минимальные сети Штейнера на плоскости 312

5.3.1 Оснащение вращения..................................313

5.3.2 Функция Максвелла....................................318

5.3.3 Построение деформации невырожденной минимальной сети ................................................320

Общий список работ 325

Список работ по теме диссертации 333

Введение

Цель настоящей диссертации — изучение геометрических свойств локально минимальных сетей на римановых многообразиях. С точки зрения римановой геометрии, локально минимальные сети являются естественным обобщением обычных геодезических. Напомним, что соединяющая пару фиксированных точек риманова многообразия геодезическая обладает следующим определяющим свойством: каждый ее фрагмент между достаточно близкими точками А и В является кратчайшей кривой среди всех кривых, соединяющих А ж В. Предположим теперь, что фиксировано не две точки риманова многообразия IV, а некоторое конечное его подмножество М, состоящее из большего числа точек. Чтобы обобщить на этот случай понятие геодезических, естественно перейти от кривых к рассмотрению связных одномерных континуумов — сетей. Затягивающая множество М С И/Г сеть называется абсолют,но минимальной, если она имеет наименьшую возможную длину, и локально минимальной, если каждый достаточно малый ее фрагмент имеет наименьшую возможную длину, т.е. является абсолютно минимальной сетью. В этом смысле естественно говорить о локально минимальных сетях как о "разветвленных геодезических".

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

1

связан с прямым перебором очень большого числа возможных топологий (комбинаторных структур) кратчайшей сети. На самом деле, как показано в [29], задача Штейнера является ÁÍV-трудной, т.е., неформально говоря, скорее всего не существует алгоритма, строящего решение за полиномиальное время. Поэтому большое значение имеет изучение геометрических ограничений, накладываемых на возможную структуру сетей условием минимальности. При таком геометрическом подходе естественно, как и в случае кратчайших кривых, расширить класс рассматриваемых сетей, перейдя от сетей кратчайших "в целом" к изучению сетей кратчайших "в малом", т.е. перейти к изучению локально минимальных сетей.

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

1 Исторический обзор

Понятие локально минимальной сети впервые неявным образом появилось при изучении следующей классической задачи, известной в литературе как проблема Штейнера: среди всех сетей (связных одномерных континуумов), затягивающих данное конечное множество М т,очек плоскости, найти сеть наименьшей длины. Эта задача была названа "проблемой Штейнера" в замечательной книге Ричарда Куранта и Герберта Е. Роббинса ílTímo такое матемагпика'Р' в честь Якоба Штейнера (Jacol) Steiner, 1796-1863), швейцарского математика, профессора Берлинского университета. Именно после появления этой очень популярной книги интерес к абсолютно минимальным сетям разгорелся с новой силой, и терминология, предложенная Курантом и Роб-бинсом стала общепринятой.

Следует отметить, однако, что сама задача о поиске абсолютно минимальных сетей имеет более длинную историю. Мы проследим ее здесь, воспользовавшись историческими обзорами в [88], [62], [37] и [34].

Рис. 1: Точка Торричелли.

По-видимому, впервые задача такого типа была поставлена Ферма (1601-1665) до 1640 года. А именно, Ферма интересовал ответ на следующий вопрос: как расположить на плоскости точку F так, чт.обы сумма расстояний от нее до трех фиксированных точек А\, Ач и была наименьшей?

Торричелли предложил геометрическое решение этой задачи. Построим на сторонах заданного треугольника AiA2A^ вне его три правильных треугольника и опишем вокруг них окружности. Тогда, как показал Торричелли, построенные три окружности пересекутся в одной точке Т, которая известна теперь в планиметрии как точка Торричелли, см. рис. 1. Торричелли утверждал, что F = Т, т.е. эта точка Т и является решением задачи, поставленной Ферма. Однако, заметим, Торричелли ошибся: его рассуждения справедливы только в предположении, что все углы треугольника A\A-iA3 не превосходят 120°. Если же один из этих углов, скажем угол Ai, больше 120°, то, как легко видеть, точка Торричелли лежит вне треугольника А\ А2 A3 и не минимизирует суммарное расстояние до вершин треугольника. В этом случае, как независимо заметили Хейнен (в 1834 году) и, позднее, Бертран (в 1853 году), искомой точкой является вершина А\.

Вернемся в XVII век. В 1647 году выходит книга Кавальери иЕх-cercitationes Geom,etricaey', в которой отмечается важное свойство точки Торричелли Т, в предположении, что эта точка лежит внутри треугольника А1А2А3: все углы между отрезками А{Т равны между собой и равны 120°. Этот факт оказывается весьма фундаментальным, и его аналоги, как мы увидим, имеют место в существенно более общих ситуациях.

В середине следующего столетия, в 1750 году, в своей книге '"Doctrine and Application of Fluctions" Симпсон предложил другой способ построения точки Торричелли. Конструкция Симпсона состоит в еле-

Рис. 2: Линии Симпсона пересекаются в точке Торричелли.

дующем. Снова построим на сторонах треугольника А\А^Аг и вне его правильные треугольники. Объединение каждого из построенных нами треугольников с исходным треугольником А1А2А3 представляет собой четырехугольник, одна из диагоналей которого совпадает с соответствующей стороной треугольника А\А2А^. Проведем недостающие диагонали. Три построенных отрезка называются теперь линиями Симпсона. Симпсон показал, что эти отрезки или их продолжения пересекаются в одной точке, совпадающей с точкой Торричелли, рис. 2.

Уже в XIX веке, в 1834 году, Хейнен показал, что если точка Торричелли лежит внутри треугольника А1А2А3, то длины всех трех линий Симпсона равны между собой и равны сумме расстояний от точки Торричелли до вершин треугольника. Таким образом, собирая воедино все сказанное выше, мы получаем следующий полный ответ на поставленную Ферма задачу.

Решение задачи Ферма. Точка Р. являющаяся решением задачи Ферма. единственна.

Если один из углов треугольника А\А2Аз, скажем А\у больше или равен 120°, то F =

Если же все углы треугольника А2Аз меньше 120°. то Р1 совпадает с точкой Торричелли. В этом случае все углы между отрезками 5А{ равны между собой и равны 120°. При этом линии Симпсона имеют одинаковые длины, равные ¡5A.il + |5Аг| + |5Аз|.

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

одну дополнительную вершину — вершину 5*. Одним из вариантов задачи Симпсона занимался Якоб Штейнер.

Другое обобщение задачи Ферма получается, если в качестве объекта, 3' которого минимизируется длина, рассматривать произвольные сети, затягивающие данные множества точек. Впервые случай 4 и 5 точек рассматривался в работах французских математиков Жергонна, Клайперона и Ламе, а также в письмах Гаусса. Наконец, в 1934 году Ярник и Кесслер поставили задачу в следующем современном виде: найти кратчайшую сеть, свлзываюгцую п данных точек плоскости.

Ярник и Кесслер решили поставленную проблему для граничных множеств, образующих вершины правильных п-угольников при п = 3, 4, 5 и п > 13. Для п = 3, 4, 5 Ярник и Кесслер нашли очевидные абсолютно минимальные сети, а для п > 13 показали, что абсолютно минимальная сеть состоит из (п — 1)-ой стороны рассматриваемого правильного п-угольника. В работе этих авторов не было ссылок на Ферма, так как им, по-видимому, казалось, что они занимаются совсем другой задачей. Переписка Гаусса и работы французских математиков им также не были известны. Заметим, кстати, ч�