Задача об оптимальном соединении в пространствах компактов (1102650), страница 4
Текст из файла (страница 4)
Естественным способом оценки может быть ограничение на количество точек в подмножествах.Для произвольного натурального > 1Cуботношением Штейнера пространства степени называетсявеличинаОпределение 1.29.15{︂ssr () = inf}︂mf( )| — конечное подмножество мощности .smt( )Отношением Штейнера-Громова пространства степени называется величина{︂sgr () = inf}︂mf( )| — конечное подмножество мощности .mst( )Отношением Штейнера пространства степени называется величина{︂sr () = inf}︂smt( )| — конечное подмножество мощности .mst( )Попытки найти такого рода отношения неоднократно предпринималисьдля евклидовой плоскости.Так, уже в [5] было показано, что sr3 (R2 ) =√√3322 , а утверждение sr4 (R ) = 2 √было доказано лишь через 10 лет в [6].Далее, утверждение sr (R2 ) = 23 было доказано для = 5 в [7], для = 6 в [8], для = 7 в [9] и, наконец, для = 8 в [10].Для суботношения Штейнера евклидовой плоскостиподобные утвер√ждения былиполучены в [11] (ssr4 (R2 ) = 23 ) и в [Ssr5] (ssr5 (R2 ) ≤√0, 8562...
< 23 ).Более общие утверждения, касающиеся произвольных метрическихпространств, были получены в [12]. Необходимая нам часть может бытьсуммирована в следующем утверждении:Для любого метрического пространства и натурального > 2 выполнены следующие неравенства:1) ssr () ≥ sgr () ≥ 2(−1)2) sr () ≥ sgr () ≥ 2(−1)Утверждение 1.30.162Различные отношения типа Штейнера дляпространстваℋ(R)В этом разделе построены различные примеры, показывающие, что дляпространства ℋ(R ) достигаются минимально возможные значения всехрассмотренных отношений и суботношений. Все рассмотренные примерыприведены для размерности = 1, но обобщаются на пространства больших размерностей естественным вложением. Все примеры были опубликованы в [GHSub].2.1Определения и предварительные результатыОсновным приемом, используемым в данном разделе, будет перенос задачи в пространство большей размерности ℋ(R ) . Здесь мы определимего и найдем его основные свойства.Под пространством ℋ(R ) будем понимать прямуюсумму пространств с метрикой максимума, а именно:Определение 2.1.ℋ(R ) = {(1 , .
. . , )| ∈ ℋ(R )},при этом ((1 , . . . , ), (1 , . . . , )) = max ( , ).=1,...,Пусть = {1 , . . . , } ⊂ ℋ(R ) — конечное ограниченное множество элементов, при этом = (1 , . . . , ). Тогда существует изометрическое отображение : → ℋ(R ) такое, чтоsmt() = smt(()).Лемма 2.2.Доказательство.
Выбрав произвольный индекс , можно рассматривать(1 , . . . , ) как набор компактов в R , при этом заведомо существуетдвижение : R → R , которое переводит все внутрь любого выбранного нами шара с диаметром 2 (). Так как это движение, торасстояния Хаусдорфа между компактами сохраняются. Выберем шары так, что расстояние между любыми двумя шарами не меньше100 (). Получили отображение : ℋ(R ) → ℋ(R ) такое, что⋃︀ ((1 , .
. . , )) = ( ).=1Покажем, что отображение сжимающее. Рассмотрим два элемента = (1 , . . . , ) и = (1 , . . . , ) из ℋ(R ) . Возьмем произвольную точку из образа (), она принадлежит одному из образов ( ),пусть ∈ ( ). Заметим что расстояние (, ()) (в обычном, нехаусдорфовом смысле), равно min (, ( )) ≤ (, ( )), значит,(, ()) ≤ ( ( ), ( )) ≤ (, ).17Следовательно, для любой точки ∈ () верно (, ()) ≤ (, ).Аналогичное утверждение верно для любой точки из (). Тогда( (), ()) = max( sup (, ()), sup (, ())) ≤ (, ).∈ ()∈ ()Будем обозначать шар с тем же центром, что и , но диаметром3 ().
Если ( ) ⊂ и ( ) ⊂ , а также (, ) < 2 (),то для любой точки = () ∈ ( ) верно (, ) = (, ( )) =(, ()), так как образы всех остальных компактов находятся слишкомдалеко. Тогда ( (), ()) = (, ).Тогда отображение сохраняет расстояния между любыми элементами из .Из того, что отображение сжимающее, очевидно, что ( ()) ≤(). Рассмотрим произвольное дерево Штейнера для ⋃︀ () с длиной, не большей (). Все его элементы лежат внутри и каждый элемент имеет хотя бы одну точку в каждом . Следовательно,отображение из образа кратчайшей сети в ℋ(R ) , такое, что () =−1( ∩ )) сохраняет расстояния между элементами(1−1 (1 ∩ ), .
. . , дерева Штейнера и переводит () в . Значит, () ≥ ( ()).Так как полученное отображение — изометрическое на , то оно сохраняет также длину минимального остовного дерева и вес минимального заполнения.Отношения и отношения степени Штейнера иШтейнера-Громова, а также суботношение и суботношения степени Штейнера равны для метрических пространств ℋ(R ) и ℋ(R ) припроизвольных натуральных и .Утверждение 2.3.Доказательство. Отображение, полученное в предыдущей лемме, показывает, что все рассматриваемые отношения для ℋ(R ) не больше такихже отношений для ℋ(R ) , так как для любого множества из ℋ(R )найдется множество из ℋ(R ) с таким же отношением рассматриваемоготипа.Аналогично, рассмотрев отображение : ℋ(R ) → ℋ(R ) такое, что () = (, {0}, {0}, .
. . , {0}), получим, что все отношения для ℋ(R ) небольше таких же отношений для ℋ(R ), и, следовательно, они равны.2.2Отношения Штейнера и Громова-ШтейнераИз предыдущего утверждения и утверждения 1.30 нетрудно вывести следующее утверждение:18Утверждение 2.4.sr (ℋ(R )) =2(−1) .Для произвольного натурального и > 1 верно. ТакимДоказательство.
Утверждение 1.30 говорит, что sr () ≥ 2(−1)образом, достаточно найти пример множества с отношением Штейнера,равным этому числу.Пусть > log2 () — натуральное число. Можно рассмотреть множество = { = (1 , . . . , ) ∈ ℋ(R ) | = {(0, 0, . . . , 0)} или ={(1, 0, 0, . . .
, 0)}}. Расстояния между любыми двумя элементами множества равны 1, а расстояние от любого элемента множества до точки = ({( 21 , 0, . . . , 0)}, {( 12 , 0, . . . , 0)}, . . . , {( 12 , 0, . . . , 0)}) ∈ ℋ(R ) равно12 . Следовательно, для любых элементов множества их отношениеШтейнера будет не больше121(−1)=2(−1) .Из того, что отношение Штейнера степени достигает теоретического минимума и утверждения 1.30 автоматически следует, что отношенияГромова-Штейнера (степени ) также минимальны.Для метрического пространства ℋ(R ) при произвольном натуральном выполнены следующие равенства:1) sr(ℋ(R )) = 21 ,2) sgr (ℋ(R )) = 2(−1)для произвольного > 1,3) sgr(ℋ(R )) = 12 .Теорема 2.5.2.3Cуботношение Штейнера степени 3 и 4В течение всего параграфа мы будем опираться на утверждение 1.30, аименно, на то, что ssr () ≥ 2(−1).Теорема 2.6.Суботношение Штейнера степени 3 для ℋ(R) равно34Доказательство.
Рассмотрим компакты 1 = {1, 4, 5}, 2 = {1, 2, 5} и3 = {1, 2, 3, 4, 5} из R. Расстояние между любыми двумя из них равно 1. Кратчайшая сеть может иметь единственную топологию звезды стремя лучами. Обозначим центральную вершину звезды за , а расстояния (, ) = . Это означает, в частности, что выполнены следующиеусловия: ⊂ 1 (1 ) ∪ 4 (1 ) ∪ 5 (1 ), ⊂ 1 (2 ) ∪ 2 (2 ) ∪ 5 (2 ), ⊂ 1 (3 ) ∪ 2 (3 ) ∪ 3 (3 ) ∪ 4 (3 ) ∪ 5 (3 ).Длина кратчайшей сети будет равна = 1 +2 +3 , вес минимальногозаполнения — 23 . Пусть < 2 (понятно, что ≤ 2, так как это длина19минимального остовного дерева).
Так как < 2, то + < 2 при ̸= . Значит, ∩ 3 (3 ) ∩ 2 (2 ) = ∅ (пересечение этого множества с1 (1 ) ∪ 4 (1 ) ∪ 5 (1 ) пусто) и ∩ 3 (3 ) ∩ 4 (1 ) = ∅ (пересечениеэтого множества с 1 (2 ) ∪ 2 (2 ) ∪ 5 (2 ) пусто). Тогда ∩ 3 (3 ) = ∅,и 3 ≥ (3, ) ≥ 2 − max(1 , 2 ), что противоречит предположению о том,что < 2. Значит, = 2 и суботношение Штейнера для будет равно34.Так как суботношение Штейнера для трехточечного множества неможет быть меньше 34 , то суботношение Штейнера степени 3 для ℋ(R)равно 34 .Этот пример естественным образом обобщается на случай компактов из пространства большейразмерности, при этом все рассуждения сохраняют верность.Одной из сложностей в определении длины минимального дерева Штейнера является нахождение топологии этого дерева.
С поРис. 3: Сверху вниз: 1 , 2 , 3мощью операции увеличения размерности мы сможем выбирать топологию рассматриваемого дерева произвольным образом.Пусть = {1 , . . . , } — множество компактов из R таких, что( , ) ≤ 1, при этом для каких-то и выполняется равенство ( , ) =1. Рассмотрим множество = {1 , . . . , } ∈ ℋ(R )! , построенное следующим образом: пусть 1 , . . . , ! — упорядоченный набор всех перестановок из элементов.
Тогда = (1 () , . . . , ! () ).Расстояние между элементами и равно 1 и длина минимальногоостовного дерева равна − 1.Пусть — некоторая перестановка из элементов. Тогда найдется перестановка 1 из ! элементов такая, что для функции : ℋ(R )! → ℋ(R )! , определяемой как ((1 , .
. . , ! )) = (1 (1) , . . . , 1 (!) ),верно равенствоЛемма 2.7. ( ) = ()Пусть — топология минимального дерева Штейнерадля множества и 1 — некоторое бинарное дерево с вершинами1 , . . . , , получающееся из заменой вершин на () . Тогда длинаминимального дерева Штейнера для множества не меньше длиныминимального дерева топологии 1 , затягивающего 1 , . . . , .Лемма 2.8.20Доказательство. Рассмотрим проекцию минимального дерева Штейнера для множества на ℋ(R )() . Получившаяся сеть будет затягивать1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
