Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 10
Текст из файла (страница 10)
Пусть теперь 5' состоит по крайней мере из трех ячеек. Проведем во всех нскрайних ячейках скелета Я их средние линии, соединяющие внутренние стороны этих,я леек. В крайних ячейках проведем средние линии, нараллельныс уже построенным в смежных ячейках. На объединении всех проведенных средних линий введем структуру графа, объявив ребрами максимальные связныг прямолинейныг говокупногти этих линий из нс внутренних ячеек, а тлкжг все линии из внутренних ячеек. Полученный нлоскии граф называется осою скелета оод Далее, пересечение оси скелета оо с каждым его линейным учагтком! называстгя осто,нингйно о участка 1..
Следующее предложение описывает все линейные участки скелетов из Игт Предложоиио 18 Ось каждого гщнейного участка Л скелета из Иг~л однозначно проектируется на прямую, тоорил»с»аную нгкоторои' стороне глротволаной,ячейки. Прямая иэ предложения 18 наэьшллетгн нгтравллютей линейносо участки Ь. Отметим, что, с точностью до параллельности, существует ровно три нрямые, каждан из которых параллельна какой-нибудь стороне цроизвольной ячейки.
В дальнейшем, говоря о направляющих, будем отождествлять параллельные прямые, поэтому, например, имеет смысл л озарить, что линейный участок обладает одной направляющей (т.е. все направляющие линейного участка параллельны). Принимая во вниманис сделанныс замечания и соглашение, отметим, что существует не более трех направляющих. Если линейньш участок обладает тремя направляющими. то он называется з.неей, если двумя то лестницей, и, наконец, если одной то ломаной з,иесй, см.
рис. 18. Таким образом, описаны основные структурные злеженплы паркетов из Иггсзлн наросты, узлы ветвления и линейные участки. Опишем, как эти элементы крепятся друг к другу. Оказывается. каждый скелет иэ Иогл можно получить иэ скелетов специального канониче- В поисках болоо удачной терминологии, мы иэллсниллл назв нио опискин» о голы о что плоского графа: в основных работах автора этот граф наэывастсл полонно около,ч. Основные результаты диссертации Рис.
16: Линейныс участки скелетов из УУРз ского вила, выбрасывая из последних некоторое количество ячеек. Операция "выбрасывания" называется редукцией. 1|азличаются редукции 1-ого и 11-ого типа. Пусть 0 некоторый паркет. Редукция 1-ого типа состоит в разрезании паркета В вдоль внутреннего ребра некоторой ячейки и отбрасывания одной из двух компонент. Ясно, что редукция 1-ого типа переводит паркет В в некоторый паркет, число вращения которого нс больше числа вращения паркета 1).
Чтобы описать редукцию П-ого типа, напомни|И что каждое ребро двойственной сети. соединяющее вершины степени три. пересекает ро|зно одяо внутреннее ребро некоторой ячейки паркета. Ото задает соответствие меж|!у такими ребрами двойственной сети и внутре|шими ребрами паркета. Итак, редукция ! 1-ого типа состоит в следующем: выберем два внутренних ребра паркета 13, таких что число вращения между соответствующими им ре|брами лвойственпои сети равно кулки ра |- режем паркет 1Э вдоль этих ребер; выбросим ту из трех обрезованных компонент, которая пересекается с обоими оставшимися компонентами; с помон|ью параллельного переноса склеим остэвшисся две компоненты по ребрам разреза.
й!ожно показать, что если 1) Е И/1ш то описанная операция корректно определена (т.е. после сдвига полу |еняые два паркета пересекаются только по ребрам разреза), и результирующий паркет имеет число вращения, яс болыпсе чем у!), в частности, оп по-прежнему принадлежит И7~;. Выше мы построили код скелета К являющийся плоским графом и описывающий топологию скелета 11. Однако код не отражает геометрических особенностей скелета 1|', таких как, скажем, взаимного расположения направляющих линейных участков, входящих в ой !1оэтому для описа|шя геене |рви скелетов построим схлеяу скелея|а 11, закодировав каждый узел ветвления кружочком, а каждый лияейцый участок 1, набором черт|лек по следующему правилу: если А змея, то поставим ему в соответствие одну черточку, параллельную оси участка А; если А лестница, то поставим сму в соответствие пару пересекающихся черточек, каждая из которых параллельна одной из двух направляющих участка 1.: если же 1, лома- Основные результаты диссертации ная змея, то поставим в соответствие 1.
три параллельные между собой черточки и параллельные единственной направляющей участка 1. Теперь мы в состоянии сформулировать основную тсорс;му, классифицирующую скелеты из И')зт Теорема 1' 1йаждый скелет из ИЩ может бьппь получен крат ны.ч при.нгнениеж редукции к скелету одного пз трех канонических типов, схе.,чы копьоуых приьгдены на 1тс. Ц. Отметим, что из теоремы 1' вытекает интсрсснос следствие. Следствие 4 Лады скелетов из ИХ~с зто всевозиожныс гмоскис бинарныс дгрсвьц каждое из которых илсст, нг более 6 вершин. степени 1. В чистности, оке.тт из Индо содержит не более 6 концевьи линеиных участков, не более 3 прожежуточньш,тнейных участков, и не бояее 4 внупьр~ нтсс ячеек (а, значит, нг.
более 4 узлов вепьвлсния). Ориснтируем ось каждого концевого участка 1 скелета .5' с И7~ в сторону крайней ячойки, припадлсжшцсй 1 (для Ь', не годгржашего внутренних ячеек, существует лвс таких ориснтацни). Тогда направления ребер так ориентированной оси назовем напраолснияльо концевого учасьпка Ь. Ясно, что всего существует не более шести различных направлений, образующих правильный шестиугольник, вписанный в единичную окружность направлений. Такой шестиугольник назовем шестиугольником направлений.
Следствие 5 11аждый концевой линейный у ~веток скелета 5' из ЪЛо имеет не более трех различньлх направлении, причем зти направления послгдооатсзьныс.. 11ножества направлений, соотвгтствуюшис любыи доул различным концеььыи .шнсйныл участком из Я. не пересекаюпься. Если ориентировать границу гамлета б', для опрсдг,.аенногти, против ~агавой стрелк|~, ппо задаст циклический порядок на иножгстве конце" вых линейньи: участков, а также ориентировать шестиугольник направлттй против часовой стрелки, что задатп цикла тгкий порядок на сеиейггпве множеств направлений концевых линейных у ~астков, то оба возникших порядка будут согласованы: последоьатсльныс концевые учасчпки будут и,ягть последовательные льнозксггпва направлений.
Оказывается, полученная нами классификация точна, а именно, имеет место следующая теорема. Тоорома 2 (О реализации) Двойственньгй граф произвольного паркетпа из Иг7)1 зквнвалетпсн некоторону п лоска ну вини нальнольу бинарнону дсргьу с вьтуклой гратсцей. Основные результаты диссертации 2) Получено полное описание всех локально минимальных бинарных деревьев, затягивающих вершины правильных многоугольников, в случае, когда соответствукпцие им диагональные триангуляции являются скелетами. Мы говорим, что паркет имеет правильную,иянильальную реализацию, если его двойгтвеннан сеть плапарпо эквивалентна локально минимально лу бинарному дереву, затягивающему вершины правилыншо мно~ оугольника. В соответствие с вьппесказапным, все такие паркеты принадлежат Иээзэ. Теорема 3 Если скелет илеет правильную .,ниниляальцую реализацию, то все его концгвьы линсйныс участки виси (количеспьво концевых лингйныт у гасткоя не пргвогходит 6).
С точнотпьиэ до изолиетриц следующие скелеты и только они иьиеют правильную лини.нальную реализацию на провильнои и-уголышкс: ° среди скелетов бсэ узлов встгления лшиь .эиеи для любого п, рис. 17, слева; ° среди скелетов с одной .я эгйкой ветвления., т..с.
среди 3-гкс~стов, лишь скелеты, у лоторых концевые линейные участки являются зясяли, состояиьияи из одинскоього числа ячеек, причс.н угол яс кду направэюниялш этих линсйньш учоспьков раасн 120' (концевые линсйныг у нэсп1ки ориентированы а гторону гвоих концевых я юегк). В часэпносэтц токио скелеты инвариантны относительно прошения вокруг центра единственной ячейки *ептления на угол в 120', с.н. рис. 17, г права. Более того, тикая реализация сущсствуетп лишь для и = бй+ 3. гдг я' произгольнос целое полоэкитояьное число: ° 4-скелеты и Ь-скелеты не ияеюпэ прови,п ной,чини.иальной реализации; ° среди 6-скелетов и.,моется лишь чгтыун скелета, по одно„иу дяя каждого и, равного 2-'1, 30, 36 и 12, рис.
18 и 1У. Г>ояее того, все провильныс: „иинииальные регьлигэации каждого такого гксяето отличаются дру. от друга на изояст1эияэ. Таким образом, среди скелетов, допускающих правильную минимальную реализацию, имеется две бесконечные серии и одна конечная серия.
3) Построена бесконечная серия квазиправильных многоугольников (многоугольников, множества вершин которых лежат на окружности и не сильно отличаются от множеств вершин соответствующих правильных многоугольников), которые ньаиьзя затянуть ни одним локально минимальным бинарным деревом.
Пусть Р = (р;) правильный п-угольник, вписанный в единичную окружность Я' с центром в пуле, и г неотрицательное п1сло, исньпн е м Основные результаты диссертации 39 Рис. 17: 1!редставители бесконечных серий скелетов без узлов ветвлении и З-скелетов, имеющих правильную минимальную реализацию си--- ,з Рис. 18: б-скелеты, имеющие правильную минимальную реализацию: слу- чаи и = 24 и н = 30 Рис. 19: б-скелеты, имеющие вравильвую минимальную реализацию: слу- чаи и = 36 и и = 42 Основные результаты диссертации чем к!п, где о = к!лп. Пусть в = (вы..., в„) произвольная последовательность из +!.
Обозначим через т, точку, полученллую из р, поло!затон на угол глг, и пусть Я~Х = )тл). Мноьоугольник ЛХ называется еквазиправилмлым,лтогоугольнаком пшпа ж Теорема 4 Пуслаь я тлпиодичсская пос,.лсдоаательаость длины и = 10й с периодом ( — 1, 1, 1, 1, — 1, — 1, 1, — 1, 1, — !), и г ллроиэвольнос лло.ложилпе.льнос число, такое ч>по к!л(2п) < г < х)лл. Тосда при ь. > 8 мнолсестао М вершин -касашпрааильного п-уго.льника типа я илльзля затянуть ци одним мттлтяьным бинарны.н дереьом,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
