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



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

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

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

ТУЖИЛИН Алексей Августинович

УДК 514.77+512.816.4+517.924.8

КЛАССИФИКАЦИЯ ЛОКАЛЬНО МИНИМАЛЬНЫХ ПЛОСКИХ СЕТЕЙ С ВЫПУКЛЫМИ ГРАНИЦАМИ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва — 1997

Работа выполнена на кафедре дифференциальной геометрии и приложений Московского государственного университета имени М. В. Ломоносова.

Официальные оппоненты:

доктор физико-математических наук, профессор Ю. Г. Борисович доктор физико-математических наук, профессор А. С. Мищенко доктор физико-математических наук, профессор В. В. Шарко

Ведущая организация — Новосибирский институт математики имени С. Л. Соболева

Защита диссертации состоится _ 1997 г. в 16 часов

15 минут на заседании диссертационного совета Д. 053.05.05 при Московском государственном университете имени М. В. Ломоносова по адресу:

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ.

119899, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 14-08.

Автореферат разослан

Ученый секретарь диссертационного совета

Д.053.05.05 при МГУ

доктор физико-математических наук,

профессор

В. Н. Чубариков

Общая характеристика работы

Актуальность темы. Настоящая диссертация посвящена изучению локально минимальных плоских связных графов, затягивающих вершины выпуклых многоугольников. Такие графы возникают при решении знаменитой проблемы Штейнера: среди всех сетей (связных одномерных континуумов), затягивающих данное конечное множество M точек плоскости, найти сеть наименьшей длины. Решения проблемы Штейнера называются абсолютно минимальными деревьями. Как было отмечено в историческом обзоре из [1], где цитировались [2] и [3], простейший вариант этой проблемы возник еще в работах Ферма, а в современном виде она была сформулирована Ярником и Кессле-ром [4]. Название "проблема Штейнера" укоренилось благодаря популярности замечательной книги Куранта и Роббинса "Что такое математика?", в которой эта проблема была названа в честь Якоба Штейнера, занимавшегося близкой, но, вообще говоря, другой задачей. Тем не менее, подавляющее большинство специалистов пользуется терминологией, связанной с именем Штейнера, поэтому, вопреки справедливости, нам придется подчиниться традиции, чтобы не вносить путаницу. Отметим, что книга Куранта и Роббинса "Что такое математика?" породила огромный интерес к проблеме Штейнера, о чем свидетельствует обширная литература, посвященная изучению этой проблемы.

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

Хорошо известна локальная структура абсолютно минимальных сетей, а также алгоритм построения таких сетей, открытый Мелзаком [5]. Тем не менее, как показано в [6] (см. также [7]), проблема Штейнера является NP-полной, и современные компьютеры в состоянии строить ее решения для общих множеств M состоящих из трех-четырех десятков точек, что крайне мало для практических нужд [7]. Поэтому представляет интерес поиск различных геометрических свойств множеств M и связных плоских графов, исходя из которых можно было бы существенно сократить перебор типов сетей, являющихся претендентами на решение проблемы Штейнера. Одним из таких свойств является "выпуклость" граничного множества M, т.е. свойство множества M лежать на границе своей выпуклой оболочки (такие M обычно называют экстремальными, тем не менее, мы используем термин выпуклые, чтобы оставить за словом экстремальные смысл, вкладываемый в него в вариационном исчислении, как в выражении "экстремаль функционала длины").

1. F. К. Hwang, D. Richards and P. Winter, Elsevier Science Publishers (в печати). 2. ff. W. Kuhn, In the book Studies in Optimization, ser. Studies in Math., vol. 10, Math. Assoc. Amer., edited by G. B. Dantzig and B. C. Eaves, 1975, pp. 53-70. 3. M. Zacharias, Encyklopädie der Mathematischen, Wissenschaften, vol. III АВЭ. 4. V. Jarnik and M. Kössler, Cas. Pest. Mat. a Fys., 1934, vol. 63, pp. 223-235. 5. Z. A. Melzak, Canad. Math. Bull., 1960, vol. 4, pp. 143-148. 6. M. R. Garey, R. L. Graham, and D. S. Johnson, Eighth Annual Symp. on Theory of Comput., 1976, pp. 10-22. 7. F. Preparata, and M. Shamos, Computational Geometry. An introduction. New York, Springer-Verlag, 1985.

