Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 25
Текст из файла (страница 25)
В этом случае число вращения редуцированного паркета завода ло нг пргногходит числа вращения походного паркета, т.с. прц работе с паркетами из Ило нс выводит из этого класса (см. утверждение 2.7). В дальнейпаем под редукцией Ны о типа паркетов из И7эь мы будем понимать именно такую редукцию. 6.4 Антиредукция плоских бинарных деревьев В настоящем разделе определяется операция, обратная к операции редукции, называемая, поэтому, антиредукцией. Пусть!'1 и Гз два непересекающихся плоских оинарных дерева.
Выберем и каждом из ннх по одному грюплчному ребру а,. Определение. Полученное в результате склейки по ребрам а, деревьев Г, плоское бинарное дерево Г = (Гы а1)~(Гз, аз) назовем 7-антиредудироеанным из Г1 и Гэ по ребра,я склейки а1 и аго а операцию перехода от деревьев Г,, к дереву Г антиредукдией 1-ео пщпи. Операции редукции и антирсдукцни 100 Г = ((Гы ВМ(1 е, 61), Ьз)Ф(Г, Оз). Определение. Полученное только что бинарное дерево Г назовем 11-ан)пп- рсдуппрованнм я из Г с помоиьью внлспва)шл бпнарноео дерева 1'с в ребро а по ребрам 61 и Ьз, а операцию перехода от деревьев Г и Гс к дереву Г внпшредупцпеи 1Дго т)ша.
Изучим поведение шола вращения при аптиредукции. Для этого нам понадобится понятие о ппюительпого числа вращения, которое мы сеичас и определим. Пусть Г произвольное плоское бинарное дерево, и а нскоторое его ребро. Определение. Чис)юм сращении 1и(а, Г) ребра в относительно дерева Г называется упорядоченная пара чисел (т, ЛХ), такая что т = — шш!и (а.
6)) Л)Х = шах Ьи (а, 6), где шах н шш берутся по всевозможным ребрам дерева Г. Определение. Числом вращснпн ьи(Г, а) дерева Г сп)ивсщпельно ребра и назовем упорядоченную пару чисел (т, М)) такую что га = — ппп 1м (6) а), ь ЛХ = шах 1н(6, а)) ь где шах и ппп берутся по всевозможным ребрам дерева Г. Имеет место следующее простое утверждение.
Ътверлсдение 2в8 Пуси)ь Ри(а) Г) = (т) ЛХ). '1'огда 1и(1', а) = (Л1) т). Доказательство. Пусть Ьи(Г, а) = (ьа', Л)Х'). По определению, т) = — ппп ьи(6, а) = — пбп ( — Ьп(а) 6)) = шах Ьи(а) 6) = ЛХ, ь ь ь ЛХ) = шах си(Ь, в) = шах ( — Ьи(а, 6)) = — ппп Ьи (а, 6) = т, ь ь ь что и требовалось. Пустьь как и выше, задано два непересекающихся плоских бинарных дерева Г и Гс, и пусть в дереве Г фиксировано произвольное ребро а, а в дереве Гс пара различных граничных ребер Ьь и Ьз. Разрежем дерево Г по ребру а, и пусть аь и аэ ребра разреза, принадлежащие компонентам Г) и Гз графа Г1а соотвстствснно.
Склеим деревья Гь и Гс по ребрам аь и Ьь К полу ьенному бинарноглу дереву (Гы аь)ф(Гс, 6~) приклсим дерево Гз по ребрам Ьз и аз. В реэулыате мы построим бинарное дерево Операции редукции и антирсдукции 101 Для формулировки основного результата настоящего раздела цам ионадобятся следующие обозначения. В приведенных ниже формулах все буквы обозначают полые числа. ° Положим (ггс, ЛХ) < ъгр, у), сели и только если гп < р и, одновременно, ЛХ <д. ° Вместо (гп, ЛХ) < (р, р) будем сокращенно писать (т, ЛХ) < р. ° Сложение двух пар чисел обозначает покомпонснтнос сложсние: (ггс, ЛХ)+ (и.
ХХ) = (т+ и, ЛХ + гьу). ° Ъ!аксиасальнос из лвух чисел гп и ЛХ назовем модулем парьг (т, ЛХ) и обозна плхс через )(ггг, ЛХ)!. 'Утворждонив 2.9 Пусть плоское бинарное гЭереао Г полу сено антиредукцисй Х-ео типа из плоских непересекающихся бинарньгх дерсеьее Гс и Гз по ребрам скггейьи аъ сь аз. 7оеда и.,мест .место следуюсцая оценка на число арап!ения гЭсреьа Гс ьъъ Г < шах(!ъъ Гс, ьъъ Гз, !и )Гс, ас) + !и )аз, Гз)!). Доказатеиьство. Пусть с и д произвольные ребра дерева !'.
Если оба зти ребра одновременно лежат в одном из Г,, то гъъг)с, д) < !и Г„. В противном случае, пусть с лежит, скажем. в Гы а с! в Гз. Положим Ьъ )Гс, ас) = )тс, ЛХс), а Ьъ )аз, Гз) = )ггсз, ЛХз). 'Тогда СЪЪгГ(С, С!) = ЫуГ,(С, ГВ) + !ИГ,(ае, д) < ппъх !иг, (с', аъ) + шах !ъъг,,(аз, д') = ЛХъ + ЛХз, а также г ъъ г (гХ, с) = !ъъ г, (д, аз) + !и г, (ам е) < шах !ъът, !с1, а ) + шах сиг, ! сгс, с ) = ггсз + ты где последнее равенство имеет место в соответствии с утвср кдснием 2.8. Позтому ! !и с.(с1, с) ! < !~ты Л11) + !тз, ЛХз) !, что и заканчивает доказательство.
Исследуем теперь, как ведет себя число вращения при антиредукции П- го типа. Пусть оинарнос дерево Г получено антирсдуссцией П-го типа пз плоского бинарного дерева Г с помошью вклеивания бинарного дерева Гс в ребро а из !" по ребрам Ьъ и бз из Ге. Обозначим через Гг и Гз компоненты, на которые распадается дерево Г при разрезании его по ребру а, а через ас соответствующее ребро разреза дерева 1",. 11оковины и их свойства 102 УтвеРждеиио 2.10 Коли сиге(6гк6з) = О, то пззеет место снес)рющав оцепив на чисзо вращения дерева Г: 1иГ < шах (1иГ з, 1иГы 1и Гз.
! 1и(Г ы п~) + 1и(6ы Гс)!, ! 1и(Гс,бз) + 1и(аз, Гз), 1и(Гы и,) + 1и(из, Гз) ) . Доказательство утверждения 2.10 полностью аналогично доказательству утверж,пения 2.Я. Следствие 2.0 В прейюлолсенинзз ртаерэзсдел ин Щ9, имеет меспзо следу- ющая оценка ни число иупщенин П-анпзиуейуииуоеанного дересо.
Г: си Г < пзах(1и Га. 1и Г. 1и(1 ы п1) + 1~"'(6ь 1 0)/, ! сии(10,62) + сии(пз, 1 2) ). Доказательство. В самом деле, рж Г, < 1и Г для 1 = 1, 2, и ~ си(Г, а1) + 1и(пз, Гз) < 1и Г, что и требовалось доказать. 6.5 Антиредукция паркетов из )чзсб Антиредукция паркетов из И 7~ может быть определена по аналогии с тем, как мы это делали по отношению к редукции. А именно, сели антиредукция двойственных графов паркетов из И2оз приводит к бинарному дереву с пе превосходящим 5 числом вра|цения, то соответствующий этому бинарному дереву вложенный паркет принадлежит ИЯ и называется антиредрИироепнным паркетом соошеспзспшующезо спина. Более того, определение антпрелукпии естественным образом переносится и на случай потру конных паркетов.
В дальнейшем, при доказательстве теоремы классификации скелетов, нами будут определены важные операции "выпускания концевого линейное о участка" и "врезавия змеи', которые являются антиредукциямн 1-го и Н-го типа соответственно. 7 Боковины и их свойства В настоящем пункте мы опишем некоторое каноническое разбиение контура деревянного паркета на концевые ребра, концевые вершины и боковины. В случае, когда паркет не содержит наростов, это разбиение не содержит концевых вершин, и булст полезно нам лля определения тос о, куда можно крепить наросты на скелет пз ИЗсщ чтобы нс выйти за пределы класса ИЯ.
Мы увидим, что числа вращения боковин паркетов из Изззо так же, как и числа вращения линейных участков таких паркетов, нс превосходят 2. Во второй части классификапионяой теоремы мы изучим возможное расположение наростов в терминах числа вращения боковни. 11оковины и их свойства 103 Рнс. 2.14: Концевые ребра паркета определены неоднозначно 7.1 Определение боковин Пусть Р произвольный деревянньп1 паркет, и Р = Яь) 1ьь,) некоторое его разбиение на скелет и наросты. Ребра контура паркета,Р, пересекающиеся с осью скелета Я, назовем кониеььыьа. Отме гим, гго концевые ребра определены неоднозначно, т.е., вообще ь оворя, они зависят от разбиения паркета па скелет и наросты (см. рис. 2.14).
Однако> для скелета неоднозначность в определении концевых ребер исчезает. Заметим также, что при фиксированном разбиении Р = 5 и 1ььь) концевые ребра паркета Р совпадают с капиевыми ребрами сто скелета 5'. Вершины наростов Ле не лехсщцие на контуре скелета Я паркета Р, также назовем кониеьььни. Определение. Замыкания связных компонент, на которые распадается контур паркета Р = ЯН~Ь,) после выбрасывания из него капиевых ребер и концевых вершин, назовем боков янами паркета Р (для данного разбиения паркета на скелет и наросты).
7.2 х1исла вращения ребер контура Пусть 0 деревяппь~й паркет, и Хб = дХ) его контур. Ориентируем контур К по часовой стрелке, т.е. в отрицательном направлении. Рассмотрим два произвольных ребра а и 6 контура К, и пусть з = Хб[а,Ь) тот из двух путей на контуре К, сов чиняющнх а и 6, для которого а начальное, а 6 конечное ребро в выбранной нами ориентации. Опредеяенио. Числа.н ьращения Ьи(а, Ь) = Рик(а, Ь) ребер контура а н 6 называется их число вращения как звеньев ломаной, г.е. ьж. (а, 6).
Пусть Г двойственный сраф паркета Р, и пусть и и я те его граничные ребра, которые пересекаются соответственно с ребрами а и Ь контура Хб = дР. Тогда числа вращения гик(а, 6) и Сьчт(л, у) связаны между собой следующим образом. 1!оковины и их свойства 104 'Утверждение 2.11 В только что сг!слогагьгт прсдпоггоэгссггият, ьиг[в, у) = !их [а, 6) + 3. Доказательство. !!усть Д и Л соответственно точки пересечения ребер в и р с контуром !Т. Пасть пути Т = К[а,6], расположенную между точками А и Л, также обозначи л через,г. Тогда путь г вместе с путем !'[ь, у], соединяющим в дереве 1' ребра л и у, образуют мнгтоугольник, у которого углы при всрппптах г! и В равны к,г'2. Полный угол поворота при обходе по часовой стрелке построеггвгп о мпгц оуго.шпика равен — 2я, поэтому тг и я — !игг[а, 6) — — — — !иг [г, у) — — = — 2к, 3 ' 2 3 '' 2 откуда, после элементарных вычислений, получается утверждение.
7.3 Связь между числами вращения боковин и числом вращения паркета у!ы начнем этот раздел с несложного утверждения, а именно. 'Утверждение 2.12 Чпсгго орагцсяия лгобой бокооипы произпольпоео ли- псбноео г!ггреьяннопо слтлсто росно гислу прощения его ог и. Доказательство. Пусть Л произвольный линейный деревянный скелет, 'эр Л его ось, и В любая нз двух его боковин.
Пусть а и 6 зпспья оси, на которых достигается ее число врашения. '1огда, как было показано при доказательстве предложения 2.Гэ, каждое из звеньев и и 6 состоит пс менее чем из двух осей ячеек. Пусть з часть оси эр1,, сосдиняюшая звснья а и 6, и пусть !У подпаркет в А, составленный из всех ячеек, оси которых принадлежат т. Положим Л' = В О И. Так как звенья а и 6 состоя г не менее чем из,авух осей ячеек, В' является боковиной линейноь о скелета А', а 3 совпадает с его осью эр Е'. Полее того, в силу той же причины, концевые звенья боковины В' параллельны звеш,ям а и 6.
Обозначим через и и я кояпевые звенья боковины Л', параллельные гоответгтвепно а, и 6. Рассмотри л многоугольник Р, ограниченный боковиной В' скелета 1,', осью -г — — с)рй' скелета Ь', а также цоловинкалш и и п концевых ребер контура скелета В', дополняюгпими Л'Отг до многоугольника [см. рис. 2.!6). Предположим для определенности, что пря полном ооходе многоугольника Р против часовой стрелки мы проходим ось скелета ь' от а к 6 [в противном случае рассуждения аналогичны). Так как полный угол поворота при обхо:!е многоугольника Р против часовой стрелки равен 2к, и при проходе через кагкдос пз ребе!э и и о угол поворота равен к [в силу параллельности а и л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
