Классификация локально минимальных плоских сетей с выпуклыми границами (1097579)
Текст из файла
51 ОСКО ВСКИЙ !'О СУДЛ РС ТВЕН НЫ Й УНИ ВЕРС И'!'ЕТ имени М. В. 7!05!ОПОСОВЛ МЕХАНИКО-МЛ ! ЕМА ! ИЧЕСКИ!7! с! Лку71Ы! ЕТ Па правах рукописи ТУЖ11ЛИП Алексей Августинович УДК 5!4.77+512.816.4+517.924.8 Кй!ЛСС!4с1>ИКЛПИН 7!ОКЛЛВНО МИНИМЛ,!НзНВ!Х ПЛОСКИХ СЕТЕЙ С ВЫПУК51ЫМИ ГРАНИЦАМИ О!.01.04 геометрия и топология 7! !! С С Е Р Т Л П И !! на соискание ученой степени доктора физико математических наук Москва 1997 Введение 1 4 !1 !2 14 ! 2 3 1 Осн 1 2 3 4 43 44 46 49 7 9 66 Минимальная реализация невырожденных графов и сетей Штсйнера 67 69 10 Содержание Исторический обзор . Осповныс результаты теории абсолютно минимальных сетей 2.! Оболочки Штейпера 2.2 ! сксагональная система координат .
2.3 Лбсолотно минимальные деревья, затягиваюшие множества специального вида М!ияимельпые ос|он)~ые де!~свая 3.1 Трианеуляция Делоне и диаерамма Вороного . Отношение 1Птсйнера . Краткое со!!ержапие диссертации Основные результаты диссертации . овныо опродеяения и общие продваритсшьные результаты Тополе~ ические ~ рафы Операции над тополо1нческимп графами Минимальные сети !окальное устройство зипимельпых сетей Л!яяимальцзя реаяизапия с данной границей 5.1 Алгоритм Мензака 5.2 Алгоритм Хванга 5.3 Следствия яз алгоритмов Меязака и Хванга Ст1эуктура минимальных остей с данными топологией и гра няней Постановка основной задачи .
Минимальная реализация деревьев Штсйнера Ъ!инимальная реализация сетей 1Птсйпера: оГ>ший случай 16 19 21 23 26 53 51 56 Гз9 !П 63 и 70 пуклои границои вы 1 83 84 86 87 сП 92 с!4 96 96 97 98 с!с! 102 102 103 103 7 2 Полная классификация минимальных бинарных деревьов с Число врашсния минимального бинарного дерева с выпуклой границей Плоские бинарныс деревья и диагональные триангуляции 2.1 Соответствие между плоскими бинарными деревьями н диагональными триангуляцияьлп 2.2 Структурные элементы л!исм овальных триапгуляпий Паркетная реализация бинарных деревьев с нс превосходящим пяти числом вращения Паркеты лл их свойства .
4.1 Разбиения паркета на скелет и наросты . 4.2 Разбиение деревянного скелета на узлы ветвления и линсйпыс участки . Ось Число в!кащ~ ния ломаной . Осевой граф Связь между числом вращения линсйнол о дсревяннол о скелета и его оси Структурные элементы скелетов иэ И7л .. 5.1 Узлы ветвления деревянных скелетов 5.2 31ипгйные участки Операции редукции и антиредукцпи 6.1 Разрезание и склейка . 5.2 Редукция плоского бинарного ~серена 6.3 Редукция паркетов из ИсРо 6.1 Лцтире !укция плоских бинарных деревьев 6.5 Антирслукцня паркетов из Илеса Воковины и их свойства 7.1 Определение боковин . 7.2 '1исла вращения ребер контура 7.3 Связь между числами вращения боковин и числом вращения паркета .
7.4 Терминологические замечания "1'еорема классифллкапии скелетов из ИсРз 8.1 Число концевых линейных участков скелета из И7~ . 8.2 Концевые змеи . 8.3 Выпускание концевого линейного участка 8.4 Врсзание змеи 8.5 Направления концевых линейных участков скелетов из ИЯ 8.6 Коды невырождеппых 6-скслетов .
8.7 Завершение доказательства теоремы 2.2 7! 74 75 76 8! 81 104 107 $07 109 109 110 1!2 114 !15 115 1П 9 10 118 122 122 !24 127 130 133 139 143 1 2 6 4 Наросты и линейные участки минимальных сетей с выпуклыми границами 236 Концевые наросты 237 2 О концевых вершинах . 239 Расположение наростов в паркетах, принадлежащих ИЩ, на их скелетах Теорема реализации 10.1 Редукция 1-го типа 10.2 Реализация змеи .
10.3 1'сализапия ломаной змеи и лестпипы 1ОЛ Реализация лестницы в усеченном треугольнике .. 10.5 СЯ7-реализация скелетов из РРРл 10.6 Завершение доказательства теоремы реализации 3 Минимальные бинарные деревья с правильной границей Дожди . У!ивимальная реализация змеи ва произвольном множестве '2. ! Характеристическая дута 2.2 Характеристическая дуга в случае трех точек 2.3 Характеристическая,!уга в общем случае .. 2.4 Вполне характеристическая дуга Существование правильной минимальной реализации змеи .
3.1 Характеристические дуги и треугольники 3.2 Доказательство существования минимальной реализации змеи Общие свойства скелетов, имеющих правильную минимальную реализацию 4.! Распо.южение концевых линейных участков 4.2 Устройство концевых линейных участков .. 4.3 Устройство боковин . Критерий сушсствования 7!М-реализации для нелинейных скелетов Правильная минимальная реализация скелетов с тремя концевыми линейными участками .
11е существование правильной минимальной реализации у скелетов с четырьмя концевыми линойными участкамп . 7. ! Длины боковин 7.2 !1ерегородки второго уровня 7.3 Доказательство предложения 3.12 11с сущсствованцс правильной минимальной реализации у скелетов с пятью концевыми линейными участками . !!равильная минимальная реализация скелетов с шестью концевыми линейными участками . 145 116 !47 !49 151 154 ! 58 163 164 164 166 169 !72 178 !85 185 189 192 210 240 241 25! 256 255 5 Квазиправильные границы, которые нельзя затянуть ни одним минимальным бинарным деревом 275 1 )Каленый модуль 276 2 Доказательство теоремы 5.1 .
279 6 Концевые линейные участки паркетов из Ю~~, имеющих ЛЛХ- реализацию 284 ! „'!инейные паркеты с правильной границей ........... 284 2 Произвольные паркеты с правильной грапипсй ......... 298 7 Невырождснныо минимальные сети с выпуклой границей. Циклический случай 313 Фундаментальные циклы нсвырожденных минимальных сетей с выпуклой грапицеи. '1рпвиальные сети.......... 313 !.1 Число вращения тривиальной сети............ 315 7[войственный комплекс 318 2.1 Число вращения ребер контура двойствснного комплекса !'сомстрия концевых линейных участков .
3.! Длина жала: на концевом змее есть наросты 3.2 Длина жала: на концевой змее наростов нет, концевой линейный у ~исток имеет излом 3.3 Длина хвоста: концевой линсйньш участок имеет излом и на концевой змее есть наросты 3.4 Взаимное расположешле концевых линейных участков . тривиальяои сети 2.2 Ядра лвойственного комплекса Паркетная реализация тривиальных сетей с числом врашения пс более пяти 3.1 Число вращения ребер контура паркета . Описание паркетов общего вида 4.! Скелет и наросты 4.2 Паркетные оболочки и ядра 4.3 Ядра паркета 4.1 Узлы ветвления 4.5 ."!инсйиые участки 4.5 С грунт)рпые злемепты 4.7 Макрозлсмснты и концсвеяе линейные участки Скелеты из Хз 5.! Структурные злементы 5.2 Направления концевых линейных участков скелетов из 73 5.3 Коды скелетов из 7о 5Л Полинаросты .
32! 330 33! 331 а3! 332 335 '38 339 6 Располохсснис наростов в паркетах на Щ на их скелетах 6.1 [3ольп1ие псевдобоковнны 6.2 Псевлобоковины . 6.3 Расположение наростов на скелетах паркетов ил 'Рл . 343 Общий список работ Список работ по тимо диссертации 350 355 Настоящая диссертапия посвящена изучению локально минимальных плоских связных графов, затягивающих всршины выпуклых мнол оугольников. Такие графы возникают при решении знаменитой проблемы, названной в честь Якоба Штейнера 1зясоЬ В1елпег, 1796 — 1863), профессора Берлинскогоувпверси гста: ср~ дч ессх сьялсб 1селзньис ос)ноче1эныг лонлллнуучое), эотягиьаилщил донное конечное жноовестоо М тяочек плоскости, нслбти сыпь наименьшей д.шны.
Решснпя проблемы Штейне ра называются обсо,иотно .нинисиольнызш дгрееьлни. Абсо,потно минимальные сети можно рассматривать как обобщения кратчайших геодезических. Пусть И' произвольное связное риманово многообразие, и (4, В) пара точек из И'. Рассмотрим множество 11~4, В) всех измеримых кривых, соединяющих точки Л и В. Тол да кривая л Е 111А, В), имслощая наименьшую длину среди всех кривых пз Й1Л, В) 1если, конечно, опа существует).
называется кротчоЯлей гривой, соединяющей А с В. Хорошо известно, что такие кратчайшие кривыс описываются системой обыкновенных дифференциальных уравнений второго порядка. Решения этой системы называются геодезическими, однако эти решения, в обшсм случае, нс обязаны быть кратчайшими кривыми, соединяющими свои начальнуло и конечную точки. '!ем не менее, если на геодезической Т выбрать две достаточно близкие точки А и В, то отрезок ЯА, В) этой геодезической, ограниченный точками А и В, будет кратчайшей кривой.
Иными словами, у каждой точки Р, лежащей на геодезической -;, имеется такал замкнутая окрестность П, что Т Р1 П является кратчайшей кривой, соединяющей точки из (с)'~ р1 1.") 0 (1 р1дВ), где д~ =.[А, В) гранина лсривоойл Т, а ЭГ граница окрестности 1'. Таким образом, геодезические локально являются кратчайшими кривыми. Отьлетим, что последнее свойство может бьггь принято за определение геодезических: каждая локсильно кратчайшая кривая есть геодезическая. Рассмотри л теперь в леото множества 1Л, В) произвольное коне шое подмножество М рихланова мллогообрази,я И'.
Наша задача обобщить на этот случай понятия кратчайшей кривой и геодезической. Естественно, первый шаг состоит в обобщении понятия кривой. Это обобщение называется сетью. В случае И" = улез, сеть это произвольный !1остановка задачи связный плоский граф, ребра которого непрерывные кривые. Если И' щ>оизвольное риманово многообразие, или, более общо, топологическос пространство, то гете Г в И' можно определить как непрерывное вложение связного одномерного конечного СИ'-комплекса С' в пространство И~, и ограничение этого вложения на клетки размерности 0 и 1 из Г называть соотвгтствгнно ребра.яи и вершина ми сети Г.
'!'аким образом, сеть можно рассматривать как разветвленную крявук>. Отметим, что, как и в случае криззых, удобно ото>кдестззлять и вершины, и ребра сети Г, являющиеся ограничениями отображения Г на соответствуюппзе клетки иэ Х', с их образами в И'. Ниже мы воспользуемся таким отождествлением. Следуя>щий шщ обобпзззгь выражение "кривая, соединяющая зо зки А и В", на с.лучай многоточечного множества ЛХ. Для этого мы будем говорить, что сеть Г затягивает ЛХ, или ЛХ яв:тется ераницсй сети Г, если ЛХ подмножество множества вершин сстп Г. Границу сети Г будем обозначать чз ргз дГ. Далее, мы хотим злзмерять длину сети, по;>тому мы потребуем, чтобы ребра сети Г были измеримыми кривыми. Такие сети будем называть иэяерияыии. ЛХлззззой сгти Г наэовги сумму длин всех ее ргбср.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
