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