Отметим, что в алгоритме Мелзака [5], а также в его модификации, придуманной Хвангом [8], в действительности перебираются так называемые локально минимальные деревья, т.е. плоские деревья, каждый достаточно малый фрагмент которых является абсолютно минимальной сетью с естественной границей. Ясно, что у локально минимальных сетей локальная структура такая же, как и у абсолютно минимальных сетей (каждая локально минимальная сеть состоит из отрезков прямых — ребер сети, стыкующихся в вершинах сети под углами, не меньшими чем 120°; при этом можно считать, что все вершины степени 1 и 2 принадлежат граничному множеству М). Однако задача описания всех локально минимальных сетей, затягивающих данное множество М, существенно сложнее.

Так, например, если множество М является множеством вершин правильного п-угольника, то, как было показано Ярником и Кесслером в [4], при п > 13 каждая абсолютно минимальная сеть, затягивающая М, состоит из всех сторон этого п-угольника, за исключением любой одной. Кроме того, Ярник и Кесслер построили очевидные абсолютно минимальные сети для случаев п — 3, 4, 5. Лишь в 1987 Ду и Хванг завершили описание абсолютно минимальных сетей, затягивающих вершины правильных многоугольников, доказав, что для п > 6 ответ такой же, как и для п > 13.

Одно из приложений, рассматриваемых в настоящей диссертации, посвящено описанию всех локально минимальных деревьев, затягивающих вершины правильных многоугольников. Как следствие общей теории, развиваемой в диссертации, эта задача полностью решается для важного класса плоских бинарных деревьев, называемых скелетами. Оказывается, что множество всех локально минимальных бинарных деревьев, затягивающих вершины правильных п-угольников и являющихся скелетами, состоит из двух бесконечных по п серий (в одной серии п принимает любое значение, а в другой серии п может быть лишь вида 6к + 3, где к — любое целое положительное число) и одной конечной серии (здесь п принимает лишь следующие значения: 24, 30, 36 и 42).

Локально минимальные сети, не являющиеся, вообще говоря, абсолютно минимальными, могут быть получены экспериментально, см., например, в [9], [10], [11]. Таким образом, локально минимальные сети имеют и самостоятельный интерес.

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

8. F. К. Hwang, Орег. Res. Letter, 1986, vol. 5, pp. 235-237. 9. Z. A. Mehak, Companion to concrete mathematics. Wiley-Interscience, New York, 1973. 10. А. А. Тужилин и А. Т. Фоменко, Элементы геометрии и топологии минимальных поверхностей. М.: Наука, 1991. 11. А. О. Ivanov, and A. A. Tuzhilin, Minimal Networks. The Steiner Problem and Its Generalizations. N.W., Boca Raton, Florida, CRC Press, 1994.

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

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

Научная новизна. 1) Получена полная классификация локально минимальных бинарных деревьев с выпуклой границей.

