Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 18
Текст из файла (страница 18)
!Вершина 2з фундаментального цикла С 1 называется внешней, если единственное ребро из Г, инцидентнос Р и не принадлсжашсс ";, лежит вне области, ограниченной циклом у. !3 противном случае, вершина Р называется анутрсннсй. Разность количеств внешних и внутренних вершин фундаментального цикла; называется индекго.и цикла б и обозггачается через шд(у). Ясно, что зквивалентные нсвырождснные ости Штсйнсра имеют одинаковые структуры фунда лснтальных циклов.
Предложение 1.9 Индекс каждого фундамснпьального цикла произьояьной лини.наивной нсвырозидснной сеоги Штсйнера равен б. Иными слова.ии, равгнство шгсти индекса каэкдого фундалснтальноео цикла нсвырожденной сети Шгпейнсра являстся нсобяоди.иы.я условие.и зьинилаяьной реализации последней.. Доказательство. г[ействительпо, каждый фундаментальный цикл зто многоугольник, углы которого равны или 2я(26, или 4к,ГЗ.
Ясно, что осли угол в верппше равен 2кг'3, то зто внешняя вершина. В противном случае, вершина внутренняя. Пусть п количество вершин фундаментального цикла, по количество внешних всргпит и пг количество внутренних вершин. Имеем по+пг = и и 2к/Лпгз+4кД1пг = л(п — 2), откуда и получаем по — из = 6. Доказательство предложения 1.9 закончено. Гипотеза 1.1 Условие предложения ИУ является таплое и достаточныл. А именно. ссяи индекс каждого фундаментального цикла нсоырозкденной сети 2Итейнсра равен 6, то тпа сеть облагдатя,мииилальнон реализацией. Минимальная реализация: общий слу чай бэ9 Замечание. Отметим, что в случае, когда люоыг два фундаментальных цикла невырожденпои сети 11!тейпера пе пересекаются, сформулированная только что гипотеза может быть легко доказана.
В общем случае доказательство этой гипотезы нс известно. 10 Минимальная реализация сетей Штейнера: общий случай Рассмотрим теперь общий случай. 11усть Г произвольная есть Штсйнгра. Как и вьшсе, определи л фунда лентальныг пиклы. Однако теперь верпплпы каждого фундаьлептзльпого никла разбиваются не па два, а па три класса, а именно, внутргппис, внспшис и вырожденные. Определение персэслх двух классов такое же, как и выше, а в третий класс входят вершиньс степени '2, Далее, снова определим илсдекс !лги;:) уэулсда.иенсиальлсоео цикла у как разность количеств внешних и внутренних веригин. Кроме того, определим спсеатсь вьсросэн дения с1едеп(у) Уэуссдалселстаэсьного циклгл г как количество вьсрождеплсгзх верпшн в у.
Предложение 1.10 Пусть Г произвольная минимальная ссгссь, и э любой сс с/эундалснсссаяьньсй цикл. Тогда )1пс1(у) — 6, '< с1ебелл(у). Доказательство. 1[лил -с .это ьлно~ оугольпик, у которого углы при внешних вершинах равны 2к/?>, при внутренних равны 4к/3, а при вырожденных вершинах нахо,лятся в пределах между 2к/3 и 4лг/3. !1усть по, пс и гсо соответственно количества внешних, внутренних и выроэклснных вершин фундаъссптальпого цикла у. Обозначим через Ен сумму углов при выролсденных вершинах. '!ос да величина е, равная Уи/пп, лежит между 2т/3 и 4т/3.
Имеем 2 г/3 по + 4к/с! пг + о гсп = к(по + пг + гсо — 2). Отсюда !пс!1;) — 6 = по — пг — 6 = (Зо/г — З)псэ = (Зп/и — 3) с1гКсп13). Так как величина Зо/к — 3 меняется в пределах от — 1 до 1, получаем утвер- ждение предложения 1.16. Гипотеза 1.2 Условие предложения 1. !О является также и достато сньслс. Л именно, если индекс каждого с/эундазсгнссссс.сьного цикла ссроизиольной сети Штейгсера отличается огп 6 ие более ие.к иа степень выролсдс.— сася этого с/эугсдалсснтассьно о цикла, то зта сеть обладает лпсиинаяьиой реаяиэацией. Глава 2 Полная классификация минимальных бинарных дбрВВБОВ с Выпуклои границей !5 настоящей главе задача !5 из главы ! будет полностью решена для вложенных невырожденных деревьев !Птейнера, т.е.
так называемых плоскиг бинирпыв деревьев илп плескал 2-деревьев. Случай бинарных деревьев интересен, во-первых, поскольку для него удастся ьпзлучить полный ответ, а во-вторых, на этом существенно более простом объекте мы разраоотаем технику, которая в дальнейшем будет использована для описания псвырожлепных сетей !!!тсйнера общего вида, ооладающнх выпуклой минимальной реалвзапией. Отметя л, что, по предложению 1..'5 из главы 1, если минимальная сеть Г обладает выпуклой грапипей, то вершины из Г степени 3 граничными пе лвллютсл, т.е.
гранина сети Г совпадает с ее эффективной грапипеи.,')то приводит пас к следующему соглашению: в да.тьнсйшем, нс оговаривал каж)ыи раз спеппальпгч мы будем предполагатьь гго граница произвольного графа !сети) Штейнера является эффективной. Кроме того, в дальпешпем мы будем интересоваться лппп вложенными минимальными сетями, поэтому всюду ниже мы будем понимать по~1 сотью илзсппо вяоженнуи> сеть. 70 '1исло вращения 1 Число вращения минимального бинарного дерева с выпуклой границей Оказывается, условие выпуклости конечного мно.ксства ЛХ С к накладывает сильные ограничения на затягиваьощьлс ЛХ 1вложсннььс) минимальпыс бинарныс деревья.
Нсформально говоря, зто условие означает, что такис деревья нс могут быть "сильно закручспнымн". 1!ля описания степени закрученности ььолезно воспользоваться числом вращения, определение которого было приведено во Введении. Напомним зто определение. Пусть !' плоское оинарпое дереид (а, 6) некоторая (упорялочепььая) пара сто ребер, и О единственный путь в Г, соединяющий зти ребра. Орисптирусм путь О от а к 6, и пусть Р произвольная вершина степени 3 дерева Г, лежащая внутри ь, т.е. пе совпадающая пи с одной из его концевых вершин. Выберем круговую окрестность, Н вершины Р, такую что НОГ является дсрсвом, нс содсржащим всршин из Г, отличных от Р. Тогда пересечение дН О Г состоит из трех точек, которые мы обозначим через А„ ь = 1, '2, 3.
Пусть аь первое, и аз последнее ребро из у, инпидентпое Р, и пусть А, Е а,, ь' = 1, 2. Рассмотрим дугу б окружности ВН, лежащую между Аь и А и нс содержащую Аз. Определение. Ес.ш движение по дуге д от Аз к Ль происходит по часовой стрелке, то будем говорить, что мы поворачпвсс.и направо в ьь~очкс Р, и припишем Р число — 1. В противном случае, скажем, что мы поворачиваем налево в то гке Р и припишем 1з число +1. Число. приписанное вершине Р, называется гпвисшинеоя всрьиины Р орпсншиуованноео пу~пьь ~с с1исшя вращения Ььь (сь, Б) уььоулдочснной парьь (а, 6) ребер плоского бинарного дерева Г называется сумма твистингов во всех внутренних вершинах пути "Ь. ! !оложим, по опрсдслсшпо, ьи (а, в) = О.
Определение. '1ислож вращснил ььв(Г) плоского бинарного дерева Г называется максимум чисел вращения ььс(а, 6) по всем упорядочснныъь парам ребер дерева Г: ьи (Г) = шах Ььг(сл, 6). Оьв! Замечание. Иногда, чтобы подчеркнуть, в каком дереве Г вычисляется число вращения, мы будем писать вместо ьж(а, 6) подправленное выражение Ьгкг !а, 6). Отметим, что если Г минимальное бинарное дерево, то число вращения имеет естественный геометрический смысл. Чтобы сформулировать соответсгььукьшсе утверждевьле. папомшлм слсдукпиие понятия. Пусть !а, 6) упорядоченная пара ненулевых векторов нз . ь~. Определим сриснтиуьсванныи' уголь сь(а, 6) поры ~а, Ь) следующим образом. Если а и 6 сонаправлсны, то положихь о(а„Ь) = О. Если а и Ь не колпнсарны, то '!исло вращения 72 определим а(а, Ь) равным по модулю наименьшему углу между а и 6, а по знаку знаку репера [а, 6).
!';ели же а и Ь противоположно нзпра|злеиы, то ориентированный угол о[а, 6) не определен. Пусть 1. С Гиз произвольная ломаная, Ло,..., г!ь се последовательные вершины, и аы..., ая сс послсдоватсльныс 'звенья, ьде ар [Лр ы Лр]. Вершины Лс,..., л!ь можно упорядочить двумя естественными способами: от Ас к Ая, и от Аи к Ас. Высюр одного из этих порядков иаэывается ориентаиией ло,,наной 1, а сама ломаная с фиксированным порядком вершин ориентированной ломаной.
При этом, ссьш вершины Лр упорядо тены от Аи к Аи, то мы говорим, что ломаная 1, ориентирована от Ла к Ль или от аь к аю В противном случае, ломшьая 1. ориентирована от Аь к Ав или от аь к аы Для ориентированной ломаной Г каждое се звено ар — — [Ар ы Ар) мо кно рассматривать как вектор .1р ьл!р с началом в Л ы Танис вектора будем называть вскторажи-звеньяжи. 5сглои по~врата между послсдовлтсльньгии векторами-звенья ли ат и арл.1 ориентированной ломаной 1 называется угол о(ар, арьь). Сумма углов поворота между всеми последовательными ребрами а и арьь ориентированной ломаной 1. называется полныя уело,и поворота вдоль ло,наной 1.
и обозначается через о(1.). Пусть теперь [а, 6) упорядоченная пара звеньев произвольной [неориентировшпьой) ломаной 1.. Рассмотрим ломануро 1,', составленную из всех звеньев ломаной Г, расположенных между а и 6. Ориснтирусм 1' от а к 6. Углож поворота о[а, 6) упорядоченной пары [а, 6) звеньев ло.наной й или уелои повороти от, звена а ь звену Ь вощаной 1, называется полный угол поворота ломаной ь'. Пусть теперь Г минимальное оинарное дерево, и [а, 6) произвольная упорядоченная пара его ребер. '!'огда единственный путь у в Г, соединяющий а с 6, является ломаной. Ориентируем логиануьо 7 от а к 6.
Иьлсет место следукяций очевидныи результат. Првдложонио 2.1 '1исло вращение ьъч[а, Ь) упорядоченной пиры [а, 6) ребер ятшжального бинарного дсрсьи Г равно полно.иу углу повороньа о[7) вдоль ориснтированьизй,т.наной у, дсленножу на к1'3: 3 !и [а, 6) = — о[2). далее, приведем несколько простых утверждений, описывающих свойства чисел вртпения плоских бинарных деревьев. Предпожонис 2.2 11усть !' произвольное плоское бинарное дерево. Тогда для любых ребер а, 6 и с из Г выполняютья ель дующие соотношения: ° Во[а, 6) = — !ил[6, а) [кососижл~стричность); '1исло вращения ° ссви а, 6 и с принадлежат однону пути, то 1,н!а, с) = !н!а, 6) + ьн!6, с) 1,аддигиивиость вдоль путей). Утверждение 2.1 Пусть Г и.юскив бинарное дерево, и!н~Г) = !н(а,6).
Тогда а и 6 граиитпяс ребра. Доказательство. Предположим противное, т.е. одно из ребер а и 6, скажем а, нг граничнос. Рассмотрим путь Т, соединяющий а с 6, и пусть А концевая вершина пути у, инпидентная ребру а. '1огда, из вершины А выходит, помимо ребра а, сще два ребра, скажем с и с', при этом числа вращения !к(с, а) и ьи (с', а) ралли шы. Пусть, для определенности, 1н(с, а) = 1. Тогда !н!с, 6) ) уи !а, 6), гто противоречит макси лальности числа ен(а, 6). Доказательство закончено. Слсдуьогяес утверждение описывает ограничение па гнело вращения минимального бинарного дерева Г, накладываемое выпуклостью границы дерева Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
