Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 20
Текст из файла (страница 20)
По предложению 2.3, число вращения диагональной триангуляции, обладаюШсй выпуклой мипимальнон реализапией, пе превосходит пяти. Из вьппесказаппого вытекаег, что для реьпепяя зада*ш В достаточно описать все диагональные триань уляции с не прсвосходяШим пяти чнслогя врагцспия. Оказывается, для этого описания полезно перейти к диагональным триангуляциям специального вида, опредсляемым тем, что все их ячейки правильные треугольники. !3о 13веденми мы называли такие триангуляции паркетами. Однако тсперь мы определим паркеты более обшим образомд а диагональные триангуляции, составленные из правильных треугольников, будем называть дерсеяняыли паркета ми, подчеркивая тем самым, что двойственная есть таких триангуляций является деревом.
21егко построить пример плоского бинарного дерева, для которого соотвстствуюШая диагональная триангуляция нс эквивалентна никакому деревянному паркету, см. рис. 2.3. Тем нс мснсс, в интересуюшем нас случае диагональных триангуляций с числом вршцения, нс превосходяпп1м пяти, вссг,ла можно построить соответствующий деревянный паркет. Этот факт будет установлен в следуюшем разделе в теореме 2.1 о паркетной реализации.
Паркетная реализация Рис. 2.2: Двойственный граф паркета На одной из этих прямых фиксируем точку и повернем зтн прямые на 60 и — 60'. Полученные три семейства параллельных прямых, называемых в дальнейшем иипраеллю>ними, н задают нскомос разбиение, которос мы будем называть (трсугольнызь) парк>.и>ом плоское>ии, а правильные треугольники, сто составляющие, ячейка.яи.
Стороны ячеек будок> называть ребрами паркета, а их вершины сер>нина.яи паркета. Множество ячеек паркета плоскости, расположенных между соседними параллельными направляющими, назовем полосой исркстс плсскоспш. Опродолоиио. Произвольпук> совокупность, ячеек назовем пархато,я. Пусть теперь Р произвольный паркет. Пару ячеек паркета Р назовем смеяснь>.яи, если они пересекаются по ребру.
Границу паркета Р как подмножества плоскости назовем контуром и обозначим через дР. Ребра ячеек из Р, лежащие на контуре, щазовем граю> шы„яи ребрами или рсбрими контура, а осшальные ребра си утренними. В дальнейшем мы часто будем объединять последовательно расположенные параллельные ребра контура в отрезки, нж>ьптеъьые зссиьлми контура. Определим теперь дьойса>осиный граф Г>> пиркси>а Р как плоский граф, полученный следующим образом. Соединим пентр каждой я ьейки зтого паркета Р отрезками с серединами ее сторон.
В качестве вершин двойственного графа Гп возьмем центры ячеек из Р и середины граничных ребер паркета Р. 1!рьь этом отрезки, соединяющие центры смежных,я ьеек с серединой их общей стороны, мы обьединим в одно ребро. Отметим, что двойственный граф Гц является обьединепнем невырожденных минимальных сетей, каждая нз которых затягивает множество середин рсбср одной из связных компонент контура паркета Р (схь.
рис. 2.2). Для удобства, терминологию из теории графов, применяемую к двойственному гр>афу паркета, мы будем переносить на сам паркет. Л именно, произвольнуэ> совокупность ячеек паркета назовем его подпаркепшм. Назовеы паркет селзиыля, сели его двойственный граф связен, дср>юлиным если его двойственный граф дерево. Союзными компонсии>ильи парке ьа Паркетная реализация назовем его подпарксты, двойственные графы которых являются связными компонентами двойственного графа самого паркета. '1акэке под число.,м вратенол деревянного паркета будем понимать число вращсния сто двойственного графа.
С другой стороны, мы будем также переносить термины, примснясмыс к паркетахц на их двойствепныс графы, и, более обтээо, на эквивалентные этим графам плоские, в частности, минимальные, сети. Теорема 2.1 (Ол паркетной реализации) Всякое плоское бинарное. дерево с числом в1эаи1енил, не превосяодяили.м гэлтп, эьвоволентно двойственной стпн некотороео паркета. Доказательство. Напомним, что каждое плоское бинарное дерево экээивалснтно двойственному графу некоторой диан ональной триангуляции выпуклого многоугольника. Поэтому для доказательства теоремы достаточно показать, что суепсствуст непрерывное кусочно-аффиннос вложение, переводящее' эту триангуляцию на диагональную т1эиангуляпию некоторого многоугольника, составленную из ячеек паркета плоскости.
Пусть Г рассматриваемое бинарное дерево, а Т соответствующая диагональная триангуляция выпуклого многоугольника Р. Вудом считать, что плоскость, содержащая многоугольник Р, и плоскость, разбитая на правильные треугольники, образующие паркет Т, орнентироваяы каноническим образом.
Возьмем произвольный треугольник 1 триангуляции Т и поставим ему в соответствие произвольную ячейку т паркета Т. Пустыд~ сохраняющее ориентапию аффипное отображение, переводящее 1 в г. Если триангуляция Т состоит иэ одного треугольняка,то искомое кусочно-аффипное отображение построено (оно совпадает с дв). В противном случае, рассмотрим треугольник 1' Е Т, смежный с 1 по некоторой стороне о. Поставим ему в соответствие ячейку г' е Т, смежную с ячейкой г по ребру у,(а).
Пусть зэк сохраняющее ориептапикэ аффиннос отображение, псреводящсе 1' в т' и совпадающее с эв~ на общей стороне а треугольников 1и 1'. Если триангуляция Т содержит только два треугольника, то искомое кусо шо-аффияное вложение к~оп склеищэется из отоб1эажений вес и вэп. В противном случае, рассматриваем новый треугольник 1," Е Т, смежный с одним нз уже выбранных треугольников (т.с. смежный с 1 О 1') по стороне 6. Опять строим сохраняющее ориентацию аффинное отооражсние вэп, переводящее 1в в ячейку тв к Т, смежную с г О г' по реб1эу:рсое ®, требуя при этом, чтооы отображения вс и у~о~ совпадали на 6. Если нам удастся продолжить описанный только что процесс до тех пор, пока пе будут задействованы все треугольники триангуляции Т, и при:этом полученный паркет окажется деревянным, то в результате мы построим кусочно-аффинное отображение из мное оугольника Р в паркет Паркетная реализация у "а Рис.
2.3: Это плоское бинарное дерево не имеет паркетной реализации плоскости Т, такое что сто образ и будет искомым деревянным паркетом. Единственное, что на л молсст помешать это воз ложность склейки на одном из ша~ ов тех ребер выбираемых ячеек, прообразы которых не склеиваются в тризн~ уляции Т.
На рис. 2.3 приведен пример бинарного дерева и соответствующей ему триангуляции, не имеющих 'паркетной реализации' . Отметим, что у рассматриваемого дерева число вращения равно б и достигается на ребрах а и 6: 1и (а, 6) = б. Однако, если число вршцспия дерева 1' нс превосходит пяти, то такие склейюл невозможны. цействятельно, в противном случае рассмотрим двойственный граф паркета, возникшего на том шаге, когда появилась 'незаконная' склейка, скажем, по ребру а. Этот двойственньш граф, очевидно, содержит цикл. Рассмотрим ребро двойственного графа, соединякппее центры ячеек, смежных по стороне а. Это ребро делится стороной а, на два отрезка, соответствующих ребрам лорена Г, скажем, реорам 6 и с. Хорошо известно, что полный обход по любой замкнутой вложенной кривой на плоскости приводит к повороту на угол +2я.
Поэтому, в силу того, что двойственный граф паркета является минимальной сетью, а также в силу геометрического смысла числа вращения минимального бинарного дерева (сэь прсдложснис 2.1), получаем, что ги(6, с) = х11. Мы пришли к противоречию, что и доказывает невозможность незаконных склеек. Таким образом, корректно определено кусочно-аффинное отображение д." Р— г Р~, персводятцсс треугольники триангуляции бу в ячейки паркета Г, причем на внутренности многоугольника Р отображение г взаимно однозначно с образом. Нам осталось показать, что это отображение также взаимно однозначно и на грашлце мпог оу! ольника Р, т.е.
~г является непрерывным вложением. 11дея доказательства последнего утверждения состоит в рассмотрении 'незаконно склеившихся по вершине" ячеек паркета ф Г), выбора в них соответствующих ребер двойственного графа и доказательстве того, что между этими ребрами число вращения будет по модулю больше пяти. Чтобы избежать несущественных технических нагромождений, мы ненадолго отложим строгое доказательство этого факта (см. ниже Паркеты и их свойства раздел "21пнейные участки" ), а пока займемся более детальным анализом комбинаторно! о и геометрического устройств деревянных паркетов.
"! еорема '2.1 позволяет нам в леото плоских бинарных деревьев рассматривать деревянные паркеты с числом вращения, не превосходящим пяти. Класс таких паркетов мы будем обозначать через уггР». 4 Паркеты и их свойства В настоящем пункте мы начнем изучать различные 'элементарные кирин ли", иэ которых составлены паркеты. Особое вшлмание мы уде.гнм случаю деревянных паркетов. Па протяжении этого пункта все паркеты считаются связными. 4.1 Разбиения паркета на скелет и наросты Оказывается, структуру паркета можно .лостато шо легко понять, если предварительно избавиться от некоторых "слу"!а!лил!к"" его элементов, называемых нами наростами.
Пусть Р произвольный (связный) паркет. Г! о ячейку назовем крайней, если по крайней мере два ее ребра легкал на контуре !»Р, и ьннтрснпеи если все ее ребра лежат внутри паркета. Если ровно одно ребро ячейки лежит на дР, то такая ячейка называется по,лукраянея. Среди крайних ячеек важный класс образуют так называеилые наросты. Определение. Крайнюю ячейку назовем !!простои, если она примыкает к внутренней ячейке. Отметим, что наросты бывают двух типов.
Пусть лк нарост, крепящийся к внутренней ячейке гл'. Если к Ь' !больше пе крепится никаких наростов, то !з называется енутрсппин нароспшж. В противном случае, нарост Л копцсвогд сл!. рис. 2ий Легко видеть, что паркет, состоящий из 1, 2 или 3 ячеек, и! содержит наростов. Первьп! паркет. содержащий наросты, состоит из 4 ячеек и изображен на рис. 2 4 справа. Отметим, что этот паркет, является иск.почительным в следующем смысле: к его внутренней ячейке примыкают сразу три нароста.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
