Длина экстремальной сети в нормированном пространстве: формула Максвелла

Полный текст

1. ВВЕДЕНИЕ Рассмотрим следующую задачу. Пусть дано конечное множество точек на плоскости. Требуется построить связный граф, множество вершин которого содержит данное множество точек и длина которого минимальна. Данная задача в литературе известна как проблема Штейнера. Решение этой задачи называется кратчайшей сетью [1, 2, 14, 15]. Очевидно, что решение поставленной задачи будет являться вложенным в плоскость деревом, все ребра которого являются прямолинейными отрезками, и дерево не будет содержать дополнительных вершин (т. е. тех, которые добавляются при построении, такие вершины называются внутренними) степени один. Отметим, что кратчайшая сеть не является единственной. Вместо евклидовой плоскости можно рассматривать произвольное риманово многообразие или метрическое пространство. Но даже в случае евклидовой плоскости задача описания класса кратчайших сетей является довольно трудной. Поэтому сначала рассматриваются сети кратчайшие в малом, так называемые локально минимальные, и сети, длина которых не уменьшается при малых деформациях, - экстремальные сети. Отметим, что с точки зрения римановой геометрии локально минимальные сети являются естественным обобщением обычных геодезических. Нетрудно показать, что каждая экстремальная сеть является локально минимальной [2, 6, 8]. Хорошо известно, что в случае римановых многообразий класс локально минимальных сетей совпадает с классом экстремальных сетей [1, 2, 14, 15], а в случае произвольного нормированного пространства совпадение классов не имеет место [1, 2, 4, 6-8, 13, 15]. Равенство имеет место только в случае гладкой нормы, т. е. когда в каждой точке единичной сферы существует единственная опорная плоскость. Локальная структура локально минимальных сетей на нормированных плоскостях хорошо изучена, см., например, [2, 5, 17]. Степени вершин ограничены четырьмя в случае внутренних вершин и шестью в случае граничных вершин (это заданные вершины). Несмотря на все полученные ограничения на структуру локально минимальных сетей, их топология может быть достаточно сложной, и их число с увеличением количества граничных точек растет очень быстро. Что касается экстремальных сетей, то для некоторых классов нормированных плоскостей их структура описана, см., например, [6-10] для λ-нормированных плоскостей (единичная окружность является правильным 2λ-угольником). Несмотря на возможную довольно сложную структуру локально минимальных сетей на евклидовой плоскости, можно найти их длину, имея только информацию о граничных вершинах Qc 2013 РУДН 5 6 А. Г. БАННИКОВА, Д. П. ИЛЬЮТКО, И. М. НИКОНОВ и граничных ребрах (ребрах, инцидентных граничным вершинам). Классическая формула Максвелла [12] позволяет вычислить длину плоского локально минимального бинарного дерева по координатам граничных вершин и направлениям приходящих в них ребер. В работе [3] Иванов и Тужилин получили формулу длины для локально минимальных сетей в евклидовом пространстве, которые могут содержать вырожденные ребра. Оказывается, что для вычисления длины такой сети достаточно знать координаты граничных вершин и топологию сети. Ответом является максимальное значение некоторой линейной функции на выпуклом компактном подмножестве евклидова пространства, образованном пересечением цилиндров. В случае произвольной нормы локально минимальные сети, затягивающие данное множество точек и имеющие одинаковые направления граничных ребер, могут иметь разную длину. Поэтому для них формула Иванова и Тужилина [3] неприменима. Вместо локально минимальных сетей нужно рассматривать экстремальные сети. Мы обобщаем результаты Иванова и Тужилина, а именно, для экстремальной сети в нормированном пространстве мы строим линейную функцию на некотором компактном подмножестве евклидова пространства, максимум которой дает длину сети. Другая проблема состоит в том, что в случае негладкой нормы нормирующий функционал вектора (см. определения ниже) определяется неоднозначно. В данной работе мы показываем, что можно подобрать нормирующие функционалы граничных ребер для вычисления длины экстремальной сети по формуле Максвелла. Для некоторых нормированных плоскостей мы явно строим соответствующие нормирующие функционалы. Данная статья устроена следующим образом. В разделе 2 мы даем основные определения, касающиеся локально минимальных и экстремальных сетей в нормированных пространствах. Раздел 3 посвящен формулам длины экстремальной сети. Мы доказываем, что существуют нормирующие функционалы граничных ребер экстремальной сети, подстановка которых в формулу Максвелла дает длину сети (теорема 3.1). Также мы предъявляем способ нахождения длины экстремальной сети, зная лишь положения граничных вершин и топологию сети (теорема 3.2). В разделе 4 мы рассматриваем различные примеры нормированных пространств, где нормирующие функционалы для формулы Максвелла ищутся явно. Благодарности. Авторы выражают благодарность А. О. Иванову и А А. Тужилину за полезные советы и постоянное внимание к работе. Работа первого автора выполнена при частичной финансовой поддержке программы поддержки ведущих научных школ РФ (грант № НШ-1410.2012.1) и программы «Научные и научнопедагогические кадры инновационной России» (госконтракт 14.740.11.0794). Работа второго и третьего авторов выполнена при частичной финансовой поддержке гранта Правительства РФ по постановлению № 220, договор 11.G34.31.0053, РФФИ (гранты № 10-01-00748-а и № 12-01-31432мол-а), Программы поддержки ведущих научных школ РФ (грант № НШ-1410.2012.1), программы «Научные и научно-педагогические кадры инновационной России» (госконтракт 14.740.11.0794). 2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ПРЕДВАРИТЕЛЬНЫЕ РЕЗУЛЬТАТЫ В данном разделе мы дадим все определения и сформулируем известные теоремы, необходимые для формулировки и доказательства основных результатов. 1. Определение сети. Определение 2.1. Топологическим графом G называется топологическое пространство, полученное из конечной совокупности отрезков {Ii}i некоторой склейкой по их концам. Пусть π : ∗i Ii → G - каноническая проекция. Образы внутренностей отрезков Ii при отображении π называются ребрами графа G, а π-образы концевых точек отрезков Ii - вершинами. Граф G связен, если он связен как топологическое пространство. Обозначим через V (G) множество вершин графа G, а через E(G) - множество его ребер. Пусть H - произвольный подграф в топологическом графе G. Обозначим через G/w H топологическое пространство, полученное из G отождествлением точек каждой связной компоненты графа H. Пространство G/w H наделяется естественной структурой топологического графа. Граф ДЛИНА ЭКСТРЕМАЛЬНОЙ СЕТИ В НОРМИРОВАННОМ ПРОСТРАНСТВЕ: ФОРМУЛА МАКСВЕЛЛА 7 G/w H называется слабым фактор-графом графа G по подграфу H. При этом каноническую проекцию π : G → G/w H будем называть слабой проекцией. Будем говорить, что граф G2 может быть слабо спроецирован на граф G1, если существует H ⊂ G2, для которого G1 = G2/w H. Определение 2.2. Граф G называется меченым, если на множестве V (G) его вершин задано отображение sgn: V (G) → Z2. Вершины из множества sgn-1(0) называются внутренними для данного графа, а вершины из sgn-1(1) - граничными. Множество граничных вершин графа G обозначается ∂G и называется границей графа G. Ребро, инцидентное (хотя бы одной) граничной вершине, будем называть граничным, в противном случае ребро назовем внутренним. На протяжении всей статьи все рассматриваемые графы являются мечеными и связными, а множество sgn-1(1) не является пустым. Определение 2.3. Пусть G - произвольное дерево и ∂G - его граница. Линейной сетью типа G или, более коротко, сетью типа G называется непрерывное отображение Γ из G в Rn, аффинное на каждом ребре дерева G. Граф G в этом случае называется параметризующим графом сети Γ или ее типом. Замечание 2.1. Мы рассматриваем только линейные сети, т. е. образы ребер графа G являются отрезками прямых или точками, так как мы изучаем кратчайшие сети в нормированных пространствах, и отрезок прямой в нормированном пространстве является кратчайшей кривой. Определение 2.4. Ограничения отображения Γ на вершины, ребра, границу называются соответственно вершинами, ребрами, границей ∂Γ сети Γ. Более того, в дальнейшем мы всегда будем предполагать, что все структуры, возникающие на параметризующем графе, такие как инцидентность, смежность, ориентация и т. д., переносятся на сети. Определение 2.5. Ребро сети называется вырожденным, если оно является отображением в точку. Сеть Γ называется погруженной, если она не содержит вырожденных ребер. Замечание 2.2. В случае погруженной сети мы часто будем отождествлять сеть с ее образом. Определение 2.6. Пусть δ = {Gk } - семейство непересекающихся поддеревьев в G. Определим редуцированное дерево G/δ как слабый фактор-граф графа G по ∗k Gk. Граница дерева G/δ состоит из всех вершин этого дерева, содержащих элементы из ∂G. Для каждой сети Γ определим Γ-редукцию дерева G, выбрав в качестве Gk связные компоненты подграфа, порожденного вырожденными ребрами дерева G. Отметим, что сеть Γ естественным образом порождает невырожденную сеть типа G/δ. Определение 2.7. Пусть Γ: G → Rn - произвольная сеть, ∂Γ: ∂G → Rn - ее граница. Сеть lG Γ: G → Rn с границей ∂Γ: ∂G → Rn называется подсетью сети Γ, если Γ= Γl , где G является подграфом графа G, и его граница ∂G состоит из вершин ∂G ∩ G и вершин G, которые имеют в G степень больше, чем в G. Если подсеть Γ отлична от Γ, то она называется собственной подсетью сети Γ. Пусть G - произвольный граф с границей ∂G (возможно пустой) и P ∈ G - некоторая его точка. Допустимой окрестностью U ⊂ G точки P графа G называется замыкание связной окрестности этой точки, не содержащей вершин графа G, отличных от P (если P - вершина). Наделим окрестность U структурой графа, объявив вершинами все точки из ∂U ∪{P }, а ребрами - внутренности отрезков в U, соединяющих эти точки. Полученную звезду обозначим через GU и будем называть локальным графом с центром в точке P . Определим каноническую границу ∂GU локального графа GU , включив в нее все вершины из ∂U, а также вершину P, если P - граничная вершина графа G, т. е. ∂GU = (∂G ∩ U ) ∪ (G ∩ ∂U ). Определение 2.8. Локальная сеть сети Γ: G → Rn - это ограничение отображения сети Γ на какой-то ее локальный граф. 2. Локально минимальные и экстремальные сети. Пусть дано произвольное нормированное пространство M = (Rn, 1· 1) с нормой 1· 1. Рассмотрим сеть Γ: G → Rn типа G. Сопоставим каждому ребру vkvl, vk, vl ∈ V (G), дерева G отрезок 1Γ(vk ), Γ(vl)l (который может быть вырожденным). Тем самым естественно определены 8 А. Г. БАННИКОВА, Д. П. ИЛЬЮТКО, И. М. НИКОНОВ x3 o 120 o 120 x0 o x1 120 x2 РИС. 1. Критические углы на евклидовой плоскости углы между смежными невырожденными ребрами сети и длина сети C(Γ) как сумма длин всех ее ребер: C(Γ) = '\" vkvl∈E(G) 1Γ(vl) - Γ(vk )1. Определение 2.9. Пусть X - произвольное конечное множество точек в пространстве. Если образ ∂Γ совпадает с X, то мы говорим, что сеть Γ затягивает множество X. Без ограничения общности всегда будем предполагать, что отображение ∂Γ является взаимно однозначным с образом. Рассмотрим множество всех погруженных сетей в пространстве, затягивающих множество X. Тогда сеть наименьшей длины среди всех таких сетей называется минимальным деревом Штейнера или кратчайшей сетью с данной границей. Сеть называется локально минимальной, если любая локальная сеть является кратчайшей относительно своей канонической границы. Опишем структуру локально минимальных сетей в произвольном нормированном пространстве. Для этого нам понадобится ряд определений. Определение 2.10. Угол ∠x1x0x2 (все точки x0, x1, x2 ∈ Rn попарно различны) в пространстве Rn называется критическим, если существует такая точка x3 ⊗= x0, что при x = x0 сумма 1xx11 + 1xx21 + 1xx31 минимальна. Угол ∠x1x0x2 называется поглощающим, если x0 минимизирует сумму 1xx01 + 1xx11 + 1xx21. Замечание 2.3. Критический угол в евклидовом пространстве - это угол, равный 120◦, см. рис. 1. Поглощающий угол в евклидовом пространстве - это угол, равный или больший 120◦. Критические углы для произвольного нормированного пространства представляют собой аналог углов 120◦ на евклидовой плоскости. Обозначим через B = {x ∈ Rn : 1x1 1} единичный шар и через S = {x ∈ Rn : 1x1 = 1} единичную сферу в нормированном пространстве M. Пусть M ∗ - сопряженное пространство к пространству M, т. е. пространство линейных функционалов на Rn. Элементы сопряженного пространства M ∗ называются ковекторами. Значение функционала ϕ ∈ M ∗ на элементе x мы будем обозначать через ϕ(x). Мы будем отождествлять пространство M ∗, рассматриваемое как линейное пространство, с пространством Rn, имея в виду следующий изоморфизм. Пусть (·, ·) - стандартное евклидово скалярное произведение. Тогда для любого линейного функционала (ковектора) ϕ из M ∗ существует такой единственный вектор v ∈ Rn, что для любого элемента x ∈ Rn имеем ϕ(x) = (v, x). Таким образом мы отождествляем линейные функционалы на M и векторы в M, и значение функционала на векторе - это просто скалярное произведение соответствующих векторов. Пространство M ∗ наделяется нормой 1· 1∗, которая называется конормой и является двойственной к норме в M : 1ϕ1∗ = sup lxl=1 ϕ(x) для любого линейного функционала ϕ ∈ M ∗. Известно, что для любого вектора x ∈ M, x ⊗= 0, существует такой функционал ϕ ∈ M ∗, что 1ϕ1∗ = 1 и ϕ(x) = 1x1. Назовем такой функционал нормирующим функционалом или субградиентом для x и обозначим через px. Если x = 0, то через px обозначим произвольный ковектор, по конорме не превосходящий единицу. Справедливо следующее предложение, связывающее критические и поглощающие углы с нормирующими функционалами ребер угла. ДЛИНА ЭКСТРЕМАЛЬНОЙ СЕТИ В НОРМИРОВАННОМ ПРОСТРАНСТВЕ: ФОРМУЛА МАКСВЕЛЛА 9 Предложение 2.1 (см. [2, 17]). 1. Угол ∠x1x0x2 является критическим углом тогда и только тогда, когда существуют такие нормирующие функционалы px1-x0 и px2-x0 , что 1px1-x0 + px2-x0 1∗ = 1. 2. Угол ∠x1x0x2 является поглощающим углом тогда и только тогда, когда существуют такие нормирующие функционалы px1-x0 и px2-x0 , что 1px1-x0 + px2-x0 1∗ 1. Последнее равносильно тому, что угол ∠x1x0x2 содержит какой-то критический угол ∠x± x0x± с той же вершиной x0. 1 2 Следующая теорема, являющаяся следствием теоремы 6.4 из [2], говорит нам, какие углы должны быть у локально минимальной сети. Теорема 2.1. Пусть Γ: G → R2 - произвольная локально минимальная сеть в нормированном пространстве. Тогда 1. каждая вершина степени 1 является граничной; 2. каждый угол между смежными ребрами является поглощающим; 3. для любой внутренней вершины x, смежной вершинам xi, существуют такие нормирующие функционалы pxi-x, что ), pxi-x = 0. i Замечание 2.4. У локально минимальной сети каждый угол во внутренней вершине степени три является критическим. Определение 2.11. Нормированная плоскость называется λ-нормированной, если единичная окружность представляет собой правильный 2λ-угольник, вписанный в стандартную евклидову окружность радиуса 1. Дадим критерий локальной минимальности сети на нормированной плоскости. Теорема 2.2 (см. [17]). Пусть Γ: G → R2 - погруженная сеть на нормированной плоскости. Сеть Γ является локально минимальной тогда и только тогда, когда: 1. каждая вершина степени 1 является граничной; 2. каждый угол между смежными ребрами является поглощающим; 3. каждый угол между смежными ребрами во внутренней вершине степени 3 является критическим; 4. ни для какой граничной вершины степени четыре не существует такой прямой, проходящей через нее, что все ребра, инцидентные этой вершине, лежат в одной замкнутой полуплоскости, определенной этой прямой, за исключением случая нормированной плоскости, изометричной 3-нормированной плоскости; 5. ни для какой внутренней вершины степени три не существует такой прямой, проходящей через нее, что все ребра, инцидентные этой вершине, лежат в одной открытой полуплоскости, определенной этой прямой; 6. во внутренней вершине степени четыре по крайней мере два противоположных ребра являются параллельными; 7. степень внутренней вершины не превосходит четырех, а степень граничной вершины не превосходит шести, причем степени 5 и 6 возможны только в нормированных плоскостях, изометричных 3-нормированной плоскости. Пусть Γ: G → Rn - произвольная сеть. Определение 2.12. Непрерывное отображение Ψ: G × I → Rn такое, что для каждого ребра e из G отображение Ψ|e×I является аффинным и непрерывно дифференцируемым, причем для всех g ∈ G имеет место равенство Ψ(g, 0) = Γ(g), называется деформацией сети Γ. Положим Ψ(g, t) = Γt(g) и в дальнейшем будем называть деформацией само однопараметрическое семейство {Γt : G → Rn} . Всегда будем предполагать, что деформация неподвижна на границе, т. е. Ψ(v, t) = Γ(v) для любой вершины v ∈ ∂G и любого t ∈ [0, 1]. Рассмотрим теперь траекторию 10 А. Г. БАННИКОВА, Д. П. ИЛЬЮТКО, И. М. НИКОНОВ движения каждой точки сети Γ при деформации Γt. Для этого зафиксируем некоторую точку dΓt(P ) l P ∈ G и рассмотрим кривую Γt(P ). Вдоль Γ определено поле полем деформации Γt. l dt lt=0 , которое называется Определение 2.13. Сеть Γ называется слабо критической или слабо экстремальной типа G, d l если для любой деформации Γt, t ∈ [0, 1], где Γt=0 = Γ, выполнено соотношение l dt lt=0+ l(Γt) 0. Определение 2.14. Будем говорить, что сеть Γ2 может быть слабо спроецирована на сеть Γ1, если существует слабая проекция π : G2 → G1 такая, что Γ2 = Γ1 ◦ π. Пусть Γ и Γ± - произвольные сети, причем Γ± может быть слабо спроецирована на Γ. Произвольную деформацию сети Γ± назовем деформацией с расщеплением сети Γ. Определение 2.15. Погруженная сеть Γ называется критической или экстремальной, если для любой деформации c расщеплением Γ±t, t ∈ [0, 1], где Γ±t=0 = Γ±, выполнено соотношение d l l ± dt lt=0l(Γt) 0. Сформулируем необходимые условия слабой экстремальности и экстремальности сети, которые вытекают из критерия слабой экстремальности, полученного А. О. Ивановым и А. А. Тужилиным (см. [2, Теорема 6.4]). Теорема 2.3. Пусть Γ: G → Rn - произвольная (слабо) экстремальная сеть. Тогда каждому ребру e = vw (необязательно невырожденному в случае слабо экстремальной сети) дерева G можно сопоставить такой нормирующий функционал pv,e ∈ M ∗, соответствующий направлению ребра Γ(e) сети Γ (в случае вырожденного ребра мы считаем, что pv,e равен нормирующему функционалу p0 нулевого вектора), приходящего в точку Γ(v), что pv,e = -pw,e и в каждой внутренней вершине v дерева G выполняется соотношение '\" pv,e = 0. (2.1) e: v∈e 1. ДЛИНА (СЛАБО) ЭКСТРЕМАЛЬНОЙ СЕТИ Пусть Γ: G → Rn - произвольная сеть типа G и ϕ : ∂G → Rn, ∂G = {v1,..., vm}, - ее граничное отображение. Положим xi = Γ(vi) ∈ Rn, где V (G) = {v1,..., vm+s}. Будем отождествлять границу сети Γ с точками x = (x1,..., xm) пространства Rnm и будем считать, что граница задана. Обозначим через [G, ϕ] множество всех сетей в Rn типа G с границей ϕ : ∂G → Rn. Каждая сеть Γ из [G, ϕ] однозначно задается образами xi, i > m, всех внутренних вершин G. Записав последовательные xi, i > m, как компоненты вектора (xm+1,..., xm+s), мы отождествим множество [G, ϕ] с пространством Rns. Длина сети представляет собой вещественную функцию CG,ϕ на [G, ϕ]. Легко видеть, что эта функция выпукла и стремится к бесконечности при неограниченном возрастании аргумента. Поэтому множество минимумов этой функции не пусто и выпукло. Оказывается, см. [6, 8], что каждая сеть, соответствующая минимуму этой функции, является слабо экстремальной сетью типа G, и каждая слабо экстремальная сеть типа G реализует минимум этой функции. По определению, длину слабо экстремальной сети можно вычислить как наименьшее значение функции CG,ϕ на Rns. Однако эта функция представляет собой сумму квадратных корней из многочленов второй степени от координат внутренних вершин, что осложняет исследование экстремальных сетей в терминах этой функции. Следуя статье [3] Иванова и Тужилина, в настоящем разделе мы покажем, как можно вычислить длину (слабо) экстремальной сети в нормированном пространстве, максимизируя линейную функцию, но на более сложном конфигурационном пространстве: криволинейном выпуклом многограннике, являющемся пересечением цилиндров и линейного подпространства. Перед доказательством основной теоремы раздела мы докажем теорему существования нормирующих функционалов граничных ребер, при подстановке которых в формулу Максвелла [3] мы получим формулу длины сети. ДЛИНА ЭКСТРЕМАЛЬНОЙ СЕТИ В НОРМИРОВАННОМ ПРОСТРАНСТВЕ: ФОРМУЛА МАКСВЕЛЛА 11 Теорема 3.1. Пусть Γ - произвольная (слабо) экстремальная сеть. Тогда для каждой граничной вершины vi ∈ ∂G и инцидентного ей ребра ei существует такой нормирующий функционал pvi,ei ∈ M ∗, соответствующий направлению ребра Γ(ei) сети Γ, приходящего в точку xi, что длина сети Γ равна m C(Γ) = '\" pv ,e (xi). (3.1) i i i=1 Доказательство. Для каждой вершины v ∈ V (G) и каждого инцидентного ей ребра e графа G возьмем нормирующие функционалы pv,e ∈ M ∗ из теоремы 2.3. Пусть e = vw - произвольное ребро графа. Тогда, поскольку pv,e = -pw,e, имеем pv,e(Γ(v)) + pw,e(Γ(w)) = pv,e(Γ(v) - Γ(w)) = 1Γ(v) - Γ(w)1. Применяя последнее равенство для сети и для наших нормирующих функционалов и учитывая равенство (2.1), получаем m '\" pv ,e i m '\" v ,e i m+s '\" '\" j v ,e i m+s '\" '\" v ,e i i=1 i i (x ) = p i i=1 i (x )+ p i i=m+1 eji :vi∈eji (x ) = i p i i=1 e: vi∈e (x ) = = '\" e=vivj ∈E(G) i pv ,e(xi - xj ) = '\" e=vivj ∈E(G), xi/=xj i pv ,e(xi - xj ) = '\" e=vivj ∈E(G), xi/=xj 1xi - xj 1 = C(Γ). Перейдем теперь к формулировке основного результата. Используя структуру дерева G, зададим на пространстве Rmn, а точнее, на пространстве (M ∗)m = M ∗ × ··· × M ∗ (напомним, что элементы из M ∗ мы отождествляем с векторами из Rn), m с координатами (θ1,..., θn,..., θ1 ,..., θn ) систему SG, состоящую из уравнений и неравенств на 1 1 m m переменные θj . Положим θk = (θ1,..., θn) и пусть θ = (θ1,..., θm). k k k Пусть e - некоторое ребро дерева G. Обозначим через Gr, r = 1, 2, связные компоненты графа G \ e. Таким образом, G \ e = G1 ∗ G2, и пусть ∂Gr = ∂G ∩ V (Gr ). Полученное в результате разбиение {∂G1, ∂G2} множества ∂G обозначим через PG(e). Выберем одно из ∂Gr ∈ PG(e), и I p I пусть ∂Gr = {vk1 ,..., vkp }. Обозначим через σe неравенство I ), θkq I 1, где 1· 1∗ - норма Iq=1 I∗ m сопряженного пространства M ∗, а через σ - ковекторное уравнение составим из σ и σe для всех ребер e дерева G. ), θk = 0 в M ∗. Систему SG k=1 Пусть |SG| ⊆ (M ∗)m - множество всех решений системы SG. Отметим, что условие σe не зависит от выбора компонент ∂Gk в силу выполнения равенства σ. Кроме того, каждое σe задает выпуклое подмножество в Rmn, ограниченное цилиндром над выпуклым ограниченным множеством, т. е. произведение выпуклого ограниченного множества в Rn на Rn(m-1), а 0 и близкие к 0 точки подпространства L, заданного уравнением σ, являются решениями системы SG. Поэтому |SG| - выпуклое тело в подпространстве L. Положим Cϕ(θ) = θ1(x1)+ ··· + θm(xm), где xi = ϕ(vi), 1 i m. Теорема 3.2. Во введенных выше обозначениях длина каждой слабо экстремальной сети из [G, ϕ] равна наибольшему значению линейной функции Cϕ на выпуклом множестве |SG|. Доказательство. Пусть θ ∈ |SG| - произвольная точка множества |SG|. Используя ковектор θ, припишем каждой паре (v, e), где e ∈ E(G) - ребро дерева G, инцидентное вершине v ∈ V (G), ковектор θv,e ∈ M ∗ по следующему правилу. Пусть PG(e) = {∂G1, ∂G2}, причем v ∈ V (G1) и ∂G1 = {vk1 ,..., vkp }. Тогда положим p q . θv,e = '\" θk q=1 Доказательство следующих лемм может быть найдено в [3]. 12 А. Г. БАННИКОВА, Д. П. ИЛЬЮТКО, И. М. НИКОНОВ Лемма 3.1. Для каждого ребра e = vw дерева G имеем: θv,e = -θw,e. Лемма 3.2. Для каждой граничной вершины vi, 1 i m, имеем: θi = '\" e:vi∈e θvi,e. Лемма 3.3. Если ej, j = 1, ..., r, - все ребра дерева G, инцидентные его внутренней вершине v, то r '\" θv,e j=1 j = 0. Лемма 3.4. Для каждой вершины v дерева G и каждого ребра e, инцидентного v, имеем: 1θv,e1∗ 1. Лемма 3.5. В сделанных обозначениях имеем: θ1(x1)+ ··· + θm(xm) = '\" (vk ,e),vk ∈e θvk ,e(xk ). Пусть Γ ∈ [G, ϕ] - (слабо) экстремальная сеть. Используя леммы 3.4 и 3.5, имеем: θ1(x1)+ ··· + θm(xm) = '\" (vk ,e), vk ∈e k θv ,e(xk ) = '\" e=vkvl θvk ,e(xk - xl) = ( xk - xl \ = '\" e=vkvl 1xk - xl1θvk ,e 1xk - xl1 '\" e=vkvl 1xk - xl1 = C(Γ). Так как, напомним, θ - произвольная точка из |SG|, заключаем, что наибольшее значение функции Cϕ(θ) на |SG| не превосходит C(Γ). Покажем теперь, что это наибольшее значение достигается. Положим ξk = ), e:vk ∈e pvk ,e при 1 k m, где нормирующие функционалы pvk ,e взяты из теоремы 2.3. Покажем, что ковектор ξ = (ξ1,..., ξm) ∈ Rmn удовлетворяет системе SG и что Cϕ(ξ) = C(Γ). Действительно, рассмотрим произвольное ребро e = vw дерева G, и пусть G \ e = G1 ∗ G2, причем v ∈ V (G1), и ∂G1 = ∂G ∩ V (G1) = {vk1 ,..., vkp }. Доказательство следующей леммы дословно повторяет доказательства лемм 6 и 7 из [3]. p Лемма 3.6. В сделанных выше обозначениях имеем pv,e = ), ξkq и q=1 m ), ξk = 0. k=1 Из леммы 3.6 и условия 1pv,e1∗ 1 вытекает, что ξ удовлетворяет каждому неравенству σe, а также условию σ. Таким образом, ξ ∈ |SG|. Далее, m Cϕ(ξ) = ξ1(x1)+ ··· + ξm(xm) = '\" '\" m+s k pv ,e(xk ) = '\" '\" pvk ,e(xk ) = = '\" e=vkvl∈E Теорема доказана. k=1 e: vk ∈e k pv ,e(xk - xl) = '\" e=vkvl∈E, xk /=xl k=1 e: vk ∈e k pv ,e(xk - xl) = '\" e=vkvl∈E, xk /=xl 1xk - xl1 = C(Γ). Замечание 3.1. Отметим, что по леммам 3.2 и 3.4 каждая координата вектора θ ∈ |SG| ограничена, поэтому |SG| является компактным подмножеством Rmn. Таким образом, с учетом вышесказанного |SG| - выпуклый компакт. Пусть, как и выше, G - дерево с границей ∂G = {v1,..., vm}⊆ V (G) и Ed ⊆ E(G) - некоторый набор ребер дерева G. Обозначим через δ = {Gk } семейство непересекающихся поддеревьев в G такое, что объединение всех их ребер совпадает с Ed. Предположим, что каждое из Gk пересекает ∂G не более чем по одной вершине. Такие семейства Ed будем называть допустимыми. Рассмотрим редуцированное дерево G/δ и выберем в качестве его границы те вершины, которые ДЛИНА ЭКСТРЕМАЛЬНОЙ СЕТИ В НОРМИРОВАННОМ ПРОСТРАНСТВЕ: ФОРМУЛА МАКСВЕЛЛА 13 пересекаются с ∂G. В силу ограничений, накладываемых на деревья Gk из δ, полученное граничное множество состоит из того же числа точек, что и ∂G, что позволяет отождествить его с ∂G. Таким образом, для произвольного отображения ϕ : ∂G → Rm определены два пространства: [G, ϕ] и [G/δ, ϕ]. Если Γ ∈ [G, ϕ] вырождает все ребра из Ed, то Γ естественным образом порождает сеть из [G/δ, ϕ], которую мы обозначим через Γ/δ. Как и выше, определим систему SG, состоящую из равенства σ и неравенств σe, и выкинем из нее все неравенства, соответствующие ребрам e ∈ Ed. Полученную систему обозначим через SG \ Ed. Теорема 3.3. В сделанных выше обозначениях длина экстремальной сети Γ/δ ∈ [G/δ, ϕ] равна наибольшему значению линейной функции Cϕ на множестве |SG \ Ed| решений системы SG \ Ed. Доказательство. Достаточно заметить, что SG \ Ed = SG/δ, так как для каждого ребра e из G/δ имеем PG/δ (e) = PG(e). Доказательство закончено. Таким образом, выбрасывание из системы SG неравенств вида σe равносильно факторизации дерева G по соответствующим ребрам e. 2. ФОРМУЛА ДЛИНЫ ДЛЯ ЛОКАЛЬНО МИНИМАЛЬНОЙ СЕТИ В данном разделе мы рассмотрим примеры нормированных пространств, где формула длины справедлива и для локально минимальных сетей. 1. Случай гладкой нормы. Определение 4.1. Пусть F ⊂ Rn - выпуклая поверхность и P ∈ F - произвольная ее точка. Проходящая через P гиперплоскость Π называется опорной плоскостью поверхности F в точке P, если F лежит в одном из замкнутых полупространств, ограниченных Π. Определение 4.2. Нормированное пространство называется гладким, если в каждой точке его единичной сферы существует единственная опорная плоскость. Предложение 4.1. Нормированное пространство M является гладким тогда и только тогда, когда для любого 0 ⊗= x ∈ M существует единственный нормирующий функционал px. Поскольку в случае гладких нормированных пространств класс локально минимальных сетей совпадает с классом экстремальных сетей, то формула (3.1) справедлива и для локально минимальных сетей. Кроме того, в случае гладкого нормированного пространства нормирующие функционалы из теоремы 2.3 единственны. 2. Случай гладкой строго выпуклой нормированной плоскости. Определение 4.3. Нормированное пространство называется строго выпуклым, если единичный шар является строго выпуклым множеством. Лемма 4.1 (см. [17]). Пусть M - гладкая строго выпуклая нормированная плоскость. Тогда для любого единичного вектора x1 существуют единственные два таких единичных вектора x2 и x3, что px1 + px2 + px3 = 0. Следствие 4.1. Пусть дана невырожденная локально минимальная сеть на гладкой строго выпуклой нормированной плоскости, все граничные вершины которой имеют степень 1. Тогда с точностью до знака существуют не более трех разных направлений ребер данной сети. Определим число вращения сети, которое является аналогом числа вращения на стандартной евклидовой плоскости, введенного А. О. Ивановым и А. А. Тужилиным, см. [2]. Пусть на плоскости задана стандартная ориентация, что дает возможность определить положительное вращение (в левую сторону) и отрицательное вращение (в правую сторону). Пусть e1 и e2 - два ребра дерева G, и γ - единственный путь в дереве G, их соединяющий. Тогда числом вращения tw(e1, e2) от ребра e1 к ребру e2 называется разность количеств левых (положительных) и правых (отрицательных) поворотов во внутренних вершинах пути γ при движении от e1 к e2. Отметим, что эта функция кососимметрическая и аддитивная вдоль путей. 14 А. Г. БАННИКОВА, Д. П. ИЛЬЮТКО, И. М. НИКОНОВ x2(-1,1) x3 (0,1) x4 (1,1) x2(-1,1) x3 (0,1) x4 (1,1) (0,0) (0,0) x1 (-1,-1) x5 (1,-1) x1 (-1,-1) x5 (1,-1) РИС. 2. Локально минимальная сеть на манхэттенской плоскости Используя следствие 4.1, мы можем для локально минимальной сети на гладкой строго выпуклой нормированной плоскости, зная направление ребра и число вращения от него до другого, определить направление последнего ребра. Пусть ξi - направления граничных ребер ei, ориентированных в сторону граничных вершин, и ki,j - числа вращения от ei к ej (при проходе пути ориентация первого ребра меняется). Сразу получаем Теорема 4.1. Пусть η1 и η2 - такие направления, что pξ1 + pη1 + pη2 = 0, и (ξ1, η1) задает положительную ориентацию на R2, а (ξ1, η2) - отрицательную ориентацию. Тогда если 1. ki,1 ≡ 0 (mod 6), то направление ξi совпадает с направлением ξ1; 2. ki,1 ≡ 3 (mod 6), то направление ξi противоположно направлению ξ1; 3. ki,1 ≡ 1 (mod 6), то направление ξi совпадает с направлением η1; 4. ki,1 ≡ 4 (mod 6), то направление ξi противоположно направлению η1; 5. ki,1 ≡ 5 (mod 6), то направление ξi совпадает с направлением η2; 6. ki,1 ≡ 2 (mod 6), то направление ξi противоположно направлению η2. Следствие 4.2. Зная направление одного граничного ребра и числа вращения от него до всех других граничных ребер, мы можем найти длину сети. 5. λ-НОРМИРОВАННЫЕ ПЛОСКОСТИ Покажем, что теорема 3.2 не верна для локально минимальных сетей в негладких нормированных пространствах. Мы рассмотрим случай манхэттенской плоскости. Напомним, что манхэттенская плоскость - это плоскость с нормой 1x1 = |x1| + |x2|, где x = (x1, x2). Легко видеть, что единичная окружность для манхэттенской плоскости - это квадрат, т. е. это 2-нормированная плоскость. Таким образом, манхэттенская плоскость не является гладкой. Структура локально минимальных и экстремальных сетей на манхэттенской плоскости описана в [2]. Рассмотрим локально минимальную сеть, состоящую из пяти граничных вершин и трех внутренних, см. рис. 2. Отметим, что эта сеть не является экстремальной. Пусть граничные вершины имеют координаты x1 = (-1, -1), x2 = (-1, 1), x3 = (0, 1), x4 = (1, 1), x5 = (1, -1), тогда соответствующие им направления граничных ребер будут (0, 1) и (0, -1). Рассмотрим деформацию, переводящую эту сеть в другую, затягивающую ту же самую границу и с теми же направлениями ребер на ней (см. рис. 2). Заметим, что она тоже будет локально минимальной сетью, но длина уменьшается, то есть мы не можем однозначно вычислить длину сети, зная только граничные вершины и топологию сети. Следовательно, теорема 3.2 в данном случае не применима. Этот пример - следствие того, что на манхэттенской плоскости локальная минимальность не эквивалентна экстремальности сети (см. [4]) ДЛИНА ЭКСТРЕМАЛЬНОЙ СЕТИ В НОРМИРОВАННОМ ПРОСТРАНСТВЕ: ФОРМУЛА МАКСВЕЛЛА 15 x2(-1,1) x3 (1,1) x5 (-1,0) x1 (-1,-1) x4(1,-1) РИС. 3. Произвольные нормирующие функционалы граничных ребер Покажем, что в формуле (3.1) нельзя выбирать нормирующие функционалы граничных ребер произвольным образом. Возьмем сеть с границей x1 = (-1, -1), x2 = (-1, 1), x3 = (1, 1), x4 = (1, -1), изображенную на рис. 3. Заметим, что длина сети равна 6. Если же мы рассмотрим нормирующий функционал (0, 1) для ребер, инцидентных x2 и x3, и нормирующий функционал (0, -1) для ребер, инцидентных x1 и x4, то при подсчете длины по формуле (3.1) длина сети должна быть 4. Почему так получается? Рассмотрим для примера ребра x5x1 и x5x2, где x5 = (-1, 0). Для вектора x1 - x5 определен нормирующий функционал px1-x5 = (0, -1). Наша цель - доопределить нормирующий функционал px5-x1 = (a, b) (в вершине x5) таким образом, чтобы выполнялось следующее условие: px1-x5 (x1)+ px5-x1 (x5) = 1x5 - x11. Подставив известные нам значения, получаем, что a = 0, b = 1, следовательно, px5-x1 = (0, 1). Аналогично рассматривая ребро x5x2, получаем px5-x2 = (0, -1). Заметим, что так как в точку x5 приходят три ребра, то всего в ней должны быть определены три нормирующих функционала инцидентных ей ребер. При этом их сумма должна быть равна 0, чтобы можно было применять формулу (3.1). Но это невозможно, так как сумма уже двух из них равна 0. Рассмотрим формулу (3.1) на λ-нормированных плоскостях, где λ ⊗= 3, 4, 6. Для случая λ = 2 мы передокажем теорему 3.1. Из полученного доказательства будет видно, что справедливость формулы (3.1) для экстремальных сетей следует из справедливости формулы (3.1) для сетей простого вида, которые представляют собой «горизонтальные» или «вертикальные» фрагменты, а для таких фрагментов нормирующие функционалы ребер можно выбрать явно. Для остальных λ мы предъявим нормирующие функционалы граничных ребер, дающие формулу (3.1) для любой экстремальной сети, граница которой состоит из вершин степени один. 1. Манхэттенская плоскость. Без ограничения общности мы рассматриваем сети, ребра которых могут быть только вертикальными или горизонтальными, и все граничные вершины имеют степень один. Сформулируем и докажем следующие леммы. Лемма 5.1. Для любого единичного элемента p1 сопряженного пространства M ∗ к манхэттенской плоскости существуют такие два единичных элемента p2 и p3, что p1 + p2 + p3 = 0. Доказательство. Доказательство аналогично доказательству предложения 3 из [17], также см. [11]. Лемма 5.2. Для экстремальной сети с одной внутренней вершиной степени три на манхэттенской плоскости нормирующий функционал ребра, перпендикулярного двум другим, который дает ноль в сумме с нормирующими функционалами двух других ребер, определен однозначно. Доказательство. Рассмотрим сеть, состоящую из двух горизонтальных ребер и одного вертикального, направленного вниз, см. рис. 4, и всевозможные направления для функционала в граничной вершине горизонтального ребра. 16 А. Г. БАННИКОВА, Д. П. ИЛЬЮТКО, И. М. НИКОНОВ e3 e1 e2 3 p3 p p p p p 1 2 1 2 p 2 p 1 p 3 РИС. 4. Нормирующие функционалы для сети из трех граничных вершин 2 e1 e2 2 e2 e1 v 1 v e3 3 1 3 e4 e3 4 РИС. 5. Сети Когда нормирующий функционал p1 ребра e1 находится в верхней замкнутой полуплоскости (рис. 4, а) и б)), два других нормирующих функционала существуют, и нормирующий функционал p2, соответствующий вертикальному ребру, не изменяется. Если же p1 расположен в нижней полуплоскости (рис. 4, в)), то для вертикального ребра не существует нормирующего функционала, удовлетворяющего условиям. То есть, p2 = (0, -1) и это единственное возможное значение функционала в этой вершине, для которого выполнены условия теоремы, что и требовалось доказать. Приведем теперь для манхэттенской плоскости конструкцию явного построения нормирующих функционалов, фигурирующих в доказательстве теоремы 3.1. Докажем по индукции, где индукцию проведем по числу n всех вершин сети. База индукции. Случай n = 4 доказан в лемме 5.2. Предположение индукции. Пусть для сетей с любым числом вершин, меньшим k, мы можем подобрать нормирующие функционалы ребер требуемым образом. Индуктивный переход. Докажем наше утверждение для сетей с числом вершин k. Любую сеть можно представить в виде, изображенном на рис. 5, а именно в виде, когда внутренняя вершина соединена с тремя подсетями: Γ± , Γ± и Γ± , или с четырьмя подсетями: Γ± , Γ± , Γ± и Γ± . 1 2 3 1 2 3 4 Предположим, что сеть Γ имеет вершину степени четыре. Тогда Γ можно представить в виде объединение двух сетей Γvert и Γhor (см. рис. 6). Если сеть Γ экстремальна, то сети Γvert и Γhor также будут экстремальны. По предположению индукции для каждой из сетей Γvert и Γhor существуют нормирующие функционалы ребер, обладающие необходимыми свойствами. Набор нормирующих функционалов для сети Γ получается следующим образом. Для ребер, инцидентных вершинам подсетей Γ± , Γ± , Γ± и Γ± , мы берем нормирующие функционалы соответствующих ребер 1 2 3 4 ДЛИНА ЭКСТРЕМАЛЬНОЙ СЕТИ В НОРМИРОВАННОМ ПРОСТРАНСТВЕ: ФОРМУЛА МАКСВЕЛЛА 17 2 ehor evert 1 3 hor vert 4 РИС. 6. Вершина степени четыре 1 2 2 e1 e2 e1 e2 1 v 3 v e3 e3 РИС. 7. Подсети из Γvert и Γhor. На ребрах e1 и e3 мы ставим нормирующие функционалы ребра ehor, а на ребрах e2 и e4 - ребра evert. Далее мы можем считать, что сеть не содержит вершин степени четыре. Тогда сеть имеет вид, изображенный на рис 5 слева. Сначала рассмотрим случай, когда каждая из трех подсетей содержит не менее одной внутренней вершины. Тогда зададим функционалы для нашей сети с 2 помощью двух других сетей Γ1 и Γ2, полученных из Γ. Сеть Γ1 состоит из сети Γ± с вершиной v, 1 ребер e1, e2, e3 и инцидентных им вершин, а сеть Γ2 включает в себя сети Γ± 3 и Γ± с вершиной v, ребра e1, e2, e3 и инцидентные им вершины (см. рис. 7). У каждой из полученных сетей число вершин меньше, чем у Γ. Следовательно, по индукции для них можно задать направления граничных ребер в соответствии с условиями теоремы. Из леммы 5.2 следует, что нормирующий функционал ребра e2 будет один и тот же для каждой из сетей Γ1 и Γ2. Если из сети Γ1 выкинуть ребра e1 и e3, то полученная сеть по-прежнему будет 2 экстремальной, и функционалы для всех ребер Γ± , так же как и для e2, останутся теми же. Следовательно, на сеть Γ мы можем перенести те же функционалы, что были у сетей Γ1 и Γ2 (см. 1 рис. 7). Случай, когда Γ± 3 или Γ± вырождаются в одну вершину, рассматривается аналогично. 2 Если же в вершину вырождается Γ± и сеть Γ имеет вид Γ2, то такой случай сводится к предыдущим, если хотя бы для одной вершины мы можем представить сеть в виде объединения трех невырожденных подсетей. Если же таких вершин нет, то наша сеть имеет вид длинного горизонтального отрезка (для определенности рассматриваем горизонтальный) с несколькими короткими вертикальными ребрами (см. рис. 8). Внутренние вершины сети, лежащие ближе всего к краям горизонтального отрезка, называются концевыми вершинами. Введем два класса вертикальных ребер: ребра, находящиеся в верхней полуплоскости относительно горизонтального отрезка, будут лежать в классе U1; ребра, лежащие в нижней полуплоскости, будут принадлежать классу U2. Далее мы приведем здесь две леммы из [4], которые позволят лучше понять устройство таких сетей. Лемма 5.3. Класс U1 (также и класс U2) не содержит более двух последовательных ребер. 18 А. Г. БАННИКОВА, Д. П. ИЛЬЮТКО, И. М. НИКОНОВ РИС. 8. Итоговые сети РИС. 9. Пример расстановки нормирующих функционалов во внутренних вершинах Лемма 5.4. Каждую неконцевую вершину, инцидентную ребру из класса U1, можно объединить в пару со смежной с ней вершиной, инцидентной ребру из U2, так чтобы полученные пары не пересекались. Замечание 5.1. На самом деле в доказательстве леммы 5.4, см. [2, Лемма 6.17], для горизонтального отрезка строится разбиение внутренних вершин сети, за исключением возможно концевых вершин отрезка, на пары, каждая из которых содержит одну вершину из U1 и другую из U2. Все нормирующие функционалы вертикальных ребер определяются однозначно, и надо только задать нормирующие функционалы для горизонтальных ребер. Сделаем это таким образом: разобьем все вершины, за исключением, возможно, концевых вершин отрезка, на пары согласно лемме 5.4. Ребрам, соединяющим различные пары вершин, сопоставим нормирующие функционалы с координатами (±1, 0), тогда внутреннему ребру самой пары единственным образом сопоставляются два нормирующих функционала (по одному для каждого направления), дающие в сумме по ребру ноль, так же, как и в сумме по ребрам, инцидентным вершине. Эти нормирующие функционалы будут иметь координаты (±1, ±1). Нормирующие функционалы для ребер, инцидентных концевым вершинам, определяются в соответствии с выбором функционалов в вершинах, соседних с концевыми (см. рис. 9). 2. Случай λ ⊗= 2, 3, 4, 6. Опишем структуру экстремальных сетей на λ-нормированной плоскости, λ ⊗= 2, 3, 4, 6. ДЛИНА ЭКСТРЕМАЛЬНОЙ СЕТИ В НОРМИРОВАННОМ ПРОСТРАНСТВЕ: ФОРМУЛА МАКСВЕЛЛА 19 Определение 5.1. Пусть Γ - произвольная погруженная сеть и γ - некоторое ребро сети Γ, ориентированное одним из двух возможных способов. Если направление этого ребра приходит во внутреннюю точку стороны [μi, μi+1] 2λ-угольника Σ, то замыканием направления ребра γ назовем отрезок [μi, μi+1], а если направление приходит в вершину μi, то замыканием направления ребра γ назовем точку μi. В первом случае назовем ребро неточечным, во втором - точечным. Замыкание направления ребра γ обозначим как (γ). Определение 5.2. Для любых подмножеств A и B из 2λ-угольника Σ обозначим через α(A, B) точную нижнюю грань углов между радиус-векторами точек x ∈ A и y ∈ B. Если γ1 и γ2 - два смежных ребра, то в выражении α( (γ1), (γ2)) под замыканиями (γi) будем понимать замыкания для ребер γi, i = 1, 2, ориентированных от их общей вершины. Определение 5.3. Пусть γ1 и γ2 - произвольные смежные ребра сети Γ, i = 1, 2. Тогда пара (γ1, γ2) имеет погрешность k, и будем писать fall(γ1, γ2) = k, если α (γ1), (γ2) = 2π kπ 3 - 3λ . Определение 5.4. Рассмотрим произвольную пару (γ, γ±) смежных ребер, ориентированных от их общей вершины. Определим знак δ(γ, γ±) этой пары следующим образом: 1. для линейно независимых ребер γ и γ± положим δ(γ, γ±) = 1, если базис (γ, γ±) положительно ориентирован на R2, и δ(γ, γ±) = -1 в противном случае; 2. для линейно зависимых ребер γ и γ± положим δ(γ, γ±) = 1. Определим для пары (γ, γ±) ориентированную погрешность fall0(γ, γ±), положив fall0(γ, γ±) = δ(γ, γ±)fall(γ, γ±). Определение 5.5. Путь P называется правильно повернутым, если все внутренние вершины пути P, граничные в сети Γ, имеют одинаковый знак. Ориентация правильно повернутого пути P называется канонической, если знак каждой внутренней вершины пути P, граничной в сети Γ, положителен. Ориентированная погрешность определяется как fall0(P ) = max j1,jn / n-2 1 fall0(γj1 , γ2)+ '\" fall0(γi, γi+1)+ fall0(γn i=2 \ n - 1, γjn ) , где ∂ (γq ) = {γ1, γ2}, q = 1 или n, - граница подмножества (γq ) окружности Σ. Пусть Π - q q множество канонически ориентированных путей в Γ, все внутренние ребра которых точечны. Положим Fall0(Γ) = max fall0(P ). P ∈Π Для λ-нормированных плоскостей имеется следующий критерий экстремальности. Теорема 5.1 (см. [6-9]). Произвольная сеть Γ: G → R2 на λ-нормированной плоскости, λ ⊗= 2, 3, 4, 6, экстремальна тогда и только тогда, когда Fall0(Γ) 3. Покажем, что для экстремальной сети можно выбрать нормирующие функционалы граничных ребер явно. Из теоремы 5.1 следует, что для бинарной сети существуют такие ориентации ее ребер, что все они удовлетворяют условию локальной минимальности, т. е. мы можем разбить все ребра на три класса так, что ориентации ребер первого класса приходят в одну и ту же вершину 2λ-угольника, ориентации ребер второго класса приходят в одну и ту же вершину 2λугольника, а ориентации ребер третьего класса приходят на одну и ту же замкнутую сторону 2λ-угольника, причем погрешность между данными направлениями меньше 3. Следовательно, мы можем выбрать три нормирующих функционала для данных направлений, сумма которых равна нулю. Таким образом, для каждого ребра мы выбрали по одному нормирующему функционалу. Второй функционал для ребра - это противоположный первому. Мы имеем три, с точностью до знака, нормирующих функционала. Для каждого направления граничного ребра берем соответствующий ему.

Об авторах

А. Г. Банникова

МГУ имени М. В. Ломоносова

Email: jozhick@gmail.com

Д. П. Ильютко

МГУ имени М. В. Ломоносова ; ЯрГУ им. П. Г. Демидова

Email: ilyutko@yandex.ru

И. М. Никонов

МГУ имени М. В. Ломоносова ; ЯрГУ им. П. Г. Демидова

Email: nikonov@mech.math.msu.su

Список литературы