Задача об оптимальном соединении в пространствах компактов (1102650), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

. . , } и = {1 , . . . , }. Рассмотрим отображение : →), а ( ) = (1 , . . . , 2R2 , обозначим: ( ) = (1 , . . . , 2+1 ). Пусть2+12+122 = 0, = 0, = 1, = 0 при ̸= . Пусть √между вершина1 2+1= 23 , а если такогоми и в графе есть ребро, тогда 2 = 2 , 2+1ребра в графе нет, то 2= 1. Значит, если между и есть = 1, ребро, то ( ( ), ( )) =2∑︀∑︀3=14+14= , а если такого ребра нет, то( 34 + 14 ) + 1 + 1 = + 1 > . Получили пару=1,̸=√компактов () и (), расстояние Хаусдорфа между ними равно и, если для него произвести операции из предыдущего абзаца, получимисходный двудольный граф.Стоит отметить, что в утверждении ничего не сказано о минимальнойразмерности пространства R , из которого выбираются компакты, и в общем случае про его возможные значения ничего не известно. Например,в [1] утверждается, что в R2 нет пары компактов, между которыми былобы 57 кратчайших, а в R3 есть. Из этой переформулировки был выведенряд фактов, которые можно суммировать в следующем утверждении:( ( ), ( ))2 =Для любых двух компактов , ∈ ℋ(R ) количество кратчайших между ними не может равняться 19 [1] или 37 [4].Для любого натурального числа от 1 до 36 включительно (кроме 19)существуют натуральные и пары компактов , ∈ ℋ(R ) с такимколичеством кратчайших между ними [1].Утверждение 1.12.111.2Кратчайшие сети, минимальные заполнения, различные фундаментальные отношенияМетрическим пространством называется множество вместе с введенной числовой функцией : × → R+ , длякоторой выполняются следующие условия:1) (, ) = 0 ⇔ = ,2) (, ) = (, ),3) (, ) + (, ) ≥ (, ).Если выполняются только последние два условия, то пространствоназывается псевдометрическим.Определение 1.13.Пусть = (, ) — псевдометрическое пространство и — произвольный связный граф, — множество его вершин, а — множествоего ребер.

Сетью в , параметризованной графом или сетью типа назовем пару отображений, сопоставляющих каждой вершине графанекоторую точку, а каждому ребру — пару точек в , являющихся образами вершин ребра. Вершинами и ребрами сети Γ называются ограничения отображения Γ соответственно на вершины и ребра графа . Длинойребра Γ : → назовем расстояние между образами вершин, а длиной(Γ) сети Γ — сумму длин всех ее ребер. Будем называть сеть невырожденной, если в ней нет ребер длины ноль. Также в пространствахсо строго внутренней метрикой сетью будем называть образ невырожденной сети, в котором ребра заменяются на какие-либо кратчайшие,соединяющие образы вершин этих ребер.Будем говорить, что сеть Γ затягивает или соединяет множество , если — подмножество образа вершин сети.Число smt( ) = inf{(Γ)|Γ — сеть, соединяющая }назовем длиной кратчайшей сети.

Сеть такой длины существует не всегда, но если она существует, то называется кратчайшей сетью, соединяющей или минимальным деревом Штейнера для .Определение 1.14.Заметим, что достаточно искать кратчайшие сети среди деревьев, ане произвольных графов. Более, того, как показано, например, в [14],можно ограничиться еще более узким классом графов.Дерево называется бинарным, если все его вершиныимеют степень 1 и 3. Пара ребер, инцидентных вершинам степени 1 иодной и той же внутренней вершине, называется усами, вершины степени1 называются лежащими на одних усах.Определение 1.15.Для любого конечного множества , являющегося подмножеством метрического пространства, верно следующее равенство:Утверждение 1.16.12inf{(Γ)|Γ — сеть, соединяющая } =inf{(Γ)|Γ — сеть типа бинарного дерева, соединяющая }Сеть, Γ, соединяющая множество , называетсялокально кратчайшей, если для любой точки из образа сети существуетокрестность такая, что пересечение ∩ Γ будет конечным множеством, и если взять ограничение сети Γ на , то оно будет соответствовать образу некоторой кратчайшей сети, затягивающей ( ∩ ) ∪ ( ∩Γ).Определение 1.17.Любая кратчайшая сеть обязана быть локально кратчайшей, обратное не обязательно верно, как пример можно рассмотреть точки, лежащие на экваторе на сфере, соединенные большим кругом.

