Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 27
Текст из файла (страница 27)
Доказательство закончено. 8.2 Концевые змеи Пусть,'> произвольный деревянный скелет, и 1, один из его концевых линейных участков. Рассмотрим ось 8р1 для Г, как линейного участка, и пусть 2 концевое звено оси йр 1, т.с. звено,пересекающееся с контуром паркета б'. Обозначим через Е множество всех ячеек паркета 1,,оси которых лежат в у. Ясно, что паркет и является змеей. Определение. Построенную только что змек1 У назовем кояиеаои зжсси' для й. Пусть теперь Я скелет из ИЯ. Продолжим отрезок ~ за контур скелета Я до некоторого отрезка конечной длины, и добавим к Я все ячейки паркета плоскости, пересекающихся с продолжением т.
Ориентирусм продолжение з наружу скелета,з'. Ясно, что прн добавлении последовательных ячеек перестраивается ровно две боковины паркета. причем зта перестроика заключается в удлинсш1и концевых звеньев этих боковин, поэтому числа вращсния этих боковин остаются неизменными. Следовательно, перестроенный паркет по-прежнему остается скелетом из Ибш Теорема класспфикации скелетов из Ичв 110 Определение. Описанную только что операцию будем называть удлине- ние,я концевого линейного участка В скелета В. Итак, имеет место следующее утверждение.
Утверждение 2.13 В результате удлинения любава конпввово линейного участла произвольного скелета из Ихв всевда по.ъучается скелет из ИУ~. 8.3 Выпускание концевого линейного участка В настоящем разделе мы определим операцию выпускания концевого линейного участка, которая является частным слу ~аем антиредукпии 1-го типа, и позволит нам достроить произвольный скелет из Ин до скелета с шестью концевыми линейными участками, также принадлежащего ИХРш Пусть В скелет нз ИЩ, имеющий менее шести концевых линейных участков.
Удлинив, сели необходимо, концевые линсйныс участки скелета В, будем предполагатьч что коппсвъле змеи сктъета В состоят нс менее чем из четырех ячеек. Пусть В; боковины скелета Я, ь' = 1,..., 6, причем 6 < 3. В силу сделанного предположения, концсвьяе звенья каждой боковины В, состоят не менее ьеьь из двух грани"шых ребер скелета В. Ориентируеъь контур Е скелета В по часовой стрелке. Будем предполагать, что боковины В, скелета В занумерованы последовательно. Обозначим через а; н 6; сосътвстствснно начальное и конечное звено боковины Вь Тогда условие равенства — 2я полного угла поворота при обходе контура 1ъ' по часовой стрелке записывается ввиде: — 6 = ~ ~1ъъ (а;, 6;) — 36.
Так как числа вращения боковин В, пе превосходят 2, а й < 6, все 6ли(а,. 6,) нс могут одновременно равняться 2. Пусть, лля ощ>сделанности, М(аы 6ь) < 2. Лемма 2.10 Рбъьввт тесто одно из слвдуюиььх двух утверлсдсний. ° гХисло вращения жсжду аь и произвольныш звено.я баковиньь Вь нс превосходшп 1.
° Висло вращенич жежду првазво ъьпьлн звентя боковинка Въ и звенохл 6ь нс прсьвсходит 1. Доказательство. Предположим противное, т.е. супьествуют звенья с и д боковины Вы такцс чтьз ьъъ(аы с) = аъ(д, 6ь) = 2. Тогда бн(ам 6ь) = ыч(ам с) + Ьъ (с, с1) + 1ъъ (д 6ь) = '1 + Съъ (с, д) < 1. Поэтому, 1ъъ(с, Н) < — 3. Последнее противоречит тому, что БиВь < 2.
Лемма доказана. '!еорема классификации скелетов из ИЩ Предположим для определенности, что выполняется первое из двух утверждений леммы 2. Н) (все приводимые шлже рассуждения тривиальным образом переносятся на случай, когда имеет место второе утвсржлсние леммьь 2.13).
Иными словами, для любого звена с боковины Лъ число вращения Съч(аъ, с) не превосходит 1. Лемма 2.11 Пусть с произвольное звено контура К ск лета б', тогда число вращения мч(а„с) иезиду звеньяли оъ и с леэкиъп в с.ъсдуно тих прсделвхс — 5 < !ъъ(аы с) < !. Доказательство.
В силу выбора звена въ, имеем !и (аы с) < 1 лля любого звена с боковины В,. Пусть теперь с не лежит в Въ, и пусть т > 1 число боковин, целиком лежащих между аъ и с. Тогда т ъъъ (аъ, с) = ~ ~!ъъ" (а,, Ь,) — 3(ьп — 1) + Фв (6,, с). Но !в(Ь,,с) < — 1, так как или с концевое ребро, смежное с 6т, и тогда Ьъъ(6,„, с) < — 1, или с лежит на следующей за В,„Оковинее, и тогда !и (6п,, с) < — 3 + 2 = — ! . С другой стороны, ъп Ся (О,, Ьъ) < 1 + 2(ъп — 1), так как !сл (аъ, Ь|) < 1. Таким образохь, Рх(аъ, с! < 1+ 2(т — 1) — 3(т — 1) — 1 = 1 — т < О. Проверим теперь неравенство !ъъ(аы с) ) — бъ. Так как !н(аы с)+ъъъ(с, аъ) — б, зто неравенство вытекает из !к(с, а~ ) < — ! .
Если с: концевое реоро, смежное с аъ, то ъъъ (с, аъ) < — 1 и все доказано. Предположим теперь, что с нс является смс.кным с аъ концевым ребром. Пусть т номер перъъой боковины, целиком лежащей между с н аъ. Если таких боковин нет, т.е. с лежит на Ль, получим: !ъи(с, аъ) = !т(с, Ьь) + !ъч(6ь, въ) < 2 — 3 = — !. В противном слу те, имеем: !м(с, оъ! = Иъ(с, а ) + ) !хя(аб 6;) + ) !хя(Ьь а;.ьъ) + !ъъ(Ьь, аъ).
ъ=ъо Легко видеть, что !ъх(с, а„) < — 1, позтому !ъъ(с, аъ) < — 1+ 2(6+ 1 — т) — 3(А — т) — 3 = — 2 + т — lс < — 2, так как й < ьп. Лемма доказана. 'Георема к:шссификации скелетов зкз ИЩ Замечание. Если в лемме 2.11 под а1 понимать ие шзево, а ребро боковины Пз, то, очевидцо, получим более слаоую опенку: — 6 < 1з»(аз, с) < 1. Обогяачим через а ребро контура, црияадлсжащсе звену аз и являющееся впутрсипизз ребром боковины Вь По замечанию к лемме 2.11, »испо вращения между а и произвольным ребром контура РГ лежит в пределах от — 6 до 1. Пусть г грацичиое ребро двойственного графа Гл скелета Я, пересекающееся с о. н у произвольное грани"шое ребро из Г».
Б силу утверждения 2.11, имеем: — 3 < 1зз (л, у) < 4, т.е. М(л, Г») < (3,4). Рассмотрим змею се не пересекающуюся с '~, состоящую более чем иэ двух ячеек, и такую, что число врашеиия 1з»(Гя, ) ее двойствеии(зз о графа Гх относительно некоторого ес коицевого ребра равно (2, 1). Склеим бинарные деревья Г» и Ги цо ребрам л и . По утверждению 2.9, 1з»ИГя,г)Ф(Г», и)) < цзах(3, бз, ~(2,1)+ (3,4)~) = бз. По теореме о паркетной реализации, бинарное дерево (Гя, г)ф(Г», л) '.зквивалеитцо дззойствеииому графу цекоторого паркета гбфЯ из ИЩ. Легко видеть, что паркст У»р,'> является скелетом и имеет иа олин концевой лииейцый участок больше, чем скелет Я.
Легко понять, что ва геометрическом языке паркет Ууу.ь можно получить так: рассмотрим сохраняющее ориентацию движение»о плоскости, совмещающее концевое рсбро контура змеи Я, пересекающее =, с ребром а контура скелета .~з' так, чтобы смежная с а ячейка из з' оказалась вяс гмси У. Паркет Лура, с точностью до движеивя, совпадает с Я 0»о(гб). 1!удем говорить, что паркет гб»рЯ получен из Я оьтусканигм концсоой змеи У с ребра а контура К этого скелета. Таки л образом, доказацо следующее цреллоисение. Предложение 2.9 Для любого скелета из Юю чис.т концсоых линсйныг учаспгкоо которого .игньшс 6, сузцсстоуст содгулсаьций его скелсзп из И1)ш имеюицзй но один концсоой линейный участок больше.
В частности, осякий скелет из И'~~ .,иолсст бьппь расширен до 6-сколь то из Иу~~ с понатто операции оьтускония концсоого линейного участка. 8.4 Врезание змеи Если в предыдущем разделе мы научились увеличивать число концевых лииейцых участков скелета, не выходя цри этом иэ класса ИЯ, то пель настоящего ргглсла иаучиться расщеплять сложиые узлы ветвления, состоящие более чем из одной ячейки, иа более простые. Для этого мы определим оцеразщзю врезация змеи. Пусть,'> цроизвольшлй скелет из яУРгь, содержащий узел ветвления С', состоящий боле~ че л из одной ячейки.
Рассмотрим внутреннее ребро о паркета П, и пусть:г ребро двойствеявоз о графа Г,» скелета К цсрсссказошсс а. Разрежем граф Г,» цо ребру л, и пусть Г1 и!'з соответствующие '!гарема классификации скеле.лов из Ил!н 113 'х А — '~ д у Рис. 2.!8: Обоснование возможности расщепления узла ветвления связные компоненты, з:, ребро разреза из графа Г„, и К вЂ” компоненты скелета 5, соответствующие Гл. Лемма 2.12 Иясюлн .ллссто следрюлдис нсрааснслаеа: (2,2) < лил(л„рл) < (3,3), л = 1, 2. Доказательство. Пусть Ь, ячейка из л„примыкалолцая к ребру а. В силУ выбоРа РебРа а, Ячейки лч вхоДЯт в Узел П, т.е.
ЯвлаютсЯ внУтРенними. Позтому к каждой из них крепится еще по две ячейки скелета з', объединение которых с ячепкамп сх, мы обозначим через Г. '!'еперь ясно (см. рис. 2 18), что !и(ль Г ) > (2 2) и !лк(Гб я ) > (2 2). Так как число вращения скелета Я не превосходит 5, то !лг(Гл, лл) + лн(яз, Гз) < 5, позтому ли (т;, Гл) < (3, 3).
Лемма доказана. Пусть теперь У змея, не пересекающаяся с сл' и состошпая из четного числа ячеек. Тогла число вралпления между конпсвымп ребрами зл и лз се двойственного графа Гх равно нулю. !еперь мы находимся в условиях следствия 2.6. С помощью антиредукции П-го типа, вклеим в ребро я дерева Гл дерево Ги по ребрам с~ и з. Полученное дерево обозначим через Г. Тол да, в силу следствия 2.6, число вращения бинарного дерева Г оценивается так: ЛьчГ < шах(3, о, ((3,3)+(2,2), ((3,3)+ (2,2)~) = б гле (2,2) в правой части неравенства оценка сверху на числа ллрипеллия концевых ребер змеи У по отношению к У. 'Хаким образом, число вращения П-антирсдуцированного дерева Г меньше или равно 5, позтому, по тсоре лс о паркетной реализации, ему соответствует паркет л из ИЯ, который, очевидно, является скелетом. !'еометричсски, паркет о' можно получить так. Разреже л паркет,5' по ребру а на подпаркеты !!л и Ьз.
Пусть 6л концевое ребро контура змеи У, пересекающееся с ребром -,. Пусть ло, сохраняющее ориснтшлию дви канис Теореьла классификации скелетов из И)св плоскости, совмщпаьощсе ребро а контура паркета 5) м конпсвьгл ребром 1), контура змеи 5, причем так, чтобы обрез смелсной с а,ячейки паркета ,5) не лежал в У. Тогда паркет 5 совпадает, с точностью до движсния, с паркетом ьо)!),5)) 0 гц 0 !сз(5з) и имеет, очевидно, на один узел ветвления больше,чем паркет Я. Будем говорптьн что скелет Я получен из скелета 5' врегзанием змеи збг в узел ветвления Г по ребру а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
