Геометрия локально минимальных и экстремальных сетей в пространствах с нормами (1102759), страница 11
Текст из файла (страница 11)
при ж = 1, 2 каждая вершина степени 3 инцидентна точечному 1- граничному ребру; ти ребра не бязаны быть очечными Рис. 2.1. Сушественная сеть на Л-нормированной плоскости. 5) в каждой вершине степени 2, инпидентной ребрам ",1 и 1~ таким. что одно пз них является 1-граничным. выполняется равенство 6) прп х = О в каждой вершине степени 3, инпидентной ребрам,1, ",:'2 и ",,я таким, что два па них. например ",.2 и ",В, являются то ~очными 1-граничными, выполняется о(Я('и): Я(720 ~ ' '(Я(13) Я("й)). Замечание.
Отметим. что любая существенная сеть локально минимальна. Слсдуюшсс утверждение можно рассматривать как альтернативное определение сущсствснной сети. Утверждение 2.9. Погруженное дерево на Л-нормированной плоскости не являющееся звездой, является сущеспкьенной сетью, если и только если оно одновременно удовлетворяелп следуюьцим условиям: 1) стехгенм вершинин, дерева не превосходят 3, при атом верьаины сте- пени 1 и 2 граничные, о, схпепени 3 внутренние; ф дерево является объединением пути, все нсконцевые ребра которого точечные, и 1-граничных ребер. инцидентных некоторым внутренним верьаинам этого пути, причем дополнительные ребра точечны, зо, исключением случая х = О, для которого ребра, смежные с концевыми ребрами пути, могут быть неточечными; з2 тт 2Л вЂ” 1 ,'т) угол, между смежными тпочечными ребрами равен ~ ~ или ''л 3 ст 2Л вЂ” 1 Л 3 — [ ~ + 1) с причем при т = О ребри инцидентпны граничной оершинес и равен — —, или + — для т = Ос когда ребра з л: з з л иннидентпны вндтпРенней веРитинес а Угол междУ тпочечным и нетпо—,2Л вЂ” 1, —,2Л, св имм сссбром вссмиси в сссссдсвсс мвжди — ( ( и — ~ ( ( ~- 1); Л 3 Л~З 4') угол между единстпвенным ребром не изолированных 1-усов и смежттт 2Л вЂ” 1 С'сия~ с~и~я~ .
», — (( (-'с1); з б) углы между ребрими, инцидентпными вери1ине усов стпепсни 3,. не рионы междд собой. Доказательство. Необходимостти . Пусть Г: С вЂ” + (Я'.Я произвольная существенная сеть. Покажем. что Г удовлетворяет всем условиям утверждения. Условие 1) утверждения вытекает из услов1п| 1) и 2) определения сущсственной сети; условие 2) из 1) с 3) и 4); а условия 3), 4) с 5) из 1)., 5) и 6). Достпатпочностпь. Докажем. что дерево Г, удовлстворятощсс условиям утверждения, является существенной сетью.
Условие 1) определения существенной сети вытекает из условия 3). условие 2) из 1) с условия 3) и 4) из 2), условия 5) и 6) из 4) и 5). Утверждение доказано. ° На рис. 2.1 приведен пример существенной сети. Определение. Рассмотрим путь из утверждения 2.9 без концевых ребер. Пол ~'чснныи путь т1ы оудст1 называть образдютция пдтпем сетпи. Пусть Г: ( ' -+ Е произвольное локально минимальное погруженное 2 дерево на Л-нормированной плоскости.
Поставим в соответствие дереву Г набор существенных подсетей (набор может быть пустым) дерева Г, экстремальность которых равносильна экстремальности исходного дерева. Сети из этого набора мы будем называть су1цестпвенными предстпаоителями дерева Г. Разрежем дерево Г по всем неточечным рсбрамс которые нс являются 1-граничнымис а также по всем граничным вершинам степени 2. для ин- цндЕНТНЫХ рЕбЕр ";;. 1' = 1с 2. КОтОрЫХ ВЕРНО НсраВЕНСтВО ,с(и( Сс(, Н(7вс( > — (( ( ~-2) тт 2Л вЂ” 1 (это все вершины степени 2 локально минимальных деревьев.
которые нс могут встречаться в существенных сетях). Рассмотрим все связные компоненты Г.;: С.; — + К~, полу-ченныс в результате такого разрезания. Используя утверждения 2.3, 2.4. 2.5. получаем Утверждение 2.1Р. Дереео Г экст»емально п)огда и только тогда, ко- гда каждая сеть Г; экстоемальна.
Найдем условия экстремальности сетей Г;. Для этого нам понадобятся следующие определения. Определение. Пусть Г: С + Ка произвольная погруженная сеть, и Р: Р— + К произвольная подсеть В Г,,являющаяся путем. 07щ) Ост; ком пути Р будем называть каждое ребро сети Г. нс лежащее в Р и пнцидснтнос неконпсвой вершине пути 'Р. Подсеть сети Г, полученная добавлением всех отростков к пути 'Р, называется распаренном пути. Если добавля|отся тс и только тс отростки. которые инцидснтны вершинам пути Р, внутренним для Г, то расширение называется енутренним. Если все добавленные отростки являются точечными, то расширение называется точеннььм. Для». = О мы будем расширение пути называть полутонечным, если все добавленные отростки.
за исключением может быть тех, которые инпидснтны концевым ребрам пути, являются точеч- ными. Для каждой сети Г; рассмотрим множество всех путей. соединяющих вершины степени 1 из Г;. Такис пути будем называть еекуи»имм путями сети Г,;. Отметим, что нс для каждого секущего пути внутреннее расширение является точечным для». = 1, 2 и полуточсчным для» = О. Секущие пути. которые допускают внутреннее (полу)точечное расширение. называются Внуп)ронне (полу) точечными Рассмотрим множество /С = 1Г»: С» — ~ К ) внутрснних (полу)точечных расширений всех внутренне (полу)точечных секущих путей сети Г;.
Сети Г.; для»<. = О, 2 могут соде1»жать грани<1ные ве1»шины степени для которых Разрежем все сети Г» по всем таким вершинам и рассмотрим новое множество сетей (Г»: С'.; -+ К ). На этом мноксстве имеется частичный 2 порядок по включению (Г» < Г, сели Г» является подсетью Г,"). Обозначим через ая,; множество максимальных компонент из (Г») в таком 54 порядке, и положим ()г( = '()', яя .;.
Элементы множества ял будем называть польусущественными представителями сети Г. Из утверждений 2.3, 2А, 2.7 и 2.8 вытекает Теорема 2.1. Пусть Г: С вЂ” + КЯ ьзроизвольное погруженное локв,.льно мин(смальное с)ерево на Х-нормированной плсгск(гсти, и % набег п(глусущественнььх представителей дерева Г. Тогда дерево Г экстпреиально.. если и только если каясдая сеть из яя экстремальна. Исключим из набора эг( все сети. являющиеся объединением граничных и расширенных нитей, а от оставшихся в ()е сетей отрежем все максимальные подсети, являющиеся объединением граничных. расширенных нитей и концевой нити, проделав последовательно разрезания по реорам крепления.
Полученное множество без сетей-звезд обозначим через яя. Сети из множества яя будем называть существенными представителями сети Г. Используя утверждение 2.6, получаем Теорема 2.2. Пусгпь Г: С вЂ” + Ка произвольное погрузя:енное локально минимальное дерево на Х-нормированной плоскости(в и ()л набор срцественньи; прес)ставителей дерева Г. Тогда, каждия сеть из яя .является, существенной сетью.
Дерево Г эк:стремально, если и, только если киясдая, сеть из яя экстремв„льна. Опишем более подрооно, как получить сети из множества К: в предположении, что сеть Г; отлична от ребра. Пусть Г: С вЂ” + КЯ произвольное локально минимальное дерево, нс содержащее нсточсчных ребер, которые нс являются 1-граничными, и граничных вершин стспсни 2, для инцидснтных ребер ",;, г' = 1. 2. которых верно неравенство Определение. Вершины сети Г, имеющие степень больше 1 и инцидентные 1-граничному реору, назывангтся предконцевылил. Все граничные прсдконцсвыс вершины.
а также вершины усов назовем отмеченными. Еромс того. каждую внутреннюю предконцсвую вершину, инцидснтную нсточсчному ребру, также назовем отмененной. Обозначим через У' множество всех отмеченных вершин сети Г. Определение. Путь в Г, содержащий более одной вершины, называется отмеченным, если он соединяет вершины из У и не содержит внутри себя вершин из .с-, внутренних для Г. Путь в Г, содержащий ровно одну вершину х. называется отмеченным, если х Е;с-, х является вершиной усов. и, кроме того, в случае когда Г отлична от изолированных усов, х граничная вершина степени 3 в Г. Концевым рисияи1эением в сети Г отмеченного пути Р: Р— + Б ., со- 2 стоящего более чем из одной вершины. называется подсеть сети Г.
полученная добавлением ребер из Г, пнцидентных концевым вершинам из Р., причем, в случае когда концевая вершина из Р граничная для Г. добавляется любое одно 1-граничное для Г ребро, а в случае когда концевая вершина из Р внутренняя для Г, добавлякэтся все ребра. Концевым расспэирением в сети Г отмеченного пути 'Р: Р— + К~, состоящего ровно из одной вершины, называется подсеть сети Г. полученная следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
