Геометрия локально минимальных и экстремальных сетей в пространствах с нормами (1102759), страница 25
Текст из файла (страница 25)
2) Вместо (т, ЛХ) < (р,р) будем сокращенно писать (т., ЛХ) < р. 3) Сложение двух пар чисел обозначает покомпонснтнос сложение (т, ЛХ) + (и, .У) = (т+ и, ЛХ+ У). 4) Максимальное из двух чисел т и ЛХ назовем модулем пары (т, ЛХ) и обозн ьчим чер( з )(т ЛХ) ) 7~11д(Г) < т~(Г~По(Г,),Га11о(Гь),(Гарц(Г,,7~)-~-РаП~(~г,Гь)(). 122 Теорема 5.2. Пусть бинарное дерево Г получено антиредукцией Х-го типа, по ребра,и склейки, -и и "(ь из двух непересснаюиихся бинарныт, деревьев Г1 и Г2. Тогда ижет .ивето след~юи)ая оценка на ориентированную погя!е!шносгпь дерева Г." Доказательство. Пусть "(' и )" произвольные реора дерева Г. Если оба эти ребра одновременно лежат в одном пз Г;, то Ы1~в (-,, ")") < Га110(Г;) и Ы1() (-,1" 1 "(') < Га11()(Г.;).
В противном случае. пусть -,,' лежит., например, в Г), а "(" в Гп. Положим Га11в(Г(. уп() = (т11ЛХ))! а Га11о(",.2,Гп) (т~о ЛХ~). Тогда Ы1()(у.", ) = Ха11~ (",; о "()) + Ы11-'(уо,",: ) < < щах1а11~)~1(а,,",о)) + п1ахЫ1цп("(~,6) = ЛХ) + Мп! а 6 а также Ы1Г( п(1 11) — Ы1Гп(, у л ) + Ы1Г ( ,/) < < щах1а11о'(а,",'2) + шах 1а11о'(";), ()) = Гпп + т) о й (1 где последне(п 1эав(пнство имеепт место в соответствии с утв(.;рждением 5.2.
Поэтому ! Ха11о(7 и "(')! < !(Гп1пЛ'Х1) + (ГпгпЛХ2)!! что и требовалось доказать. И Исследуем теперь! как ведет себя ориентированная погрешность прп антиредукциях ХХ-го типа. Пусть бинарное дерево Г получено антиредукциеп ХХ-го типа из бинарного дерева Г с помощью вклеивания бина1эного дерева Г() в ребро ",: пз Г по ребрам ",' и ",," из Г(). Обозначим через Г1 и Г2 компоненты, на которые распадается дерево Г прн разрезании его по ребру;, а через я соответствующее ребро разреза дерева Г,. Теорема 5.3. Если 1а11~'( у'.""") = ()1 то имеет место следу)ощвя, оценка, ни ориентированную погрешность дерева Г: Га!1о(Г) х паах(ГаПп(Гп) Га11п(Г) ГаПп(Го) ( Га1!п(Гп, пп ) ! ГаПп(п'.
Го) (, (Раап(Га,О") О- Г!1О( ПО, ГП)(,(Г~11О(ГП.ОИ) -~ ГаПО(ООп Г )(). Доказательство теоремы 5.3 полностью аналогично доказательству те- оремы 5.2. ° Следствие 5.2. В Г)редполояеениях. теоремы 5.Х имеет место еледую- яцая, оценка на ориентированную поерспшность дерево, Г: Га!1п(Г) < тах(Га11о(Гпп), Па!!о(Г), (ПаПО(ГН,Оп) -1-Га110(,, Го)(, (Г~11о(Го, О ) ! Га1!о(~2, Гп)(). Доказательство. В самом деле, Га11()(Г;) < Га11()(Г) для г = 11 2! и ! Га11о(Г1!",ч) + Га11в( (21 Г2)! < Га11()(Г)! что и требовалось доказать. ° 123 5.2. Топологическая и планарная Л-минимальные (экстремальные) реализации сети Рассмотрим две произвольные вложенные сети Г;: С вЂ” + КЯ на Л-нормированной плоскости (К2, рл). Определение. Сети Г1 и Г2 называются тьланирно эквявалентнытл.
если существует деформация в классе вложенных сетей, .переводящая одну сеть в другую, причем граница переходит в границу. Замечание. Классическое определение планарной эквивалентности состоит в том., что две вложснныс сети планарно эквивалентны, если существует гомеоморфизм плоскости К на себя, сохраняющий ориентацию и переводящий одну сеть в другую. причем граница переходит в границу. На самом деле, эти определения планарнои эквивалентности эквивалентны, но для удобства мы будем использовать только первое.
Рассмотрим произвольный топологпческнй граф С. Определение. Будем говорить. что топологичсский граф С допускает, топологпческую Л-минимальную (экстремильную) реализацию, если существует вложенная локально минимальная (экстремальная) сеть Г: С вЂ” + Е на Л-нормированной плоскости. 2 Определение. Будем говорить, что вложенная сеть Г: С вЂ” + К~ допускает планарную Л-минимильную (экстремальную) реализацию, сели существует планарно эквивалентная сй вложенная локально минимальная (экстремальная) сеть Г': С вЂ” т Й2 на Л-нормированной плоскости. Рассмотрим произвольнун~ вложеннун> сеть Г: С вЂ” + Я~.
Из определения Л-мпнимальной (экстремальной) реализации сразу вытекает утверждение. 'Утверждение 5.3. Если сеть Г допускает тыанарную Л-минимальную (эксипремильную) реилнэицию. тпо и тиопологический гриф С допускиет тот!ологннескукэ Л-мнннмальнл/В ~экстпремальнукэ! ээеилнэацРиО. Определение. Дерево Т' с некоторой границей называется дереоом Штейнера, если степени вссх вершин нс больше 3, а все вершины степени 1 явл.яютс.я граничными. Определение. Две вершины называются соседними, если они инци- дентны одному и тому же ребру.
Из структуры локально минимальных сетей сразу вытекает теор~ма. Теорема 5А. 1) Топологическое дерево Т допускает топологическую Л-минхляальную реализицию тогда и только тогда.. когда Т' ,являетая деревом Штейнера,. о) Вложенное дерево Г: Т вЂ” + К~ допускает, плинирную Л-минимальную реализацию тогда и пъолько тогда, когда, Т',является, деревом Хй тейнер а. Оказывается. теорема 5.4 верна и для Л-экстремальной реализации. Теорема 5.5. Вложенное дерево Г: Т вЂ” ~ К~ допускает планирную Л- экстремальную реилизицию тогда и только тогда, когда Т' является деревом Штс"йнери. Доказательство. Необходимость следует из того факта. что каждое экстремальное дерево является и локально минимальным. Поэтому.
по теореме 5Л. дерево Т является деревом Штсйнсра. Достаточность. Нам надо построить экстремальное дерево Г': Т вЂ” > К, планарно эквивалентное вложенному дереву Г: 'Т' — ~ К, где Т' явля- 2 2 ется деревом Штеине1за..~1ы будем строить дерево 1', все ребра которого точечны. 1) Рассмотрим сначала случай, когда вложенное дерево Г является бинарным. Пусть 2Л = О (п1ос1 3). В этом случае в качестве дерева Г' можно взять 27Г дерево, у которого углы между смежными ребрами равны . Тогда 3' Га11с(Г') = О.
Следовательно., сеть Г' экстремальна. Пусть 2Л = х (шос1 3), где х = 1, .2. Построим такое дерево Г', чтобы в соседних вершинах погрешности были расположены как показано на рис. 5.1, 5.2. Построим дерево Г' по индукции, где индукцик~ будем проводить по количеству вершин дерева Г степени больше 1. Пусть дерево Г содержит п вершин степени больше 1. Для п = 1 дерево Г' строится произвольным образом. Пусть утверждение индукции верно для п. Рассмотрим дерево Г, содержащее (п, + 1) вершину =1.....:,+1 степени больше 1. Так как Г является деревом., то Г содср кнт в~ ршину усов, например., -„+~.
Рассмотрим Рис. 5.1. Расстановка погрешностей Рис. 5.2. Расстановка погрешностей поддерево Г дерева Г., в котором вершины -~...., -„, имеют степень 3, а остальные 1, т.е. дерево Г является бинарным. По предположению индукции, для дерева Г сушествует планарно эквивалентное ему дерево Г', у которого в соседних вершинах погрешности расположены так, как показано на рис. 5.1, 5.2. Дерево Г' получается из лерева Г' путем добавления внутренней вершины степени 3.
в которой углы между смсжнымн ребрами удовлетворяют нашему требованию. Докажем, что полученное дерево экстремально. Для этого мы покажем. что Га110(Г') = 2, отсюда и будет следовать экстремальность Г'. Рассмотрим произвольньп| ориентированный путь 'Р в Г' и последовательность ориентированных погрешностей для него.
Согласно нашей расстановке., в этой последовательности после двух ~1 или после ~2 будет следовать ~2. две ~1 или одна ~1. на которой последовательность закончится. Поэтому Га110(Г') = 2. 2) Для произвольного вложенного дерева Г дерево Г' строится так, как и в бинарном случае, а в вершинах степени 2 берется угол, равный и. Для так построенного дерева Г' будет выполнено неравенство Е~11о(Г') ~ (3, поэтому дерево Г' экстремально. Теорема доказана.
° 126 Следствие 5.3. Топологическое дерево Т допускает топологическую Л-экстремального реализацию тогда и только тогда,, когда, Т,яаляетсл деревом Шп)ейиерп. 5.3. Стандартная евклидова плоскость как предел Л-нормированных плоскостей при Л вЂ” + ~~~ Напомним, что нормированная плоскость (К, рл) называется Л-нор- 2 мированнои, если единичная окружность )' = 1х Е К (р~(х) = 11 является п1эавильным 2Л-угольником. '1аким ооразохп станда1этная евклидова.
норма является пределом Л-норм при Л вЂ” + с. Экстремальные сети на Л- нормированной плоскости будем называть Л-зксяпремальнылт. Напомним. что вложенная сеть на стандартной евклидовой плоскости является локально минимальнои, если и только если все вершины степени 1 являются граничными и угол между каждой парой смежных ребер не 27Г меньше . Из структуры локально минимальных и экстремальных сетей , 3 вытекает что еетп ать) рассмот1птм произвояьняк) тока чьно мин))ма яьн'ск) или экстремальную сеть на Л-нормированной плоскости и устремим Л к бесконечности, то получим экстремальную сеть на стандартной евклидовой плоскости (классы локально минимальных и экстремальных сетей на стандартной евклидовой плоскости совпадан)т).
Возникает вопрос: верен ли обратный результат, т.е. для лк)аой ли экстремальной на стандартной евклидовои плоскости сети можно построить последовательность Л- экстремальных сетей, которая сходится к данной сети при Л вЂ” ) сс. 5.3.1. Сходимость сетей Рассмотрим на плоскости произвольную вложенную сеть Г и последовательность вложенных сетей ~Г„~~ ), планарно эквивалентных Г. Определение. Будем говорить. что последовательность сетей ~Г„: С вЂ” + К )~-'~ ) сяадияпся, к сети Г: С вЂ” + К .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
