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