Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 24
Текст из файла (страница 24)
Утворждепио 2.6 Контур линейного скелета из ИЧ~; янлясп~ся вяозкснной .ломаной. Такия образом, ьтороя пасись пьсорсяьс оЛ иясст .кесто для,нтсйных скслстоо. Доказательство. Очевидно, нсе паркеты, состоящие не более чем нз пяти ячеек, принадлежат Исса и имеют вложенные контуры. Среди паркетов из цвести ячеек только один содержит пикл (он состоит из всех ячеек, имеющих одну общую вершину), остальные принадлежат ИЩ и имеют вложенные конту:ры. Предположим теперь, что линейньш скелет Д нз Ий~ нмсст нс монсе семи ячеек, и пусть / некоторая его направляющая. Достаточно показатьн что ячейки сз1 и Ь из А, между которымп находится пс менее пяти ячеек, пе пересекаются.
Действительно. если а длина стороны, ячейки, то расстояние между проекция ли середин осей ячеек Л~ и с1сз на направляющую ! не меньше ба/4, поэтому ячейки сл1 и слз не имеют общих точек. Доказательство закончено. Операции редукции и антирсдукции 96 !'еперь мы в состоянии завершить доказательство теоремы 2Л. Завершоние доказательства тоо!п.мы 2.1.
Предполохшм противное, т.г. контур некоторого паркета 0 из Ипз нс является вложенной ломаной. '!огда существуют ячейки Л1 и Лз из П, имекяцне общую "незаконную' вершину. Пусть Л наименьший связный подпаркст в Г!, содержащий Л1 и Ьз. Ясно, что паркет ! линсйныи скелет из ИЯ'. По утверждению 2.6, контур паркета 1 является вложенной ломаной, позтому "шзакопныс' склейки его ячеек невозможны. Полученное противоречие и завершает доказательство теоремы 2.1. 6 Операции редукции и аитиредукции В настоящем пункте мы определим операции редукции и антиредукции, которые в дальнейшем будут неооходимы при формулировке и доказательстве основных классификационных теорем для паркетов из И~Р~.
Неформально, операция редукции представляет собой факторизацию плоского бинарного дерева (паркета~ по поддереву (подпаркету) специального вида, а аятиредукция обратную операцию по отношению к редукции. Классификационная теорема для скелетов (сьь теорему 2.2 ниже) дает три канонических типа скелетов из Итз, из которых остальные получаются с помощью редукции. 6.1 Разрезание и склейка В главе 1 мы определили основные операции па графах и сказали, что зти операции очевидным образом переносятся на ости.
Уточним определение двух вазкпых для нас операций, а именно, разрезания и склейки сети в интересующем нас случае вложенных сетей. Пусть Г плоское бинарное дерево, и а его произвольное ребро. Выбросим из плоского дерева Г маленькую открыту|о окрестность внутренней точки его ребра а. Полученный в результате плоский граф, представляющий гобой ооъсдипенис двух бинарных деревьев Г1 и Гз, будем обозначать через Г1а и ~ оворить, что 1' ! а = Г1 Н Гз получен из Г разрезание„и по ребру а. 1'абра графа Г ! а, получившиеся из ребра а исходного дерева Г, будем называть рсбражп разреза. Пусть теперь заданы два плоских непересекающихся бинарных дерева Г1 и Гз, и пусть а граничное рсоро из Гь а 6 гршш шос ребро из Гз.
Ооозначим через А и В вершины степени один, инцидсптныс ребра л и и 6 соответственно. Соединим Л и !3 произвольной вложенной кривой у, не имеющей с Г1 Г! Гз других общих точек. В результате мы получим плоское бинарное дерево, вершины которого суть все вершины бинарных деревьев Г1 и Гз, за исключением Л и В. Построенное плоское бинарное Операции редукции и антирсдукции 97 дерево обозначим через )Гы а)Я!'з, 6) и будем называть склейкой Гь и Гз по реораи а и 6. Ребро дерева (Гс,сь)ф(рз,6), яыляюпьееся объединением !эсбср а, 6 и кривой 7, назовем ребро,и склейки. Легко видстчь что класс эквивалентности дерева (Гы а)ур(Гз, 6) зависит липп от выбора ребер а и 6. От летим, что операции разрезания и склейки взаимно обратны в следующем смысле. Л именно, бинарное дерево, являющееся результатом склейки по реорам разреза двух бинарных деревьев, полученных рскзрезанисм бинарного дерева Г.
эквивалентен Г. Обратно, граф, полученный разрезанием по ребру склейки бинарного дерева, склеенного из непересекающихся бинарных деревьев !'ь и Гз, эквивалентен Г1 'сЗ Г . 6.2 Редукция плоского бинарного дерева Пусть Г' плоское бинарное дерево, и Г1а = Гь!зГз результат разрезания дерева !'по нскоторо лу его ребру а. Определение. Каждую из компонент связности ь рафа Г1а будем называть плоским бинарным деревом, 1-рсдуцироеанныж сы !', а операцию перехода от!' к Г, редукцией 1-ео типа.
Пусть, как и выше, Г плоское бинарнос* лерсво, и аь и аз пара его разли пнях ребер. Рсщрежем Г по ребрам а~ и аз, и пусть Гс та компонента связности получснного плоскоь о графа, которая содсржнт два ребра разреза, а Г, компонента, содсржаьцая липп ребро разреза, полученное из аб которос мы также обозначим через а;. Определение. Плоское бинарное дерево (Гы аь)ф(Гз, аз) назовем 11рсдуцироеанныл из Г по ребра„н аь и аз, а операцию перехода от!' к (Гы аь) ЯГз, аз) редукцией П-ео типа. Ребра а1 и аз будем называть ребразеа разреза.
,'1егко видеть, что редукпия 1-го типа ве увеличивает число вращения. Для редукции второго типа это уже нс так, как видно из примера, приведенного на рис. 2.!3. Однако, имеет место следующее утверждение. Утверигдение 2.7 Пусть Г' плоское бинарное дсрсас, пслучь'нное редукцией 11-го типа из бинарного дерева !" по рсбрал а и 6.
'!'огда, сели !ич.)а, 6) = О, то число ори щения дереза Гз нс превосходит числа ерищсния дерева Г: сиГ'(ьи Г. Доказательство. Пусть Г' = )Гыа)ф(Гз,6), где Г; соответствующие подлерсвья дерева 1' из определения рсдукпии П-го типа. Пусть с я д произвольные ребра из Г'. Ес;ли с и д лежат в одном из Гб то Риг (с, с1) = Операции редукции и антирсдукции е х !чг= 3 Рис. 2.13: Редукция П-го типа может увеличить число вращения сиг(с, и).
В противном случае, путь в Г, соединяющий с и Н, проходит через ребра а и 6. Позто лу, в силу аддитивности числа нращсппя на путях, имеем !иг(с, д) = !иг(с, е) + !иг(с, 6) + !иг(6, л) = !иг(с, а) + !иг(6, п) = !иг (с,а) + !иг (6, Н) = ги1 (с, с!), что и завершает доказательство утверждения. 6.3 Редукция паркетов из р!г1-б Операция редукции, определенная нами для бинарных деревьев, может быть естествснныи образом перенесена на деревянные паркеты.
Пусть Р произвольный паркет из ИЯ, и 1' его двойственный граф. Пусть бинарное дерево Г' получено из Г в результате редукции !и о или П-го ыша. Пред- поло ким, что число вращения Г' нс превосходит пяти. В силу теоремы о паркетной реализации, бинарное дерево Г' зквивалептпо двойственному графу некоторого паркета Р' из И7~. Опредсжонио. Паркет Р' назовем рес)уцироепнньья из паркета Р, а операцию перехода от Р к Р' рос!укцисй. соответствующего типа. Замечание. Понятие редукции паркетов становится более естественным, если определять ее для так называемых пог руженных деревянных паркетов.
Напомнихц что деревянный паркет строится по бинарному дереву с помощью соответствукнпей последнему триангуляции лиагоналямп некоторого выпуклого многоуч ольника. В теореме 2.1 было построено непрерывное кусочно-аффинное отображение, переводящее диагональную триангуляцию в некоторый подпаркст плоскости. Для деревьев с числом врщпсния, не превосходящим пяти, зто отображение оказалось вложением.
Ясно, что оно может быть точно так жс определено и в общсм случае, однако тогда оно, вообще говоря, будет липп погружением. Такие погружения называются поерцисснныжа паркета„аи. Определяя для таких паркетов понятие Операции редукции и антирсдукции 99 редукции, можно, как и в случае бинарных деревьев, пг заботится о числе вращения. На геометрическом языке редукцию паркета моекно представлять ссое так.
Редукпия 1-го типа состоит в разрезании паркета по произвольному внутреннему ребру и выбрасывании одной из связных компонент. 1эслукпия П-го типа закюочается в следующем. !'ассмотрим нпутреннис реора а и 6 паркета Р, пересекающиеся с ребрами разреза а' и 6' двойственного графа Г па!зкета Р. Пусть 7 путь в Г, сослиняющий а' с 6' и ориентированный от а' к Ь'. Ориентация пути 7 порождает ориентацию ребер а' и 6', которые тем самым можно рассматривать как вектора. Ориептируем а и Ь так, чтоб|т пары векторов (а, а') и (Ь, 6') имели одинаковую ориентацию. Нулем рассматривать так ориептировапнгле ребра а и 6 как вектора, приложенныс к соответствующим точкам плоскости (касателыпяс вектора на плоскости).
Разрежем паркет Р по а и 6, и выкинем ту часть паркета, которая одновременно пересекается с а и 6. Пусть з сохраняющее ориенташпо движение плогкости, совмещающее вектор а с вектором 6. Если Р' и Р" остаипиеся невыброп1енными части паркета Р, то г(Р') ОРа и сеть, с точностью ло двилссния плоскости, редуцированный паркет. Этот паркет является в.юженным, так как число вращения его двойственного графа, по определению операции редукции паркетов из И7;, не превосходит 5. В дальнейшем внутренние ребра паркета, пересекающиеся с ребрами разреза двойственного г рафа этого паркета, также будем называть ребражп разреза. Один из важных примеров редукции П-го типа возникает в случае равенства нулю числа вращения между ребрами разреза.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
