Связь вида нормы и геометрии минимальных сетей (1104796), страница 2
Текст из файла (страница 2)
А. Тужилину за постановку задачи, поддержку, внимание к работе и конструктивные замечания, А. О. Осиненко и З. Н. Овсянникову запродуктивные обсуждения и совместную работу, а также всем участникам и докладчикам семинара «Оптимальные сети» за внимание и полезные предложения.81Различимость нормированных пространств поустройству кратчайших и по точкам Ферма1.1Необходимые определенияПусть X — нормированное пространство, γ : [a, b] → X — некоторая непрерывнаякривая. Кривая γ называется измеримой, если существует предел `(γ) длин ломаных, вписанных в эту кривую, при стремящемся к 0 диаметру разбиения отрезка[a, b] прообразами вершин ломаных.
Число `(γ) называется в этом случае длинойкривой γ.Точкой Ферма трех точек A, B, C в метрическом пространстве (Y, ρ) называетсяточка T ∈ Y , минимизирующая сумму ρ(A, T )+ρ(B, T )+ρ(C, T ). В зависимости отметрического пространства, точка Ферма может не существовать или быть неединственной.Норма в нормированном пространстве называется строго выпуклой, если единичный шар в этой норме является строго выпуклым множеством.Напомним, что банахово пространство — полное нормированное векторноепространство, а гильбертово пространство — банахово пространство, норма которого порождена положительно определенным скалярным произведением.Банахово пространство X называется рефлексивным, если оно совпадает со своим вторым сопряженным пространством X ∗∗ при каноническом вложении.Для удобства, будем иногда называть норму на n-мерном пространстве n-мернойнормой.1.2Различимость нормированных пространств по устройству кратчайшихВ любом нормированном пространстве выполнено неравенство треугольника, поэтому прямолинейный отрезок между двумя точками всегда будет (возможно, не9единственной) кратчайшей между данными двумя точками.Две нормы на векторном пространстве будем называть неразличимыми по устройству кратчайших, если для любых двух точек множества кратчайших между ними в первой и второй норме совпадают.Как уже упоминалось во введении, для любых двух точек в любой строго выпуклой норме существует лишь одна кратчайшая, их соединяющая.
То есть, длялюбых двух точек вид кратчайшей определен (это отрезок) и не зависит от нормы(при условии ее строгой выпуклости), а значит, все строго выпуклые нормы нельзя различить по виду кратчайших. Но для норм, заданных центрально симметричными выпуклыми многогранниками произвольной размерности, все же можнополучить некоторую классификацию по видам кратчайших.Будем называть норму многогранной, если ее единичная сфера является многогранником.
Обозначим единичную сферу некоторой многогранной нормы n-мерногопространства N через Ω. Рассмотрим относительные внутренности всех граней Ωвсех размерностей. Заметим, что они образуют разбиение Ω. Это означает, что конусы с исключенной вершиной в 0 и основаниями — относительными внутренноe Теперь, длястями граней Ω образуют разбиение N \{0}, обозначим разбиение за Ω.e которому принадлежиткаждой точки P ∈ N \ {0} обозначим за OGP конус из Ω,открытый луч (OP ) с началом в O (для удобства, будем обозначать 0 пространства N за O при его рассмотрении как точки); за GP обозначим относительнуювнутренность грани, являющуюся основанием конуса OGP .Утверждение 1.1 Пусть N — нормированное пространство размерности n смногогранной нормой.
Тогда для любого P ∈ Ω измеримая кривая γ : [0, 1] →N, γ(0) = O, γ(1) = P является кратчайшей между O и P тогда и только тогда,когда для любых a, b таких, что a < b, a, b ∈ [0, 1], вектор γ(a)γ(b) принадлежитOGP .Доказательство. (⇐). Пусть T — любое разбиение отрезка [0, 1], заданное последовательностью {ti }mi=0 : t0 = 0, tm = 1, ∀i, j : 0 ≤ i ≤ j ≤ m, ti ≤ tj . Обозначим10диаметр разбиения T за s(T ). Спроецируем все векторы vi := γ(ti )γ(ti+1 ) на векторv := OP параллельно любой гиперплоскости π, являющейся опорной к сфере Ω иTтакой, что GP = Ω π, обозначим оператор проекции за A. Заметим, что A неменяет норму векторов, параллельных какому-либо вектору из OGP , и уменьшаетнорму остальных.
Поскольку ∀i ∈ [0, m − 1] вектор vi ∈ OGP , то kvi k = kAvi k. ЭтоmmPPозначает, что длина кривой `(γ) = limkvi k = limkAvi k = kOP k, что иs(T )→0 i=0s(T )→0 i=0требовалось доказать.(⇒) Докажем от противного. Пусть γ — кратчайшая кривая между O и P ,γ(0) = O, γ(1) = P . Пусть ∃a, b ∈ [0, 1] : a < b, γ(a)γ(b) 6∈ OGP . Покажем в этомслучае, что длина кривой γ больше, чем kOP k. Действительно, длина γ не меньшедлины ломаной Oγ(a)γ(b)P , которая равна kOγ(a)k + kγ(a)γ(b)k + kγ(b)P k. Попредположению, γ(a)γ(b) 6∈ OGP . Возможны два варианта:1) γ(b)γ(a) ∈ OGP . Тогда длина ломаной больше либо равна, чем kOP k + 2 ·kγ(a)γ(b)k = kOP k + 2 · kA γ(a)γ(b) k > kOP k (поскольку в этом случае, есливвести ориентацию на прямой OP«O левее P » , то проекция A(γ(b)) окажетсялевее, чем A(γ(a)))2) γ(b)γ(a) 6∈ OGP .
Тогда длина ломаной больше, чем kA Oγ(a) k+kA γ(a)γ(b) k+kA γ(b)P k ≥ kOP k, противоречие.Критерий 1.1 Две многогранные нормы k · k1 и k · k2 на линейном n-мерном пространстве N неразличимы по устройству кратчайших ⇔ у этих двух норм совe1 и Ωe 2 на конусы.падают разбиения ΩДоказательство. (⇐).
По утверждению 1.1, кратчайшие в нормах k · k1 и k · k2совпадают.(⇒) Докажем от противного. Пусть нормы k · k1 и k · k2 неразличимы, но уe1 и Ωe 2 . Это означает, что найдется такаяних не совпадают разбиения на конусы Ωточка P ∈ N \{O}, что OG1P 6= OG2P . Без ограничения общности можно считать,что ∃v1 ∈ OG1P , v1 6∈ OG2P .
Построим кривую, являющуюся кратчайшей в k · k1 ине являющуюся кратчайшей в k · k2 .11Рассмотрим вектор OP − εv1 . OG1P — относительно открытый конус, поэтомунайдется ε > 0 : OP − εv1 ∈ OG1P . Обозначим точку P − εv1 за L. Тогда длиналоманой OLP в k · k1 равна kOP k1 , и OLP — кратчайшая. Вместе с тем, v1 6∈ OG2P ,и по утверждению 1.1 ломаная OLP не является кратчайшей кривой между O и P ,поскольку ее звено LP = εv1 не принадлежит конусу OG2P ; значит, длина ломанойOLP в норме k · k2 больше kOP k2 , получаем противоречие.1.3Различимость нормированных пространств по местоположению точек ФермаПо устройству кратчайших отличить евклидову норму от остальных строго выпуклых норм невозможно.
Оказывается, для этих целей полезно рассмотреть обобщение кратчайших кривых между двумя точками, а именно — кратчайшие сети натрех точках, «тройники» с разветвлением в точке Ферма этих трех точек.Две нормы на векторном пространстве будем называть F3 -неразличимыми, если для любых трех точек множества их точек Ферма в первой и второй нормесовпадают.Теорема 1.1 Пусть дано пространство R2 с евклидовой нормой. Тогда для любойстрого выпуклой нормы, единичная окружность которой симметрична относительно поворота на π3 , верно, что эта норма и евклидова — F3 -неразличимы.Прежде чем перейти к доказательству теоремы 1.1, разберем необходимые дляэтого леммы.Лемма 1.1 Пусть в векторной плоскости с заданной нормой заданы четыре попарно несовпадающие точки {u, v, w} и t. Лучи с началом в t и направленные к{u, v, w} обозначим, соответственно, через {Rtu , Rtv , Rtw }.
Тогда t — точка Ферма для {u, v, w}, если и только если t — точка Ферма для {ũ, ṽ, w̃}, где {ũ, ṽ, w̃} —любые точки на лучах {Rtu , Rtv , Rtw }, соответственно.12Доказательство. Заметим сначала, что утверждение справедливо для более узкого класса троек точек, а именно {ũ, ṽ, w̃}, полученные из данной тройки {u, v, w}при помощи гомотетии с неотрицательным коэффициентом с центром в t (поскольку точка Ферма образов тройки точек при гомотетии будет образом точки Ферма изначальной тройки точек).
Теперь, пусть есть две тройки точек {u1 , v1 , w1 }и {u2 , v2 , w2 } такие, что для первой тройки t является точкой Ферма, а для второй — нет. Тогда для второй тройки проведем сжимающую гомотетию с центромt так, чтобы образы точек {u2 , v2 , w2 } при гомотетии оказались (назовем их, соответственно, {u02 , v20 , w20 }) , соответственно, на отрезках tu1 , tv1 и tw1 . Заметим, чтоточка t не является точкой Ферма для тройки {u02 , v20 , w20 }, (назовем их точку Ферма t0 ); поэтому сеть из отрезков {tu02 , tv20 , tw20 } между точками {u02 , v20 , w20 } заменимна сеть из отрезков {t0 u02 , t0 v20 , t0 w20 }, при этом сеть для {u02 , v20 , w20 } стала короче,а значит, что и для {u1 , v1 , w1 } сеть, состоящая из отрезков {u1 u02 , v1 v20 , w1 w20 } и{t0 u02 , t0 v20 , t0 w20 }, окажется короче сети из отрезков {tu1 , tv1 , tw1 }.
По неравенствутреугольника имеемku1 u02 k + kv1 v20 k + kw1 w20 k + kt0 u02 k + kt0 v20 k + kt0 w20 k > kt0 u1 k + kt0 v1 k + kt0 w1 k,противоречие.Аналогичными рассуждениями можно получить следующий результат в вырожденном случае:Лемма 1.2 Пусть в векторной плоскости с заданной нормой заданы три попарно несовпадающие точки {u, v, w} и t = u. Также, лучи с началом в t и направленные на {v, w} назовем, соответственно, через {Rtv , Rtw }. Тогда t — точка Фермадля {u, v, w}, если и только если t — точка Ферма для {u, ṽ, w̃}, где {ṽ, w̃}— любыеточки на лучах {Rtv , Rtw } соответственно.Лемма 1.3 Точка Ферма t треугольника uvw лежит внутри или на границе этого треугольника (в случае двумерного пространства).13Доказательство. Пусть точка t лежит вне треугольника.
Тогда один из лучейRtu , Rtv , Rtw пересекает относительную внутренность одной из сторон треугольника. Без ограничения общности будем считать, что луч Rtv пересекает сторонуuw в точке ṽ. Тогда по лемме 1.1 точка t является точкой Ферма вырожденноготреугольника uṽw, что невозможно.Лемма 1.4 В нормированном пространстве со строго выпуклой нормой k · kточка Ферма существует и единственна для любых трех точек.Данная лемма следует из теоремы 3.22 работы [10], ниже приведем элементарноедоказательство.Доказательство. Докажем от противного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
