Геометрия локально минимальных и экстремальных сетей в пространствах с нормами (1102759), страница 24
Текст из файла (страница 24)
Следовательно. 1а11о(Р) > — 3, 1а11» ( Ргн) ~) 3 и ( — 1 ) Тот (6 ) — 3 ~ )— 3, что и дае "г ( — 1 ) Тот (ь ) ~ )О. Теорема доказана. ° Используя теоремы 4.10, 4.11. 4.12, получаем следующую теорему. Теорема 4.13. Произвольния бинирная суиясствггнная сеть Г: С вЂ” + К2 на Л-нормированной плоскости экстрсмальни тогда и только тогда, когда Га11о(Г) < 3. 4.8.4. Геометрический критерий экстремальности бинарного дерева Рассмотрим произвольное бинарное дерево Г: С вЂ” ~ К .
По теореме 2.2, экстремально(:ть дерева Г равносильна экстремальности всех существенных подсетей дерева Г. Используя теорему 4.13, получаем сле- дующпи результат. Теорема 4.14. Пусть Г: С вЂ” + К~ произвольное бинирнов дерево ни Л- нормированной плоскости (К~, рл). Тогда Г экстремально, если и только если Га110(Г) < 3. Замечание. В теореме 4.14 мы не треооваяи локальной минимальности дерева Г, так как, по теореме 1. г, неравенство Еа110(Г) < С3 влечет локальную минимальность. 4.9.
Геометрический критерий экстремаль- Теорема 4.15. Произвольная существенная сеть Г: С вЂ” ~ К~ на Л- нормировиннгьй плоскости экстрсмальна тогда, и только тогда, когда, Га11в(Г) < 3. Пб Доказательство аналогично доказательству теоремы 4.12. Надо только учитывать. что если некоторая внутренняя вершина пути Р является граничной в сети Г, то слово ( = И'(Г) принадлежит лишь А» где сеть Г получена внутренним расширением пути 'Р (ориентация на Г индуцируется из пути Р).
Поэтому для слова ( достаточно проверить лишь положительность слева. Тео1эема доказана. ° Основным результатом этой главы является следующая теорема. ОсновнаЯ теоРема. ПРоизвольное пог1»Уженное деРево Г: С вЂ” э К~э не содержащее внд»тренних вери(ин степени 2, на Л-нормированной пяоскосп»и (К . рэ,):экстщэемаяьно тоглЬ и нпо,лько тогдоь когда все вертинь) 2 сп)еп)ени 1 явля»отея граничными и Г<а11в(Г) < 3. Доказательство.
Достпаточность. Пусть для дерева Г выполняется неравенство Га110(Г) < 3. Тогда то же самое неравенство выполнено и для любой сушественной подсети дерева Г. Из теоремы 4.15 вытекает. что каждая существенная подсеть дерева Г экстремальна. Следовательно, по теореме 2.2, дерево Г экстремально. Необходимость.
Пусть дерево Г экстремально. Тогда, по теореме 2.2, экстремальна каждая существенная подсеть Г, дерева Г. Из теоремы 4.15 вытекает, что Га11о(Гл) < 3 для каждой сети Г, Пусть 'Р = 1-»1.....,",',,) произвольный канонически ориентирован- ный путь в дереве Г, все внутренние ребра которого точечны. Если ребро -»»э нс является точечным, то ближайшее к »:, точечное ребро, на котором достигается максимум лля Ы1о(Р).
обозначим так же через ",:, р = 1, и. Обозначим через::; внутренние вершины из Р, инпидентные у; и у;+1, а через 'Р»,..., 'Рл все максимальные подпути в 'Р, лежашис в сушественных сетях (»» может быть равно нулю). По предположению Ха11вЯ.) < 3, где Пусть 1.-;;,Я» все внутренние вершины из 'Р, которые не входят Л в пути Р~» 1 < й < (»» и Ы1()("»», ",;,+)) = 3~ ~ — Л + 3 (г может быть равно нулю). Тогда из локальной минимальности дерева Г и определения существенной сети следует, что путь Р содержит, по крайней мере, (д+ Л г — 1) внутренних вершин:,, для которых Ы1о( ):,, "):,, +») < 3~ — ~ — Л вЂ” 3.
Имеем Л эацо(7») < < бац»я) э <.~а~10(ъ,,1ъ»») ' (чэ» — 1)(з( — ) — ~ — з) < 1=! »=» , Л < (»э э 2») (д( — ) — л) э 3 < 3. 117 Если у+ г = О, то Ы1о(Р) < О. Следовательно, Га11о(Г) < 3. Теорема доказана. ° 4.10. Некоторые следствия из основной тео- ремы Рассмотрим на Л-нормированной плоскости. где 2Л = ж (шос1 3), произвольный путь Г = 1;»»..... ", ), все внутренние реора которого точечны.
Орпентируем этот путь от ребра ",:». Заметим, что путь Г необязательно правильно повернут, Покроем путь Г максимальными последовательными правильно повернутыми ориентированными путями Г;, где г', = 1,..., г. Из определения строго допустимой деформации следует, что сеть Г экстремальна тогда и только тогда. когда ка кдая сеть Г'; экстремальна. По основной теореме. сеть Г; экстрсмальна тогда и только тогда,. когда Еа11»»(Г,;) < 3. Исследуем более подробно неравенство Еа11о(Г.,) < 3. Пусть компоненты Г; = 1", »,...,"; покрытия сети Г имеют длины с д; > 2.
Заметим, что ~ с»; = у+и — 1. Поскольку на каждой сети Г; задана Кс» Канонипоексая ОРИЕНТВЦИЯ, ТО КажДОИ СЕТИ Г,; СООТВЕТСТВУЕТ ПОСЛЕДОвсательность (Ы1»»(",,»,"~),...,Ы1о(,' »,",,', )). Обозначим через (а»....., а„,) последовательность (и»...., а„,..., а»,..., и„, ), где олоки (а»,..., а„, ) повторяются» Е И»» 101 раз.
Получаем следукнцук> теорему. Теорема 4.16. Сеть Г.; не яелястся экстремально»», тогда и только то- гда, когда носледоеательность (Ы1»»(;,', "»Я,..., .1а11»»(-»:,',, »" )) содержит нодноследовотельность вада: (3, (0,)~3) для х = О, (1„1., 1.
( — 2, 1. 1, ) 1) для х = 1, (2,( — 1,2,— 1,) 2) для к=2, гдето»=1»:1»»101. Определение. Будем говорить. что знак е(Г;. Г) равен 1, если каноническая ориентация сети Г; индуцируется из ориентации сети Г. В про- ТИВНОМ СЛупас, Знсзк Е(Г;., 1 ) 1зсзвсн — 1. Поставим в соответствие сети Г последовательность (е(Г», Г) Ха11»»( у,', "»2),...., е(Г». Г) Ха110(;,',, у,',),...
...,е(Г,,Г) Ы1о(";».,;2), ..,.е(Г,,Г) Ы1о(-»„", -,,' )). Используя основнук» теорему и теорему 4.16, получаем 118 Теорема 4.17. Путь Г не является экстреиальныа на Л-нортпрованной, плоскости тогда и только тогда, когда последовательность (е(Г~,Г) Ы10(.у~~, у~~),...,е(Г~.,Г) Ы10(у', ~, у,)..... ....е(Г„,Г) Ы10("у~, у~),...,е(Г, Г) Ы10(",:д ~,"у~ )) содержит, иодноследовательностпь вида: фЗ. (О. )' ~ 3) для х = О, (~1, ~1., ~1, (~2, ~1, ~1, ) ~ 1) для ж = 1,. (~2.
(~1,~2,Т1,) ~ 2) для ж = 2. где/ Е М0 ~01. Глава 5. Свойства Л-экстремальных сетей и их асимптотика при Л -+ ос В даннои ~~~~~ мы заимемся изучением своиств экстремальных сотен. В начз)ле мы посмотрим как Влияют нскОтОрые ОПС1)ац1л11 над се'1'ями на их экстремальность.
Поско,1ьку экстремальность сети характеризуется ее 1)1)1лентир1)ваннс)й п1)грешн1)стью, го мы Исследуем поведение погрешности при этих операциях. Далее, мы изучим вопросы, касающиеся топологической и планарной эквивалентности сетей. В последней части данной главы исследуется поведение экстремальных сотен на Л-нормированных плоскостях при Л вЂ” ) х). В данной главе Л ~ 2., 3, 4, 6 и сети не содержат внутренние вершины степени 2. 5.1. Поведение погрешности при редукциях и янтиредуыциях Пусть Г: С вЂ” + К2 произвольная вложеннз.я бинарная локально минимальная сеть на Л-нормированной плоскости, все ребра которой точечны (далее в этом параграфе мы будем рассматривать только такие сети).
Рассмотрим произвольный ориентированный путь 'Р = ( у1, у2) в сети Г, нз;п1нающийся на реб1эе )11 и заканч)лваюлц)лйся нз. ребре ";2. Для пути Р мы определили ориентированную погрешность Ы1з(Г) = Ха111)(",:1,",:~) как сумму ориентированных погрешностей в каждой внутренней вершине пути. Иногда мы будем записывать ориентированную погрешность в виде Ы10(";1,")2), имея в виду, что рассматриваются пути в Г.
Из опре!' деления ориентированной погрешности вытекает Утверждение 5.1. 1) Ориенп)ироеиннан позре)иноспн иддиптени, п1.е. 1а11о11л ")г) + 1а11оЬ,7з) = 1З11о("'1 ":з): 120 2) Ориентированная погрешносп»ь кососимметрични. т.е. Ы10(;и, -»2) = Ы10 ("»2; 1) ° Замечание. Если сеть Г нс .является бинарной., т.е. возможны граничные вершины степени оольше 1, то утверждение бэ.1 для некоторых путей неверно. Теорема 5.1. Пусть Г'. С' -+ К2 бинарное дерево.
полученное рсдук»»«пей ХХ-го типи по ребром -и и ",»2 иэ бинарного дерева, Г: С вЂ” э»1с2. Тогда, если Ы1»»~"д.-,«2) = О, то ориентированная погреи«ность дерево, Г' не прес»осходит ориенп«ировинную погрешность дереви Г: Га11»»~Г') < Еа11«»(Г). Доказательство. Пусть Г' = (Г».-п)ф(Г2.,"»2), где Г, соответствующие поддеревья дерева Г из определения редукции ХХ-го типа. Пусть; и у«а пропзвольныс ребра из Г'. Если; и у" лежат в одном Г.;, то Еа110~ (-«', уа) = Ы1~0(",,',",,").
Б противном случае, путь в Г, с»оедпнякэший ",»' и ", ', проходит через ребра у» и у2. Поэтому, в силу аддитивности ориентированной погрешности на путях, мы имеем Ха11о("»: «) 1а11оЬ: »1) +Ха11оЬ. »2) +Ха11о("»'2. у ) = Ы1г(", . ",») + 1а11г(;2, "«р) = Ы1г ("»», ",'») + Ы1«~» ( у2. ",: ) = Ы1<~» (",: .,;«)., что и завершает доказательство утверждения.
° Следствие 5.1. В условият теоремы 5.1, сели дерево Г экстремально, то и Г' экстремально. Изучим поведение ориентированной погрешности при антиредукции. Для этого нам понадооится понятие относительной ориентированной погрешности, которую мы ссичас и определим. Пусть Г произвольное бинарное дерево. и -«некоторое его ребро. Определение. Ориентированной погрешностью И10(";.Г) ребра ",: оп»- носительно дерева Г называется упорядоченная пара чисел (»»», .ЛХ) такая, что т. = — ш1п Ха110( у, "«)., ЛХ = шах Ы10(";, ", )., где шш и шах берутся по всевозможным ребрам из Г. 121 Определение. Ориентированной погре(иностью Га110(Г, ",~) дерева Г относительно ребра ") называется упорядоченная пара насел (т, .ЛХ) такая, что тп = — ш1пЫ1о(ч ") ЛХ = шахЫ1о( ' ":) 1' где шш и шах берутся по всевозможным ребрам из Г.
Утверждение 5.2. Пусть Га11о(";, Г) = (гп. ЛХ). (ЛХ, т). Тогда Га11о(Г,-() Доказательство. Пусть Га11о(Г, у) = (т', ЛХ'). По определению, — Ха11о('~'';"') = — » ( — 1а11о( (,'у')) = » ' ° Х' 11о(",; ) = ЛХ; ЛХ' = шах Ха11в( у'., у) = шах( — Ы1()(",, ",')) = — шш Ы1о(",:., у') = т, что и требовалось доказать. И Для формулировки следующего результата нам понадобятся следующие обозначения. В приведенных ниже формулах все буквы обозначают целые числа. 1) Положим (т, ЛХ) < (р, ((), если и только если т < р и, одновременно, ЛХ< д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
