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