Пусть Г — плоское бинарное дерево, (а, Ь) — некоторая (упорядоченная) пара его ребер, и 7 — единственный путь в Г, соединяющий эти ребра. Ориентируем путь 7 от а к Ь, и пусть Р — произвольная вершина степени 3 дерева Г, лежащая внутри 7, т.е. не совпадающая ни с одной из его концевых вершин. Выберем круговую окрестность V вершины Р, такую что II П Г является деревом, не содержащим вершин из Г, отличных от Р. Тогда пересечение ди ПГ состоит из трех точек, которые мы обозначим через А{, г = 1, 2, 3. Пусть 01 — первое, и 02 — последнее ребро из 7, инцидентное Р, и пусть Л, € а,-, г = 1, 2. Рассмотрим дугу 5 окружности 3(7, лежащую между А\ и Л2 и содержащую А3.

Определение. Если движение по дуге 5 от А\ к Л2 происходит по часовой стрелке, то будем говорить, что мы поворачиваем направо в точке Р, и припишем Р число —1. В противном случае, скажем, что мы поворачиваем налево в точке Р и припишем Р число +1. Число, приписанное вершине Р, называется твистингом вершины Р ориентированного пути 7. Числом вращения упорядоченной пары (а, Ь) ребер плоского бинарного дерева Г называется сумма твистингов во всех внутренних вершинах пути у. Положим, по определению, Ьту(о, а) = 0.

Определение. Числом вращения Г бинарного дерева Г называется максимум чисел вращения tw(a, Ь), взятый по всевозможным упорядоченным парам ребер из Г.

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

Напомним, что плоские бинарные деревья можно описывать на двойственном языке, а именно с помощью триангуляции диагоналями плоских многоугольников: по каждой диагональной триангуляции Т многоугольника IV можно построить плоское бинарное дерево Гу, называемое двойственной сетью этой триангуляции, и обратно, по каждому плоскому бинарному дереву Г

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

Если двойственная сеть диагональной триангуляции Т обладает некоторым свойством, то мы, в дальнейшем, будем говорить, что сама триангуляция Т обладает этим свойством. Так, например, совокупность ячеек из Т называется связной, если пересечение двойственной сети Гу с этими ячейками связно. Или, скажем, число вращения сети Гт будем называть числом вращения триангуляции Т. Также, будем говорить, что диагональная триангуляция Т имеет выпуклую минимальную реализацию, если ее двойственная сеть Гт планарно эквивалентна некоторому локально минимальному бинарному дереву с выпуклой границей. Из предложения 1 вытекает, что для описания всех локально минимальных бинарных деревьев с выпуклой границей достаточно расклассифицировать все диагональные триангуляции с числом вращения, не превосходящим 5. Множество всех таких триангуляций будем обозначать через ]Щ.

Пусть Т — произвольная триангуляция диагоналями многоугольника IV (такие триангуляции будем называть диагональными), и Д — любая ее ячейка. Назовем Д крайней ячейкой, если по меньшей мере две ее стороны являются сторонами IV. Ячейка Д называется внутренней, если ни одна из ее сторон не есть сторона из . Если две ячейки пересекаются по стороне, то мы называем их смежными и говорим, что одна из них примыкает ко второй. Крайняя ячейка, примыкающая к внутренней, называется наростом, а триангуляция Т без наростов называется скелетом. Если для каждой внутренней ячейки триангуляции Т из всех примыкающих к ней наростов (если они есть) выбросить ровно один, то, как легко проверить, полученная триангуляция Т" уже не будет содержать наростов, т.е. Т' является скелетом, который называется скелетом триангуляции Т. Таким образом, мы построили, вообще говоря, неоднозначное разложение триангуляции Т на скелет и наросты. Эта неоднозначность возникает при наличии концевых наростов — пары наростов, примыкающих к одной и той же внутренней ячейке.

Оказывается, для триангуляций из У/Щ скелеты устроены достаточно просто. Наша классификация состоит из двух частей: сначала описываются все скелеты из УУР;, а затем то, как можно к ним прикреплять наросты, не выходя при этом из класса У/Р>. Мы приведем здесь лишь описание скелетов из Первый шаг в описании скелетов — это разложение их на линейные участки и узлы ветвления.

Пусть 5 — произвольный скелет (не обязательно из У/Щ- Связные компоненты множества внутренних ячеек скелета 5 называются узлами ветвления, а связные компоненты скелета из которого выброшены все внутренние ячейки, называются линейными участками. Линейный участок, содержащий крайнюю ячейку, называется концевым, а не содержащий — промежуточным. Если скелет Б содержит к концевых линейных участков, то 5 будем называть к-скелетом.

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

Рис. 1. Узлы ветвления скелетов из

ниже, код скелета из устроен достаточно просто.

Следующее предложение полностью описывает все возможные узлы ветвления скелетов из У/^Ь-

Предложение 2. Узлы ветвления скелетов из И^ могут быть ровно 5 типов, приведенных на рис. 1.

Опишем теперь линейные участки скелетов из УУТ^. Чтобы это описание было наглядным, оказывается полезным рассматривать диагональные триангуляции специального вида, а именно, так называемые паркеты.

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

Предложение 3. Каждое плоское бинарное дерево, число вращения которого не превосходит 5, планарно эквивалентно двойственной сети некоторого паркета.

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

Пусть 5 — скелет, и Ь — его линейный участок. Сейчас мы определим ось линейного участка Ь, что позволит нам полностью описать линейные участки скелетов из

Если 5 состоит из одной ячейки, то проведем в этой ячейке произвольную среднюю линию. Если 5 состоит из двух ячеек, то проведем в них параллельные средние линии, пересекающиеся с единственным внутренним ребром скелета 5, одним из двух возможных способов. Пусть теперь 5 состоит по

Рис. 2. Линейные участки скелетов из УЛ^

крайней мере из трех ячеек. Проведем во всех некрайних ячейках скелета 5 их средние линии, соединяющие внутренние стороны этих ячеек. В крайних ячейках проведем средние линии, параллельные уже построенным в смежных ячейках. На объединении всех проведенных средних линий введем структуру графа, объявив ребрами максимальные связные прямолинейные совокупности этих линий из не внутренних ячеек, а также все линии из внутренних ячеек. Полученный плоский граф называется осью скелета Б. Далее, пересечение оси скелета й с каждым его линейным участком Ь называется осью линейного участка Ь.

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

Предложение 4. Ось каждого линейного участка Ь скелета из однозначно проектируется на прямую, параллельную некоторой стороне произвольной ячейки.

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

сты, узлы ветвления и линейные участки.

Опишем, как эти элементы крепятся друг к другу. Оказывается, каждый скелет из можно получить из скелетов специального канонического вида, выбрасывая из последних некоторое количество ячеек. Операция "выбрасывания" называется редукцией. Различаются редукции 1-ого и П-ого типа. Пусть Б — некоторый паркет. Редукция 1-ого типа состоит в разрезании паркета Б вдоль внутреннего ребра некоторой ячейки и отбрасывания одной из двух

ЛЛЛЛЛЛЛ7

компонент. Ясно, что редукция 1-ого типа переводит паркет О в некоторый паркет, число вращения которого не больше числа вращения паркета В. Чтобы описать редукцию П-ого типа, напомним, что каждое ребро двойственной сети, соединяющее вершины степени три, пересекает ровно одно внутреннее ребро некогоройячейки паркета. Это задает соответствие между такими ребрами двойственной сети и внутренними ребрами паркета. Итак, редукция Н-ого типа состоит в следующем: выберем два внутренних ребра паркета О, таких что число вращения между соответствующими им ребрами двойственной сети равно нулю; разрежем паркет О вдоль этих ребер; выбросим ту из трех образованных компонент, которая пересекается с обоими оставшимися компонентами; с помощью параллельного переноса склеим оставшиеся две компоненты по ребрам разреза. Можно показать, что если Б € Н^, то описанная операция корректно определена (т.е. после сдвига полученные два паркета пересекаются только по ребрам разреза), и результирующий паркет имеет число вращения, не большее чем у Д в частности, он по-прежнему принадлежит У\Щ.

Выше мы построили код скелета Б, являющийся плоским графом и описывающий топологию скелета 5. Однако код не отражает геометрических особенностей скелета 5, таких как, скажем, взаимного расположения направляющих линейных участков, входящих в 5. Поэтому для описания геометрии скелетов построим схему скелета 5, закодировав каждый узел ветвления кружочком, а каждый линейный участок Ь набором черточек по следующему правилу: если Ь — змея, то поставим ему в соответствие одну черточку, параллельную оси участка £; если Ь — лестница, то поставим ему в соответствие пару пересекающихся черточек, каждая из которых параллельна одной из двух направляющих участка Ь\ если же Ь — ломаная змея, то поставим в соответствие Ь три параллельные между собой черточки и параллельные единственной направляющей участка Ь.

Теперь мы в состоянии сформулировать основную теорему, классифицирующую скелеты из У^Р;.

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

Отметим, что из теоремы 1 вытекает интересное следствие.

Следствие 1. Коды скелетов из — это всевозможные плоские бинарные деревья, каждое из которых имеет не более 6 вершин степени 1. В частности, скелет из содержит не более 6 концевых линейных участков, не более 3 промежуточных линейных участков, и не более 4 внутренних ячеек (а, значит, не более 4 узлов ветвления).

Ориентируем ось каждого концевого участка Ь скелета 5 € Н^ в сторону крайней ячейки, принадлежащей Ь (для 5, не содержащего внутренних ячеек, существует две таких ориентации). Тогда направления ребер так ориентированной оси назовем направлениями концевого участка Ь. Ясно, что всего существует не более шести различных направлений, образующих правильный шестиугольник, вписанный в единичную окружность направлений. Такой шестиугольник назовем шестиугольником направлений.

Рис. 3. Схемы классифицирующих скелетов

Следствие 2. Каждый концевой линейный участок скелета 5 из имеет не более трех различных направлений, причем эти направления — последовательные. Множества направлений, соответствующие любым двум различным концевым линейным участкам из Я, не пересекаются.

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

Оказывается, полученная нами классификация точна, а именно, имеет место следующая теорема.

Теорема 2 (О реализации). Двойственный граф произвольного паркета из эквивалентен некоторому плоскому минимальному бинарному дереву с выпуклой границей.

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

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

Теорема 3. Если скелет имеет правильную минимальную реализацию, то все его концевые линейные участки — змеи (количество концевых линейных участком не превосходит 6).

С точностью до изометрии, следующие скелеты и только они имеют правильную минимальную реализацию на правильном п-угольнике:

• среди скелетов без узлов ветвления — лишь змеи для любого п, рис. 4;

хлллллллллллл

Рис. 4. Представители бесконечных серий скелетов без узлов ветвления и 3-скелетов, имеющих правильную минимальную реализацию

Рис. 5. 6-скелеты, имеющие правильную минимальную реализацию: случаи п = 24 и п = 30

• среди скелетов с одной ячейкой ветвления, т.е. среди 3-скелетов, — лишь скелеты, у которых концевые линейные участки являются змеями, состоящими из одинакового числа ячеек, причем угол между направлениями этих линейных участков равен 120° (концевые линейные участки ориентированы в сторону своих концевых ячеек). В частности, такие скелеты инвариантны относительно вращения вокруг центра единственной ячейки ветвления на угол в 120°, см. рис. 4. Более того, такая реализация существует лишь для п = 6/с + 3, где к — произвольное целое положительное число;

• 4-скелеты и 5-скелеты не имеют правильной минимальной реализации;

• среди 6-скелетов имеется лишь четыре скелета, по одному для каждого п, равного 24, 30, 36 и 42, рис. 5 и 6.

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

Таким образом, среди скелетов, допускающих правильную минимальную

УУУУХ

Рис. 6. 6-скелеты, имеющие правильную минимальную реализацию: случаи п = 36 и п = 42

реализацию, имеется две бесконечные серии и одна конечная серия.

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

Пусть Р = {р,} — правильный га-угольник, вписанный в единичную окружность 51 с центром в нуле, иг — неотрицательное число, меньшее чем л/п. Пусть в = («1,... , 5„) — произвольная последовательность из ±1. Обозначим через т; точку, полученную из р, поворотом на угол и пусть М = {га,}. Многоугольник М называется е-квазиправильным многоугольником типа в.

Теорема 4. Пусть э — периодическая последовательность длины п = 10/; с периодом (—1,1,1,1, —1, —1,1, — 1,1, —1), ие — произвольное положительное число, такое что 7г/(2га) < е < п/п. Тогда при к > 8 множество М вершин е-квазиправильного п-угольника типа 5 нельзя затянуть ни одним минимальным бинарным деревом.

4) Получено полное описание всех невырожденных локально минимальных сетей с выпуклыми границами.

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

Сначала для произвольной сети Штейнера Г, т.е. для сети, степени вершин которой не превосходят 3, определим фундаментальные циклы. А именно, пусть и — произвольная связная компонента множества К2 \ Г, и V — замыкание множества У. Тогда связная компонента С границы д(7 множества У, такая что область, ограниченная С, содержит все остальные связные компоненты множества ЭУ, называется фундаментальным циклом, соответствующим и.

и

Разобьем вершины фундаментального цикла С на внешние, внутренние и вырожденные. Пусть V — произвольная вершина из С. Если вершина и имеет степень 2 в сети Г, то назовем г) вырожденной вершиной. В противном случае, обозначим через е единственное ребро сети Г, инцидентное V и не содержащееся в С. Если е пересекает V по вершине V, то назовем V внешней вершиной, иначе назовем V внутренней вершиной. Обозначим через ¿(С), о(С) и г(С) соответственно количества вырожденных, внешних и внутренних вершин фундаментального цикла С. Имеет место следующий результат.

Предложение 5. Если сеть Штейнера Г планарно эквивалентна некоторой локально минимальной сети, то для каждого фундаментального цикла С из Г выполняется

|о(С) - ¿(С) - 6| < ¿(С).

Пусть теперь Г — невырожденная сеть Штейнера, т.е. Г не содержит вершин степени 2.

Следствие 3. Если невырожденная сеть ШтейнераТ планарно эквивалентна некоторой локально минимальной сети, то для каждого фундаментального цикла С из Г выполняется

о(С) - ¿(С) = 6.

Предложение 6. Если невырожденная сеть Штейнера Г планарно эквивалентна некоторой локально минимальной сети с выпуклой границей, то для каждого фундаментального цикла С из Г выполняется

о(С) = 6, »'(С)= 0.

Иными словами, в любом фундаментальном цикле внутренние вершины отсутствуют, и каждый фундаментальный цикл состоит из шести ребер.

Фундаментальный цикл С, для которого ¿(С1) = 0, г(С) = Ои о(С) ~ б называется тривиальным, а невырожденная сеть Штейнера, все фундаментальные циклы которой тривиальны, также называется тривиальной.

Пусть Г — тривиальная сеть Штейнера, и пусть о и Ь — два произвольных ребра из Г, инцидентных вершинам степени 1 (такие ребра будем называть граничными). Рассмотри произвольный ориентированный путь 7 в Г, начинающийся на а и заканчивающийся на Ъ. Так же, как и выше, определим число вращения 6) упорядоченной пары ребер (а, Ь) вдоль пути 7.

