Введение к работе
Актуальность темы. Настоящая диссертация посвящена изучению локально минимальных плоских связных графов, затягивающих вершины выпуклых многоугольников. Такие графы возникают при решении знаменитой проблемы Штейнера: среди всех сетей (связных одномерных континуумов), затягивающих данное конечное множество М точек плоскости, найти сеть наименьшей длины. Решения проблемы Штейнера называются абсолютно минимальными деревьями. Как было отмечено в историческом обзоре из [1], где цитировались [2] и [3], простейший вариант этой проблемы возник еще в работах Ферма, а в современном виде она была сформулирована Ярником и Кессле-ром [4]. Название "проблема Штейнера" укоренилось благодаря популярности замечательной книги Куранта и Роббинса "Что такое математика?", в которой эта проблема была названа в честь Якоба Штейнера, занимавшегося близкой, но, вообще говоря, другой задачей. Тем не менее, подавляющее большинство специалистов пользуется терминологией, связанной с именем Штейнера, поэтому, вопреки справедливости, нам придется подчиниться традиции, чтобы не вносить путаницу. Отметим, что книга Куранта и Роббинса "Что такое математика?" породила огромный интерес к проблеме Штейнера, о чем свидетельствует обширная литература, посвященная изучению этой проблемы.
Заметим также, что проблему Штейнера можно рассматривать как транспортную задачу, где множеству М соответствуют положения некоторых пунктов, например городов, а сети— система коммуникаций, например дорог, соединяющая эти пункты. При этом абсолютно минимальная сеть — это система коммуникаций, строительство которой будет произведено с наименьшими затратами (здесь естественно предполагается, что затраты пропорциональны длине сети).
Хорошо известна локальная структура абсолютно минимальных сетей, а также алгоритм построения таких сетей, открытый Мелзаком [5]. Тем не менее, как показано в [6] (см. также [7]), проблема Штейнера является NP-полной, и современные компьютеры в состоянии строить ее решения для общих множеств М состоящих из трех-четырех десятков точек, что крайне мало для практических нужд [7]. Поэтому представляет интерес поиск различных геометрических свойств множеств М и связных плоских графов, исходя из которых можно было бы существенно сократить перебор типов сетей, являющихся претендентами на решение проблемы Штейнера. Одним из таких свойств является "выпуклость" граничного множества М, т.е. свойство множества М лежать на границе своей выпуклой оболочки (такие М обычно называют экстремальными, темне менее, мы используем термин выпуклые, чтобы оставить за словом экстремальные смысл, вкладываемый в него в вариационном исчислении, как в выражении "экстремаль функционала длины").
1. F. К. Hwang, D. Richards and P. Winter, Elsevier Science Publishers (в печати). 2. Я. W. Kuhn, In the book Studies in Optimization, ser. Studies in Math., vol. 10, Math. Assoc. Amer., edited by G. B. Dantzig and В. C. Eaves, 1975, pp. 53-70. 3. M. Zachartas, Encyklopadie der Mathematischen, Wissenschaften, vol. Ill АВЭ. 4. V. Jarnik and M. Kossler, 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 принадлежат граничному множеству М). Однако задача описания всех локально минимальных сетей, затягивающих данное множество М, существенно сложнее.
Так, например, если множество М является множеством вершин правильного n-угольника, то, как было показано Ярником и Кесслером в [4], при п > 13 каждая абсолютно минимальная сеть, затягивающая М, состоит из всех сторон этого n-угольника, за исключением любой одной. Кроме того, Ярник и Кесслер построили очевидные абсолютно минимальные сети для случаев п = 3, 4, 5. Лишь в 1987 Ду и Хванг завершили описание абсолютно минимальных сетей, затягивающих вершины правильных многоугольников, доказав, что для п > 6 ответ такой же, как и для п > 13.
Одно из приложений, рассматриваемых в настоящей диссертации, посвящено описанию всех локально минимальных деревьев, затягивающих вершины правильных многоугольников. Как следствие общей теории, развиваемой в диссертации, эта задача полностью решается для важного класса плоских бинарных деревьев, называемых скелетами. Оказывается, что множество всех локально минимальных бинарных деревьев, затягивающих вершины правильных n-угольников и являющихся скелетами, состоит из двух бесконечных по п серий (в одной серии п принимает любое значение, а в другой серии п может быть лишь вида 6fc + 3, где к — любое целое положительное число) и одной конечной серии (здесь п принимает лишь следующие значения: 24, 30, 36 и 42).
Локально минимальные сети, не являющиеся, вообще говоря, абсолютно минимальными, могут быть получены экспериментально, см., например, в [9], [10], [11]. Таким образом, локально минимальные сети имеют и самостоятельный интерес.
Цель работы. Выяснить, какие ограничения накладывает выпуклость граничного множества М на топологии локально минимальных сетей, затягивающих М. Выявить, как дополнительные ограничения на выпуклые границы М, такие, скажем, как правильность множества М (т.е. когда М — множество вершин правильного многоугольника) или квазиправильность множества М (когда М "близко" к множеству вершин правильного многоугольника), влияют на возможные топологии локально минимальных сетей, затягивающих М.
8. F. К. Hwang, Орег. Res. Letter, 1986, vol. 5, pp. 235-237. 9. Z. A. Meteak, 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 дерева Г, лежащая внутри у, т.е. не совпадающая ни с одной из его концевых вершин. Выберем круговую окрестность U вершины Р, такую что U Л Г является деревом, не содержащим вершин из Г, отличных от Р. Тогда пересечение dU ПГ состоит из трех точек, которые мы обозначим через Л;, г = 1, 2, 3. Пусть ai — первое, и 02 — последнее ребро из 7i инцидентное Р, и пусть Л,- Є а;, і = 1, 2. Рассмотрим дугу 5 окружности дії, лежащую между А\ и Л2 и содержащую Лз-
Определение. Если движение по дуге 5 от Лі к А2 происходит по часовой стрелке, то будем говорить, что мы поворачиваем направо в точке Р, и припишем Р число —1. В противном случае, скажем, что мы поворачиваем налево в точке Р и припишем Р число +1. Число, приписанное вершине Р, называется твистингом вершины Р ориентированного пути у. Числом вращения tw(a,b) упорядоченной пары (а,Ь) ребер плоского бинарного дерева Г называется сумма твистингов во всех внутренних вершинах пути 7- Положим, по определению, tw(o, a) = 0.
Определение. Числом вращения twT бинарного дерева Г называется максимум чисел вращения tw(a, b), взятый по всевозможным упорядоченным парам ребер из Г.
Предложение 1. Плоское бинарное дерево Г планарно эквивалентно некоторому локально минимальному бинарному дереву с выпуклой границей тогда и только тогда, когда twT < 5.
Напомним, что плоские бинарные деревья можно описывать на двойственном языке, а именно с помощью триангуляции диагоналями плоских многоугольников: по каждой диагональной триангуляции Т многоугольника W можно построить плоское бинарное дерево Тті называемое двойственной сетью этой триангуляции, и обратно, по каждому плоскому бинарному дереву Г
можно построить некоторую диагональную триангуляцию Т, такую что двойственная сеть Гт этой триангуляции планарно эквивалентна Г. Треугольники таких триангуляции будем называть ячейками.
Если двойственная сеть диагональной триангуляции Т обладает некоторым свойством, то мы, в дальнейшем, будем говорить, что сама триангуляция Т обладает этим свойством. Так, например, совокупность ячеек из Г называется связной, если пересечение двойственной сети Гт с этими ячейками связно. Или, скажем, число вращения сети Гт будем называть числом вращения триангуляции Т. Также, будем говорить, что диагональная триангуляция Т имеет выпуклую минимальную реализацию, если ее двойственная сеть Гт планарно эквивалентна некоторому локально минимальному бинарному дереву с выпуклой границей. Из предложения 1 вытекает, что для описания всех локально минимальных бинарных деревьев с выпуклой границей достаточно расклассифицировать все диагональные триангуляции с числом вращения, не превосходящим 5. Множество всех таких триангуляции будем обозначать через \Щ.
Пусть Т — произвольная триангуляция диагоналями многоугольника W (такие триангуляции будем называть диагональными), и А — любая ее ячейка. Назовем Д крайней ячейкой, если по меньшей мере две ее стороны являются сторонами W. Ячейка Д называется внутренней, если ни одна из ее сторон не есть сторона из W. Если две ячейки пересекаются по стороне, то мы называем их смежными и говорим, что одна из них примыкает ко второй. Крайняя ячейка, примыкающая к внутренней, называется наростом, а триангуляция Т без наростов называется скелетом. Если для каждой внутренней ячейки триангуляции Т из всех примыкающих к ней наростов (если они есть) выбросить ровно один, то, как легко проверить, полученная триангуляция Г' уже не будет содержать наростов, т.е. Т является скелетом, который называется скелетом триангуляции Т. Таким образом, мы построили, вообще говоря, неоднозначное разложение триангуляции Т на скелет и наросты. Эта неоднозначность возникает при наличии концевых наростов — пары наростов, примыкающих к одной и той же внутренней ячейке.
Оказывается, для триангуляции из У/Щ скелеты устроены достаточно просто. Наша классификация состоит из двух частей: сначала описываются все скелеты из Wf%, а затем то, как можно к ним прикреплять наросты, не выходя при этом из класса W1%. Мы приведем здесь лишь описание скелетов из W/J. Первый шаг в описании скелетов — это разложение их на линейные участки и узлы ветвления.
Пусть S — произвольный скелет (не обязательно из W?5). Связные компоненты множества внутренних ячеек скелета S называются узлами ветвления, а связные компоненты скелета S, из которого выброшены все внутренние ячейки, называются линейными участками. Линейный участок, содержащий крайнюю ячейку, называется концевым, а не содержащий — промежуточным. Если скелет S содержит к концевых линейных участков, то S будем называть к-скелетом.
Построенное разбиение скелета S позволяет определить код этого скелета как плоский граф, вершины которого соответствуют крайним и внутренним ячейкам из S, а ребра — линейным участкам и внутренним ребрам скелета S, по которым пересекаются смежные внутренние ячейки. Как будет показано
Л zv
AZV Z
Рис. 1. Узлы ветвления скелетов из W%
ниже, код скелета из W?J устроен достаточно просто.
Следующее предложение полностью описывает все возможные узлы ветвления скелетов из W%.
Предложение 2. Узлы ветвления скелетов из W% могут быть ровно 5 типов, приведенных на рис. 1.
Опишем теперь линейные участки скелетов из VV7J. Чтобы это описание было наглядным, оказывается полезным рассматривать диагональные триангуляции специального вида, а именно, так называемые паркеты.
Диагональная триангуляция, все ячейки которой— правильные (конгруэнтные) треугольники, называется паркетом. Следующее предложение показывает, что при изучении локально минимальных бинарных деревьев с выпуклой границей можно ограничиться паркетами.
Предложение 3. Каждое плоское бинарное дерево, число вращения которого не превосходит 5, планарно эквивалентно двойственной сети некоторого паркета.
Итак, в дальнейшем всегда будем предполагать, что рассматриваемые диагональные триангуляции являются паркетами. Кроме того, для паркетов двойственную сеть удобно выбрать специальным образом: в качестве вершин такой двойственной сети возьмем центры ячеек и середины граничных сторон, а все ребра будем считать отрезками, соединяющими соответствующие вершины. Именно такие бинарные деревья мы и будем иметь в виду, говоря о двойственных сетях паркетов. Отметим, что двойственная сеть каждого паркета является локально минимальным бинарным деревом с границей, состоящей из всех вершин степени 1.
Пусть 5 — скелет, и L — его линейный участок. Сейчас мы определим ось линейного участка L, что позволит нам полностью описать линейные участки скелетов из W7J.
Если S состоит из одной ячейки, то проведем в этой ячейке произвольную среднюю линию. Если S состоит из двух ячеек, то проведем в них параллельные средние линии, пересекающиеся с единственным внутренним ребром скелета S, одним из двух возможных способов. Пусть теперь S состоит по
Рис. 2. Линейные участки скелетов из VWJ
крайней мере из трех ячеек. Проведем во всех некрайних ячейках скелета 5 их средние линии, соединяющие внутренние стороны этих ячеек. В крайних ячейках проведем средние линии, параллельные уже построенным в смежных ячейках. На объединении всех проведенных средних линий введем структуру графа, объявив ребрами максимальные связные прямолинейные совокупности этих линий из не внутренних ячеек, а также все линии из внутренних ячеек. Полученный плоский граф называется осью скелета S. Далее, пересечение оси скелета S с каждым его линейным участком L называется осью линейного участка L.
Следующее предложение описывает все линейные участки скелетов из Wfjj.
Предложение 4. Ось каждого линейного участка L скелета из WJ% однозначно проектируется на прямую, параллельную некоторой стороне произвольной ячейки.
Прямая из предложения 4 называется направляющей линейного участка L. Отметим, что, с точностью до параллельности, существует ровно три прямые, каждая из которых параллельна какой-нибудь стороне произвольной ячейки. В дальнейшем, говоря о направляющих, будем отождествлять параллельные прямые, поэтому, например, имеет смысл говорить, что линейный участок обладает одной направляющей (т.е. все направляющие линейного участка параллельны). Принимая во внимание сделанные замечания и соглашение, отметим, что существует не более трех направляющих. Если линейный участок обладает тремя направляющими, то он называется змеей, если двумя — то лестницей, и, наконец, если одной — то ломаной змеей, см. рис. 2. Таким образом, описаны основные структурные элементы паркетов из \0%: наросты, узлы ветвления и линейные участки.
Опишем, как эти элементы крепятся друг к другу. Оказывается, каждый скелет из И#5 можно получить из скелетов специального канонического вида, выбрасывая из последних некоторое количество ячеек. Операция "выбрасывания" называется редукцией. Различаются редукции 1-ого и П-ого типа. Пусть D — некоторый паркет. Редукция 1-ого типа состоит в разрезании паркета D вдоль внутреннего ребра некоторой ячейки и отбрасывания одной из двух
компонент. Ясно, что редукция 1-ого типа переводит паркет D в некоторый паркет, число вращения которого не больше числа вращения паркета D. Чтобы описать редукцию П-ого типа, напомним, что каждое ребро двойственной сети, соединяющее вершины степени три, пересекает ровно одно внутреннее ребро некоторой ячейки паркета. Это задает соответствие между такими ребрами двойственной сети и внутренними ребрами паркета. Итак, редукция Н-ого типа состоит в следующем: выберем два внутренних ребра паркета D, таких что число вращения между соответствующими им ребрами двойственной сети равно нулю; разрежем паркет D вдоль этих ребер; выбросим ту из трех образованных компонент, которая пересекается с обоими оставшимися компонентами; с помощью параллельного переноса склеим оставншеся две компоненты по ребрам разреза. Можно показать, что если D Є W^, то описанная операция корректно определена (т.е. после сдвига полученные два паркета пересекаются только по ребрам разреза), и результирующий паркет имеет число вращения, не большее чем у D, в частности, он по-прежнему принадлежит Wf$.
Выше мы построили код скелета S, являющийся плоским графом и описывающий топологию скелета S. Однако код не отражает геометрических особенностей скелета S, таких как, скажем, взаимного расположения направляющих линейных участков, входящих в S. Поэтому для описания геометрии скелетов построим схему скелета S, закодировав каждый узел ветвления кружочком, а каждый линейный участок L набором черточек по следующему правилу: если L — змея, то поставим ему в соответствие одну черточку, параллельную оси участка L; если L — лестница, то поставим ему в соответствие пару пересекающихся черточек, каждая из которых параллельна одной из двух направляющих участка L; если же L — ломаная змея, то поставим в соответствие L три параллельные между собой черточки и параллельные единственной направляющей участка L.
Теперь мы в состоянии сформулировать основную теорему, классифицирующую скелеты из W7J.
Теорема 1. Каждый скелет из VV% может быть получен кратным применением редукции к скелету одного из трех канонических типов, схемы которых приведены на рис. 3.
Отметим, что из теоремы 1 вытекает интересное следствие.
Следствие 1. Коды скелетов из VWJ — это всевозможные плоские бинарные деревья, каждое из которых имеет не более 6 вершин степени 1. В частности, скелет из У\Я$ содержит не более 6 концевых линейных участков, не более 3 промежуточных линейных участков, и не более 4 внутренних ячеек (а, значит, не более 4 узлов ветвления).
Ориентируем ось каждого концевого участка L скелета S Є WJ% в сторону крайней ячейки, принадлежащей L (для 5, не содержащего внутренних ячеек, существует две таких ориентации). Тогда направления ребер так ориентированной оси назовем направлениями концевого участка L. Ясно, что всего существует не более шести различных направлений, образующих правильный шестиугольник, вписанный в единичную окружность направлений. Такой шестиугольник назовем шестиугольником направлений.
/-/-
Рис. 3. Схемы классифицирующих скелетов
Следствие 2. Каждый концевой линейный участок скелета S из W?5 имеет не более трех различных направлений, причем эти направления — последовательные. Множества направлений, соответствующие любым двум различным концевым линейным участкам из S, не пересекаются.
Если ориентировать границу скелета S, для определенности, против часовой стрелки, что задаст циклический порядок на множестве концевых линейных участков, а также ориентировать шестиугольник направлений против часовой стрелки, что задаст циклический порядок на семействе множеств направлений концевых линейных участков, то оба возникших порядка будут согласованы: последовательные концевые участки будут иметь последовательные множества направлений.
Оказывается, полученная нами классификация точна, а именно, имеет место следующая теорема.
Теорема 2 (О реализации). Двойственный граф произвольного паркета из WF^ эквивалентен некоторому плоскому минимальному бинарному дереву с выпуклой границей.
2) Получено полное описание всех локально минимальных бинарных деревьев, затягивающих вершины правильных многоугольников, в случае, когда соответствующие им диагональные триангуляции являются скелетами.
Мы говорим, что паркет имеет правильную минимальную реализацию, если его двойственная сеть планарно эквивалентна локально минимальному бинарному дереву, затягивающему вершины правильного многоугольника. В соответствие с вышесказанным, все такие паркеты принадлежат Y/J%.
Теорема 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) Построена бесконечная серия квазиправильных многоугольни
ков (многоугольников, множества вершин которых лежат на окруж
ности и не сильно отличаются от множеств вершин соответству
ющих правильных многоугольников), которые нельзя затянуть ни
одним локально минимальным бинарным деревом.
Пусть Р = {pi} — правильный га-угольник, вписанный в единичную окружность S1 с центром в нуле, иг — неотрицательное число, меньшее чем тг/п. Пусть s = («і,... , sn) — произвольная последовательность из ±1. Обозначим через т; точку, полученную из р, поворотом на угол s;, и пусть М = {тп,}. Многоугольник М называется е-квазиправильным многоугольником типа s.
Теорема 4. Пусть s — периодическая последовательность длины п = Wk с периодом (-1,1,1,1,-1,-1,1,-1,1,-1), иє — произвольное положительное число, такое что 7г/(2га) < є < п/п. Тогда при к > 8 множество М вершин є-квазиправильного п-уголъника типа s нельзя затянуть ни одним минимальным бинарным деревом.
4) Получено полное описание всех невырожденных локально ми
нимальных сетей с выпуклыми границами.
Для описания таких сетей мы обобщаем понятие паркета на случай триангуляции, допускающих внутренние вершины. Теперь мы называем паркетами общие триангуляции (не обязательно диагональные), составленные из правильных треугольников. (В действительности, паркеты, являющиеся диагональными триангуляциями, в диссертации называются деревянными в силу того, что двойственные сети таких триангуляции— деревья.)
Сначала для произвольной сети Штейнера Г, т.е. для сети, степени вершин которой не превосходят 3, определим фундаментальные циклы. А именно, пусть U — произвольная связная компонента множества R2 \ Г, и U — замыкание множества U. Тогда связная компонента С границы dU множества U, такая что область, ограниченная С, содержит все остальные связные компоненты множества dU, называется фундаментальным циклом, соответствующим U.
Разобьем вершины фундаментального цикла С на внешние, внутренние и вырожденные. Пусть v — произвольная вершина из С. Если вершина v имеет степень 2 в сети Г, то назовем v вырожденной вершиной. В противном случае, обозначим через е единственное ребро сети Г, инцидентное v и не содержащееся в С. Если е пересекает U по вершине v, то назовем v внешней вершиной, иначе назовем v внутренней вершиной. Обозначим через d(C), о(С) и г(С) соответственно количества вырожденных, внешних и внутренних вершин фундаментального цикла С. Имеет место следующий результат.
Предложение 5. Если сеть Штейнера Г планарно эквивалентна некоторой локально минимальной сети, то для каждого фундаментального цикла С из Г выполняется
\о(С) - І(С) - 6\ < d(C).
Пусть теперь Г — невырожденная сеть Штейнера, т.е. Г не содержит вершин степени 2.
Следствие 3. Если невырожденная сеть ШтейнераТ планарно эквивалентна некоторой локально минимальной сети, то для каждого фундаментального цикла С из Г выполняется
о(С) - i(C) = 6.
Предложение 6. Если невырожденная сеть Штейнера Г планарно эквивалентна некоторой локально минимальной сети с выпуклой границей, то для каждого фундаментального цикла С из Г выполняется
о(С) = 6, .-(С)=0.
Иными словами, в любом фундаментальном цикле внутренние вершины отсутствуют, и каждый фундаментальный цикл состоит из шести ребер.
Фундаментальный цикл С, для которого d(C) = 0, i(C) = 0 и о(С) = б называется тривиальным, а невырожденная сеть Штейнера, все фундаментальные циклы которой тривиальны, также называется тривиальной.
Пусть Г — тривиальная сеть Штейнера, и пусть а и b — два произвольных ребра из Г, инцидентных вершинам степени 1 (такие ребра будем называть граничными). Рассмотрим произвольный ориентированный путь у в Г, начинающийся на а и заканчивающийся на Ь. Так же, как и выше, определим число вращения twT(a, 6) упорядоченной пары ребер (а,Ь) вдоль пути 7-
Предложение 7. Пусть Г — тривиальная сеть Штейнера, (а,Ь) — упорядоченная пара граничных ребер из Т, a у и у' — пара ориентированных путей, начинающихся на а и заканчивающихся на Ь. Тогда
tw7(a,6) = twy(a',b').
Иными словами, в тривиальной сети Штейнера число вращения между граничными ребрами не зависит от пути, их соединяющего.
Последнее предложение позволяет обобщить понятие числа вращения на произвольную упорядоченную пару граничных ребер тривиальной сети Штейнера Г.
Определение. Числом вращения тривиальной сети Штейнера Г называется максимум чисел вращения tw(a, о) по всем упорядоченным парам (а, Ь) граничных ребер из Г.
Теорема 5. Если невырожденная сеть Штейнера Г имеет выпуклую минимальную реализацию, то Г — тривиальная сеть Штейнера, и ее число вращения не превосходит 5.
Предложение 8. Каждая тривиальная сеть Штейнера с не превосходящим 5 числом вращения пленарно эквивалентна двойственной сети некоторого паркета.
Два последних результата позволяют использовать язык паркетов для описания невырожденных сетей Штейнера, имеющих правильную минимальную реализацию. Так как полученные описания достаточно сложны, мы не будем здесь приводить точного результата.
Все основные результаты диссертации являются новыми и получены автором самостоятельно. Часть результатов получена автором совместно с А. О. Ивановым и включена в диссертацию для полноты изложения.
Практическая и теоретическая ценность. Диссертация носит теоретический характер. Ее результаты могут быть применены в классической теории абсолютно минимальных сетей.
Апробация работы. Результаты диссертации доложены и обсуждены на многочисленных научных конференция, в том числе, на международных конференциях и математическом конгрессе, а также на ведущих научно-исследовательских семинарах как в России, так и за рубежом. В частности,
на Ломоносовских чтениях (МГУ, Москва)
на Зимних математических школах в Воронеже
на Ташкентской конференции по геометрии инвариантов многообразий (Ташкент, 1992)
на конференции, посвященной Лобачевскому (Санкт-Петербург, 1992)
на семинаре по геометрической визуализации под руководством проф. Т. Kunii (Токио, Япония, 1993)
на Александровских чтениях в МГУ
на международном математическом конгрессе (Цюрих, Швейцария, 1995)
на конференции по уравнениям в частных производных и их приложениям (Санкт-Петербург, 1995)
на конференции, посвященной Чебышеву, (МГУ, Москва, 1996)
на международной конференции по дифференциальной геометрии (Рио де Жанейро, Бразилия, 1996)
на научных семинарах в Московском государственном университете
на семинаре профессора J. Jost в Рурском университете (Бохум, Германия, 1S93)
на семинаре профессора F. Mercury в математическом институте (IMECC] университета г. Кампинаса (Кампинас, Бразилия, 1993)
на семинаре профессора R. Asperty в университете г. Сан-Пауло (Сан-Пауло, Бразилия, 1994)
на топологическом семинаре в Дортмундском университете (Дортмунд, Германия, 1996)
на семинаре профессора S. Hildebrandt в Боннском университете (Бонн, Германия, 1996)
на семинаре профессора F. Tomi в Хайдельбергском университете (Хайдельберг, Германия, 1996)
на семинаре профессора Ю. Манина в институте Макса Планка (Бонн, Германия, 1996)
на семинаре профессора Н. Zieschang в Рурском университете (Бохум, Германия, 1996)
Публикации. Основное содержание диссертации опубликовано в работах, список которых приводится в конце автореферата.
Структура и объем диссертации. Диссертация состоит из введения и семи глав, объем — 399 стр. книжного текста, список литературы содержит 67 названий.
