Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 7
Текст из файла (страница 7)
А именно, они показали, что р[з) = !пХ [1-ь[РХ)~1-со[ЛХ)) = хуэ12 лх=!А и с! си-' еде через Хо„[ЛХ) обозначена длина мииимального остовного дерева, 'затягивающего множество Л1, Поэтому, о ссвидпо, р < р[3) < ху312. В той жс работе Гилберт и Поллак выдвнпулн следукяпую ! ипотезу. Гипотеза 1 (Гилберт, Поллак) Оп~ношснис Шп~сйнсро р равно ъ'31'2 = 0,86602э4... За доказательство этой гипотезы шла упорная борьба, длившаяся 24 года.
Поллак [33) показал, что гипотеза справедлива для множеств ЛХ, состоящих из и, = 4 точек. Х[у, Хвапг и Яо [18) распространили этот результат на случай п = б. а затем Рубинштейн и '1омас [36] па случай и = 6. С другой стороны предпринимались попытки получить оценки снизу на р. Гилберт и Поллак сообщают [22), что Моор установил справедливость исравснства О, 5 < р.
Затем оценка послсдовательио улучшалась так: !'рэхсм Краткое содержание диссертации и Хванг О, 57 < р; «1анг и Хванг О, 74 < р; Ду и Хванг О, 8 < р: Чанг и Грэхем О, 824 < р. И наконец, когда стало ясно, что за сотые и тысячные доли можно бороться до бесконечности, Ду и Хванг в своих блестящих работах (!3) и (14) получили доказательство гипотсзьь Гилберта — Поллака в общем случае. Л именно, была доказана теорема. Предложенио 1О (Ду, Хвапг) Гипотеза Гчыбсутщ По,члолсь ве1ьно, о чь,яензд ьо 5 Краткое содержание диссертации Опишем теперь структуру диссертации.
В первой главе формулируются основныс определения и доказываются наиболее общие результаты о локально минимальных сетях, такие как теорема о локальной структуре локально минимальных сетей, свойство выпуклой оболочки грани шого мнолссства локально мини«сальной сети и т.д.
Во второй главе приводится классификация пока.льно минимеаььных бинарных деревьев с выпуклой гранипей. Для этого вводится понятие чис,ьсь ври«лючия ьь.чоснсяю бинарного с!е!ьеоо, описывающего "степеш закрученности' таких деревьев, и доказывается теорема о том, что у локально минимальных бинарных деревьев с выпуклой границей число врщцспия нс превосходит 5. Далее, плоские бинарные деревья изучаются на двойственьчом языке,диагональных триангуляций, важным частным случаем которых являются парис-соль, т.е. дна«опальные триангуляции, составленные из правильных треугольников.
Парксты оказываются чрезвычайно удобными для описания локально минимальных бинарных деревьев с выпуклыми граннпами в силу того, что они одновременно 'хорошо чуьзствуьот' как экстре«сальность соответствующих им сетей, так и выпуклость границы этих сетей, и, более того, мноь о различных дополнительных оь раничений на границу, таких как, скажем, правильность или квазиправильность граничного множества.
Использование диагональных триангуляций позволяет более естествснным образом описывать глобальную ст1зуьстуру плоских бинарных деревьев, в частности, определить важное разбиение диагональной триангуляции на скелет и норогшы. Это разбиение оказывается очень по.ьезным в нашем случае, так как скелеты, имеющие выпуклую,лпьььчь.чсасььную реп„нюоцию (двоиствешьые сети этих скелетов планарпо эквивалентны локально минимальным бинарным деревьям с выпуклыми границами), устроены достаточно регулярным об1зазом и зьогут быть .легко описаны. Наросты, в отличии от скелетов, можно рассматривать как 'случайные элеллеььтьг, чем и ооъясняется введенная терминология. От летим, что классификационная теорема состоит из двух частеи: сначала мы описываем вес* скелеты, двойствснныс соти которых имеют число вращения, Краткое содержание диссертации пе превосходящее 5, а затем то, как к таким скелетам можно прикреплять наросты, чтобы двойственные сети нолучешзых в результате днагонщсьных триангуляций по-прежнему имели число вращения, не превосходящее 5.
В заключение второй главы мы доказываем теорему реализации: каждая диагональная трианс уляцця, двойственная сеть которой имеет нс превосходящее 5 число вращения, имеет выпуклую миниьсальную рсалнзапию. При этом приводимое доказательство конструктивно, а именно, оцо описывает алгоритм, позволяющий по данному паркету с не превосходящим 5 числом вращения явно построить нсюзторое локально минимальное бинарное дерево с выпуклой границей. В третьей главе рассматриваются вопросы прагильион .иинииильной реализации: двойственные сети каких из найденных во второй главе паркетов п.ланарно эквивалентны минимальным бпнарным деревьям, затягивающим вершины правильных п-угольников. Развивая результаты второй главы, мы приводи л полную классификшппо скелетов, имеющих правильнук> минимальную рса.сизацикз. Неожиданным являетгя тот факт, что существует две бесконечные по и серии таких скелетов, и о,лна конечная.
В четвертой главе теория паркетов, имеющих выпуклую минимальную реализяцизо, находит свое,дальнейшее развитие. Приводится большое ко.плчество оценок, описывающих р;юли шые геометрические характерслстнки таких паркетов нсхо,ся из свойств соответствуюппзх граничных множеств. В пятой главе технические результаты четвертой главы применяются к так называемым кьсззспзригсзльньслс жззогоргосльииким (нефсзрмазсьззо, многоугольникам, близким к ирззззильзсыьс).
Строится бесконечная по п серия квазиправильных п-уз ольтсков, каждый из которых нс может быть затянут ни одшпл локально минимальнылс бинарным деревом. Интересно озметить, что для компьютерного подтверждения доказанной теоремы далсс в случае наименьшего и,, равного 80, необходимо проверить столь большое число варнантозз, что ни олин современный компьютер пе в состоянии справиться с этой проблемой. В шестой главе вновь испо,сьэуются технические результаты четверсой главы и доказываются теоремы, описывающие новые ограни сепия на паркеты общего вида, обладающие правильной минима.зьной реализацией. В седьмой глино мьс переносим технику паркетов па случай триангуляций более общего вида, двойствснныс сети которых соответствуют невырожденным сетям П!тейнера, т.е.
сетям, степени вершин которых могут равняться только ! и 3 1стспсрь сети могут иметь циклы). для этого мы определяем паркет как триангуляцию некоторого многоугольника, все треугольники которой правильные. П отличие от опрсделснил, данного выше, теперь паркеты могут иметь внутренние ззерцплпы. (П действительности, паркеты, являкяпиеся диагональными триангуляпиями, в диссертации называются сЗсрсалнньс.яи в силу того, что двойственные сети таких триангуляций деревья.) 26 Основные результаты диссертации Далее, мы вводим понятие фундаментального цикла и показываем, что если невырожденпая сеть 1Птейпера имеет выпуклую минимальную реализацию, то каждый се фундаментальный пики состоит из шести ребер и внутри его пст других вершин сети.
Невырождспныс ости Штсйнсра, у которых фундаментальные циклы устроены таким образом, мы называем трпваальнылп. Оказывается, для тривиальных сетей Г можно естественно определить число врон!елин и показать, что если Г имеет выпуклую минимальную реализацию, то сс число вращения не превосходит 3. Используя зтот факт, мы доказываем, что кюкдая невырож,лепная сеть Штейнера плапарпо эквивалентна двойственной сети некоторого паркета.
Таким образом. мы сводим задачу описания локально минимальных невырожденных сетей 1!1тейнера с выпуклыми границами к описанию всех паркстов с числом вращения, нс превосходящим з. 6 Основные результаты диссертации Приведем основныс определения и результаты диссертации. 1) Получона полная классификация, локально минимальных бинарных деревьев с выпуклой границей. Хотя в диссертании приводится классификация в терминах диагона;и,— ных триангуляций специального вида, а именно, триангуляций, у которых все треугольники правильныс !мы называем такие триангуляпии паркетами), з,лесь мы сформулируем основную теорему непосредственно па языке графов, без использования триангуляций. Ото делается для того, чтобы было более понятно, какими объектами из теории графов мы пользуемся в наших построениях. Чтобы не зш ромождать описание, мы сразу будем предполагать, что все рассмагрлваемые бинарные деревья содержат не менее трех вершин сгепени 3. Отметим, что каждое плоское бинарное дерево, имеющее меньше трех вершин степени 3, планарно зквнвачентно некоторому локалы|о минимальному дереву с выпуклой границей, в качестве которо1 о можно взять, например, очсвидныс абсолютно минимальныс дсревья.
затя~ ивающие вершины правильных и-угольников для и < 4. Пусть Г плоское бинарное дерево, (а, 5) некоторая (упорядоченная~ пара его рсбср, и ~ единственный путь в Г, соединяющий зти рсора. Ориентпрусм путь ч от а к Ь. и пусть Р произвольная вершина степени :5 дерева !', лежащая внутри д т.е. не совпадающая пи с одной из его концевых вершин. Выберем круговую окрестность П вершины Р, такук> что НОГ является деревом, нс содержащим вершин из Г, отличных от Р. Тогда пересечение дП О Г состоит из трех точек, которзле мы обозначим через Л„ ! = 1, 2, 3. Пусть а1 первое, и из последнее ребро из -,~, инцидснтнос Р, и пусть Л, Е а„, з,' = 1, 2. Рассмотрим дугу Б окружности дП, лежащую Основные результаты диссертации 27 между Ль и Лз и пс содсрькшцую Лз. Определение.
Если движение по дуге 6 от Лз к:1ь происходит по часовой стрелке, то будем говоритьь что мы поворачиваем направо в то ьке Р, и припишем Р число — !. В противном случае., ока кем, что мы поворачиваем налево в точке Р и припишем Р число +1. '1исло, приписанное вершине Р, называстсн пшисьпиигом всрьиииы Р ориентированного пути. 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