Предложение 7. Пусть Г — тривиальная сеть Штейнера, (а,Ь) — упорядоченная пара граничных ребер изТ, а •/ и у1 — пара ориентированных путей, начинающихся на а и заканчивающихся на Ь. Тогда

Иными словами, в тривиальной сети Штейнера число вращения между граничными ребрами не зависит от пути, их соединяющего.

Последнее предложение позволяет обобщить понятие числа вращения на произвольную упорядоченную пару граничных ребер тривиальной сети Штейнера Г.

Определение. Числом вращения тривиальной сети Штейнера Г называется максимум чисел вращения tw(a, Ь) по всем упорядоченным парам (а, Ь) граничных ребер из Г.

Теорема 5. Если невырожденная сеть Штейнера Г имеет выпуклую минимальную реализацию, то Г — тривиальная сеть Штейнера, и ее число вращения не превосходит 5.

Предложение 8. Каждая тривиальная сеть Штейнера с не превосходящим 5 числом вращения планарно эквивалентна двойственной сети некоторого паркета.

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

Все основные результаты диссертации являются новыми и получены автором самостоятельно. Часть результатов получена автором совместно с А. О. Ивановым и включена в диссертацию для полноты изложения.

Практическая и теоретическая ценность. Диссертация носит теоретический характер. Ее результаты могут быть применены в классической теории абсолютно минимальных сетей.

