Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 34
Текст из файла (страница 34)
Птэсдпоттожихл тспертн что паркет Р имеет менее шести концевых линейных у тастков. Пусть контуры паркета Р и его скелета В ориентированы по часовой стрелке, и Вт боковины скелета Я, занумерованные последовательно числами по лтодулю их количества. Тогда у его скелета В существует боковина В,, число вращения меж,лу начальным а, и конечным 6, звеньями которой меньше 2. Пусть В; часть контура паркета Р, начинающаяся ребром ат и закан тиваюшаяся ребром Ь,. Возможшт два случая: тттахтт;(а„, л) = $в (а„, Ь,), или нет, где максимум берется по вссвоз ложным рсбрахт л ломаной В„. В первом случае выберем следующее за а; ребро из В; и обозначим сто через иь Лемма 2.17 т1лл ребра иыло.наной В, выполнены слтет1туюиттте соотнотаештят — 6 < тв1ю, и) < 1, гете и ттроизоольнос ребро контура наркота Р.
Доказатлляьствтт. По условию, для лпобого ребра и вз В; число вращения ттл1то, и) меньше '2, так как ттл1а„Ьт) < 1, а а, и ю сопаправлены. '1ак как число вращения ме кду лктбой парои последовательных ребер контура паркета Р не превосхо;1ит 2, а при переходе через каждое концевое ребро число втэащентля меняется нл — 3, то, по ана.лотки с доказательством предложения 2.т2, убеждаемся, что ы (ттд и) < 1 для .попого реора и из контура паркета Р. Получим теперь опенку снизу на Ьтл1то,и). Если и лежит на Вб то ттт"(и, и) > — 4, так как тв В, < 2, и, следовательно, ти В, < 4 1докажттте).
Пусть теперь и не лежит в В,. '1ак как ттл(то, тт)+ттл(и, ю) = — 6, достаточно показать, что ти(и, ю) < О. Если и смоленое с ат концевое ребро контура паркета 12, то зто очевидно. В противнолл случае, вновь воспользуемся тем, что число вращения между лктбой нарой последовательных репер контура паркета Р не превосходит 2, а при переходе через ка.кдос концевое ребро число вращения меняется па — 3, и,по аналогии с доказательством предлолления 2.9, убедимся, что Ьтл(и, и) < О. Лемма доказана. Из леммы 2.17 вытекает, гго в первом случае с ребра ю можно выпустить концевой линейный участок.
Позтому, в таких предположениях предлояленис доказано. Пусть теперь иллеет мссто второй случай: шахтв(а,, л) ф ттн(а,, 6 ). Рассмотрим все ребра х лолланой В,, такие что би(а,, я) > ттт1а„у) для любого ребра у из Вт. Выберем из найденных робер л последнее в обозначим его через з. Б:жом слу тае, через ит обозначим следующее за л ребро из В,. '!еорема реализации Лемма 2.18 Длл ребра ш ломаной В, выполнено одно из двух состпноитсниттт или — 6<!и(ш,и) <1, или — 7< от(ш,и) <О, где и произсольнос ребро нонптттрс нсрхстпс Р. Доказаттотьство. Мы покажем, что одно из требуемых неравенств имеет место для произвольного и из Вт. Для всех остальных ребер контура паркета 1д доказательство получается точно так хте, как в лемме 2.17.
Отзтстизт, прежде всего, что, так как последнее из ребер и, на которых достигается максимум ття(а;, р), то ттт (з, и) < О. Поскольку и ш соседние ребра, возможны ровно два случая: ттт(з, ш) = — 1 или ти (=, ш) = — 2. Пусть сначала ттс(з, ш) = — !. Покажем, тто — 7 < ти(ит, и) < О. Пусть тл произвольное ребро из 11, лежащее между а; и ш. '1огда тн(и,ш) < 1, так как в противном случае 1тт(и, з) > 3, что невозможно. С другой стороны, 1тг(и, ш) ) — 4. Поэтому, так как та (и, ш) +!и (ш, и) = — 6, имеем: — 7 < ти(777, и) < — 2. Пусть теперь тл лежит между и.
и Ь,. '1огда т,ю(ш, тл) < О, так кзк тз противном случае ттк(з, и) > О, поэтому х нс послсднсс ребро иэ ребер х. С друт ой стороны, ттт"(и, и) > — 4. Таким образом. для случая ти (з, 77~) = — 1 лемма доказана. Предположим теперь, что 1тя(х, и ) = — 2.
Пока кем, что — 6 < ття(и, и) < 1. !Осли и лежит между а, и ит, то 1и(77, ит) < О, тзк как в противном случае ттт(77, ) ) 3, что невозможно. С другой стороны, ттт(и,и) ) — 1, поэтому — 6 < 1ю(тю, и) < — 2. Пусть теперь и лсжпт между и и 67. Тогда ти(ш, и) < !, так как в противном случас тте(х, и) > О, поэтому х нс последнее ребро из ребер х. С другой стороны, ттт (и.
Н) > — 4. Доказательство ле лмы закончено. Из леатмы 2.18 вытекает, что и во втором случае с ребра ш моткпо выпустить конпевой линейный участок. Доказатеттьство предложения закончено. Теперь теорема 2И ттьттекает из предложений 2.20, 2.21 и 2.15. Доказательство теоремы 2л! закончено. Глава 3 Минимальные бинарные деревья с правильной Границеи В настоящей главе мы применим технику, разработанную в главе 2, и получим полную классификацюо минимальных бинарных деревьев, затяпьвающих вершины правильных многоугольников, в случае, когда соответствуюпше этим деревьям паркеты являются скелетами. Б следующих главах мы прпвсдсм некоторыс резулыаты, описывающие произвольныс паркеты из )гЩ имеюпше правпльпуго минимальную реализацию. В частности, мы покажем, что если паркет П из В7з имеет минимальную реализацию на некотором правилы1ом п-угольнике, то при и > 12 паркет 0 не имеет концевых наростов, поэтому скелет 5' паркета Л определен однозначно; более того, все концевые линейные участки такого скелета,5 являются змеями.
Приведем основной результат данной главы. Теорема 3.1 Пуспьь Г минимальное бинарное дерево, зьппягиваюшсс вершины прови.юного и-угольника. Прсдиолозкизу чиьо соогпвстспььуюший Рт паркет, 5' ятавстся скеле|пои. То да, ° гс:ш скелет 5' линейный, то,5' зися, рис. 3.1, слева, причс.и, для любого п суизеспшует правильная минимальная ргали ~опия виси с и граничными ребрами; ° сели 5 плюет три конасаых яинсйньчл учаспька, и, значиив одну ячейку гете зсиия, пьс.
Ь' является З-скелета и, то все лиисиные участки из 5 зжси, соспьояи1ис из ог)инакоаого числа ячеек, причет 5 инваригттсн отиостпсльио поворота на 120' вокруг центра гдинствснной Рис. З.П Представители бесконечных серий скслстон без узлов ветвления и З-скелетов, имеющих правильную минимальную реализацию Рис. 3.2: б-скелеты, имеющие правильную минимальную реализацию: слу- чаи и = 24 и и = 30 своей ячейки всепвления, рис. 3.1, справа. Более того, выкая реализация существует тогда и только тогда, когда п = бк+ 3, где х. произвольное* целое положип1ельное число; ° скелет Б не .ножет быть 4-скелетом: ° скелет Б не может быть б-скелетом; ° сели Б является б-скеьлстом, то он представляет, собой один из четырех скелетов, привсденныт, на рис. д.й и З.дч Лри этом соответствующие значения и ратая 24, 30, 36 и 42.
Более ьлого, все прови ~ьные минимальные реализации каждого такого скс.тта отличаются друе от друга на изометрню. Итак, среди скелетов из ИЩ, имеющих цравильнукь минимальную реализацию, существует две бесконечные по п серии, и одна конечная. Дождгг Рис. 3.3: б-скелеты, имеющие правильную минимальную реализацию: слу- чаи и, = 36 и и = 42 1 Дожди Напомни л, что ггахсдезг па плоскости мы назвали произвольную совокупность попарно ра.зличных параллельных прямых. Пусть ЛХ произвольное конечное множество точек плоскости. Будсъг говорить, что до кдь ХХ проходит через ягголггесгпео М, если каждая точка из ЛХ лежит на ггекоторой прямой дождя ХХ, и, обратно, каждая пряггая дождя Л проходит через некоторую точку из М.
Определение. Дождь ХХ, проходящий через конечное множество ЛХ точек плоскости, называется реерлярны я, сели на каждой пряггогй дождя лежит ровно одна точка из М. Н ггротивном случае, дождь ХХ называется особы.и. Пусть дождь Л проходит через множество М, и М' С ЛХ нскоторос подмножество в Л1. Дождь ХХ и, состоящий из тех и только тех прямых ,дождя Я, которые солержаг точки из Л1', нгюовем огрпничышея дождя й иа ЛХ'. Отметим, что каждое ограничение регулярного догкдя также регулярно. Обратно, если нз М' задан некоторый дождь 11', то ложль Л, полученный иэ Л,' присоединением прямых, проходящих через точки из ЛХ гг ЛХ', булем называть расгпиреииеж далгдя ХХ с М' на М.
Нустг теггерь И орггеггтиггоьчшный дождь. Напомним, тсо направлением ориентированного дождя называется единичный вектор, сонаправленньгй с формирующиънг этот дождь ориептпровапш,гми прямьгми. Мы будем отождествлять вектора направлений с соответствующими точками единя шой окружности, которую назовем окрухкгггосгггьга иапраеленгил ,Чсгко понять, что для каждого направления существует единственный дождь этого направления, проходящий через данное згггохгество Л1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