Для евклидовых пространств известен критерий того, что сеть является локальнократчайшей [5].Невырожденная сеть в евклидовом пространствеявляется локально кратчайшей тогда и только тогда, когда образы ребер являются отрезками, и углы между любыми двумя соприкасающимися отрезками не меньше 120 градусов.Утверждение 1.18.Сеть Γ называется остовной для множества ,если она затягивает и образ всех ее вершин лежит в .Определение 1.19.Минимальным остовным деревом для конечногомножества называется остовная сеть минимальной длины, ее длина называется длиной минимального остовного дерева и обозначаетсяmst( ).Определение 1.20.Такое дерево существует потому, что невырожденных остовных сетейконечное число.Отношением Штейнера для множества назыsmt( )вается отношение sr( ) = mst( ) . Отношением Штейнера для метрического пространства называется величинаОпределение 1.21.sr() = inf{sr( )|| −конечное подмножество , состоящее не менее, чем из двух элементов}.Заметим, что отношение Штейнера для множества не обязательнореализуется на какой-либо кратчайшей сети даже в случае полного пространства, так, в [15] был, в частности, приведен пример такого множества в банаховом пространстве.

Остается открытым вопрос, обязано ли13отношение Штейнера в пространстве достигаться на каком-либо конечном множестве. В [24] была выдвинута гипотеза, что этого не происходитдаже в трехмерном евклидовом пространстве.Очевидно, что отношение Штейнера не больше 1. В [12] показано,что если рассматривать отношения Штейнера для множеств из не бо, а отношение Штейнералее, чем точек, то они не меньше, чем 2(−1)произвольного метрического пространства не меньше 12 .Минимальное заполнение конечного метрического пространства, впервые введенное в [14], можно рассматривать с двух точек зрения: каквзвешенный граф с вершинами в метрическом пространстве и как минимум кратчайших сетей по всем возможным изометрическим вложениямконечного метрического пространства. По мере необходимости будем использовать как одну интерпретацию, так и другую.

Следующие определения взяты из [14].Граф вместе с функцией : → R из множества ребер графа в вещественные числа называется взвешенным, функция называется весом, ее значение на каком-либо ребре называетсявесом ребра. Для пути, или последовательности ребер, в графе весом пути называется сумма весов всех входящих в него ребер. Весом графаназывается сумма весов всех его ребер.Определение 1.22.Заполнением конечного псевдометрического пространства типа называется произвольный взвешенный граф снеотрицательными весами такой, что — подмножество множества еговершин и вес любого пути между элементами не меньше расстояниямежду ними.Определение 1.23.Заполнение конечного метрического пространства типа минимального веса называется минимальным параметрическим заполнением типа .

Граф называется типом заполнения.Заполнение пространства минимального веса называется минимальным заполнением. Его вес называется весом минимального заполненияи обозначается mf( ).Определение 1.24.В [14] было показано, что минимальное заполнение, то есть, заполнение минимального веса, существует для любого конечного метрическогопространства и что, как и в случае с минимальным деревом Штейнера, достаточно рассматривать минимум по заполнениям типа бинарногодерева.Минимальному заполнению можно дать альтернативное определение, показывающее его связь с минимальным деревом Штейнера:Пусть — конечное метрическое пространство.Тогда весом минимального заполнения назовем следующую величину:Определение 1.25.14mf( ) = inf{smt( ( ))| : → —изометрическое отображение пространства в произвольное конечное метрическое пространство }.Сеть (в пространстве, объемлющем M) такой минимальной длиныбудем называть минимальным заполнением.То есть, минимальное заполнение — это кратчайшая сеть, выбранная среди всех сетей изометричных отображений нашего пространства вкакое-либо объемлющее метрическое пространство.([14]).

Два вышеприведенных определения минимального заполнения эквивалентны в том смысле, что их веса одинаковы, а граф кратчайшей сети с весами – расстояниями между вершинами образует взвешенный граф минимального заполнения.Утверждение 1.26В [14] также было показано, что можно выбирать не среди всех вложений во все объемлющие метрические пространства, а рассмотреть лишьодно (!) фиксированное вложение в пространство ℓ∞ , где — мощностьисходного метрического пространства (координаты образа точки — расстояния до соответствующих точек в исходном метрическом пространстве). Более того, в [17] показано, что для любого пространства Линденштраусса (в частности, ℓ∞ ) кратчайшая сеть для любого конечногоподмножества совпадает с его минимальным заполнением.Отношением Громова-Штейнера пространства называется величина{︂}︂mf( )sgr() = inf| — конечное подмножество , # > 1 .mst( )Определение 1.27.СуботношениемШтейнера пространства на-}︁{︁mf( )зывается величина ssr() = inf smt( ) | — конечное подмножество .Определение 1.28.Поиск отношений Штейнера, Громова-Штейнера и особенно суботношения Штейнера — нетривиальная задача, которая пока не выполненадаже для евклидовой плоскости [13], поэтому имеет смысл попытатьсянайти некоторые оценки на эти величины.

Характеристики

Список файлов диссертации