Апробация работы. Результаты диссертации доложены и обсуждены на многочисленных научных конференция, в том числе, на международных конференциях и математическом конгрессе, а также на ведущих научно-исследовательских семинарах как в России, так и за рубежом. В частности,

— на Ломоносовских чтениях (МГУ, Москва)

— на Зимних математических школах в Воронеже

— на Ташкентской конференции по геометрии инвариантов многообразий (Ташкент, 1992)

— на конференции, посвященной Лобачевскому (Санкт-Петербург, 1992)

— на семинаре по геометрической визуализации под руководством проф. Т. Kunii (Токио, Япония, 1993)

— на Александровских чтениях в МГУ

— на международном математическом конгрессе (Цюрих, Швейцария, 1995)

— на конференции по уравнениям в частных производных и их приложениям (Санкт-Петербург, 1995)

— на конференции, посвященной Чебышеву, (МГУ, Москва, 1996)

— на международной конференции по дифференциальной геометрии (Рио де Жанейро, Бразилия, 1996)

— на научных семинарах в Московском государственном университете

— на семинаре профессора J. Jost в Рурском университете (Бохум, Германия, 1993)

— на семинаре профессора F. Mercury в математическом институте (IMECC университета г. Кампинаса (Камлинас, Бразилия, 1993)

— на семинаре профессора R. Asperty в университете г. Сан-Пауло (Сан-Пауло, Бразилия, 1994)

— на топологическом семинаре в Дортмундском университете (Дортмунд, Германия, 1996)

— на семинаре профессора Б. ШЫеЬгапсИ в Боннском университете (Бонн, Германия, 1996)

— на семинаре профессора Г. Тот! в Хайдельбергском университете (Хайдельберг, Германия, 1996)

— па семинаре профессора Ю. Манина в институте Макса Планка (Бонн, Германия, 1996)

— на семинаре профессора Н. 21езсЬап§ в Рурском университете (Бохум, Германия, 1996)

Публикации. Основное содержание диссертации опубликовано в работах, список которых приводится в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения и семи глав, объем — 399 стр. книжного текста, список литературы содержит 67 названий.

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

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

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

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

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

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

В пятой главе технические результаты четвертой главы применяются к так называемым квазиправильным многоугольникам (неформально, многоугольникам, близким к правильным). Строится бесконечней по п серия квазиправильных п-угольников, каждый из которых не может быть затянут ни одним локально минимальным бинарным деревом. Интересно отметить, что для компьютерного подтверждения доказанной теоремы Даже в случае наименьшего п, равного 80, необходимо проверить столь большое число вариантов, что ни один современный компьютер не в состоянии справиться с этой проблемой.

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

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

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

тальные циклы устроены таким образом, мы называем тривиальными.

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

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

Список РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Тужилин A.A., Фоменко А.Т., Элементы геометрии и топологии минимальных поверхностей. М.: Наука, 1991. (Добавление 1: теоремы 1, 2 и предложения 4, 5, 7, 8, 9 доказаны А. А. Тужилиным).

[2] Иванов А.О., Тужилин A.A., Решение задачи Штейнера для выпуклых границ. Успехи матем. наук, 1990, т. 45, 2, с. 207-208. (Основная теорема и предложения 1, 2 доказаны А. А. Тужилиным).

[3] Иванов А. О., Тужилин A.A., Задача Штейнера для выпуклых границ или плоские минимальные сети. Матем. сб., 1991, т. 182, 12, с. 1813-1844. (Теоремы 1, 2.1, 3, 4.1, и предложения 1.2, 2.3-2.6, 3.1, 3.2, 3.5, 3.6, 3.8, 3.9, 3.12 доказаны А. А. Тужилиным).

[4] Иванов А.О., Тужилик A.A., Геометрия минимальных сетей и одномерная проблема Плато. Успехи матем. наук, 1992, т. 47, 2 (284), с. 53-115. (Теоремы 1.2, 1.3, 3.1-3.8 и предложения 3.3, 3.4, 3.5, 3.9, 3.11-3.14, 3.17 доказаны А. А. Тужилиным).

[5] Ivanov А.О., Tuzhilin A.A., The Steiner problem for convex boundaries, I: general case. Advances in Soviet Mathematics, 1993, vol. 15, pp. 15-92. (Теоремы 1, 2, 3 и предложения 2.2, 4.1, 4.2, 8.1-8.5, 9.1, 10.2-10.7, 11.1, 11.2 доказаны А. А. Тужилиным).

[6] Ivanov А.О., Tuzhilin A.A., The Steiner problem for convex boundaries, II: the regular case. Advances in Soviet Mathematics, 1993, vol. 15, pp. 93-131. (Теоремы 1-6 и предложения 2.1, 2.2 доказаны А. А. Тужилиным).

[7] Ivanov А.О., Tuzhihn A.A., Minimal Networks. The Steiner Problem and Its Generalizations. N.W., Boca Raton, Florida, CRC Press, 1994. (Глава 4: Теоремы 2.1, 2.2; глава 6: теоремы 1.1-1.4, 2.1, 2.2 и предложения 1.1, 1.3, 1.5-1.11, 1.14-1.18, 2.2, 2.3, 2.5, 2.6; глава 7: теоремы 2.1, 3.1, 4.1, 4.2, 5.1, 6.1 и предложения 2.1, 3.1 доказаны А. А. Тужилиным).

[8] Ivanov А.О., Tuzhilin A.A., Some problems concerning minimal networks. International Journal of Shape Modeling, 1994, v. 1, N 1, p. 81-107. (Теоремы 1-5 и предложения 2.1-2.6 доказаны Тужилиным)

[9] Иванов А.О., Тужилин A.A., О минимальных бинарных деревьях с правильной границей. Успехи матем. наук, 1996, т. 51, N 1, с. 139-140. (Основная теорема доказана Тужилиным)

[10] Иванов А. О., Тужилин А. А., Классификация минимальных скелетов с правильной границей, Успехи матем. наук, 1996, т. 51, N 4, с. 157-158. (Основная теорема доказана Тужилиным)

[11] Ivanov А.О., Tuzhilin A.A., Planar Local Minimal Binary Ti-ees with Convex, Quasiregular, and Regular Boundaries. Preprint, 1997, Sonderforschungsbereich 256, 490. (Теоремы 2.1-2.5, 3.1-3.2, 4.1-4.3 доказаны Тужилиным)

[12] Тужилин A.A., Минимальные бинарные деревья с правильной границей: случай скелетов с четырьмя концами. Матем. Сборник, 1996, т. 187, N 4, с. 117-159.

[13] Тужилин A.A., Минимальные бинарные деревья с правильной границей: случай скелетов с пятью концами. Матем. Заметки, 1997, т. 61, N 6.

[14] Тужилин A.A., Полная классификация локально минимальных бинарных деревьев с правильной границей, двойственные триангуляции которых являются скелетами. Фундаментальная и прикладная математика, 1996, т. 2, N 2, с. 511-562.