Задача об оптимальном соединении в пространствах компактов (1102650), страница 5
Текст из файла (страница 5)
. , , при этом ее топология будет 1 , а длина каждого ребра будет не больше длины соответствующего ребра в исходном минимальномдереве Штейнера. Следовательно, длина исходной сети будет не меньшедлины ее проекции, а та, в свою очередь, не меньше длины минимальнойсети топологии 1 .Теорема 2.9.Суботношение Штейнера степени 4 для ℋ(R ) равно 32 .Доказательство. Рассмотрим компакты 1 = {1, 2, 3}, 2 = {1, 4, 5},3 = 2 и 4 = {1, 2, 5} из R (различных множеств получается три).Расстояние между любыми двумя из них, кроме 2 и 3 равно 1.
Рассмотрим множество ⊂ ℋ(R)4! , образованное таким же образом, как вутверждениях выше. Кратчайшая сеть может иметь единственную бинарную топологию с двумя внутренними точками. Рассмотрим такуюпроекцию этой сети на ℋ(R), что вершины 1 и 2 лежат на одних усахи вершины 3 и 4 лежат на одних усах, пусть при этом (() ) = . Обозначим внутренние вершины проекции за 1 и 2 , вершина 1 соединяетсяребрами с вершинами 1 и 2 . Пусть также () = 1 , () = 2 , здесь и – внутренние вершины исходного минимального дерева Штейнера.Обозначим расстояния между точками как ((1) , ) = 1 , ((2) , ) = 2 ,((3) , ) = 3 , ((4) , ) = 4 , (, ) = .
Понятно, что + ≥ 1 при ̸= .Длина кратчайшей сети для множества будет равна = 1 + 2 +3 + 4 + , вес минимального заполнения — 2. Пусть < 3 (понятно, что ≤ 3, так как это длина минимального остовного дерева для множества ). Тогда 1 + 2 < 3 − 3 − 4 − < 2. Аналогично, 3 + 4 < 2. Из леммы2.8 следует, что расстояния между точками на проекции не больше расстояний между их прообразами. Это значит, что выполнены следующиеусловия (здесь первое условие следует непосредственно из определениярасстояния Хаусдорфа, а второе — из расстояния Хаусдорфа между 1и 2 ):1 ∩ 3 (1 ) ̸= ∅1 ⊂ 1 (2 ) ∪ 4 (2 ) ∪ 5 (2 ).Значит, так как 1 + 2 < 2, то 1 ∩ 3 (1 ) ∩ 4 (2 ) ̸= ∅. Выберем изэтого множества произвольную точку . Также верно, что 2 ⊂ 1 (4 ) ∪2 (4 )∪5 (4 ).
Несложно заметить, что расстояние от точки до 1 (4 )∪2 (4 ) ∪ 5 (4 ) не меньше min(2 − 1 − 4 , 2 − 2 − 4 ). Значит, ≥ (1 , 2 ) ≥ (, 2 ) ≥ (, 1 (4 )∪2 (4 )∪5 (4 )) ≥ min(2−1 −4 , 2−2 −4 ).21Тогда = 1 + 2 + 3 + 4 + ≥ 2 + min(2 + 3 , 1 + 3 ) ≥ 3, чтопротиворечит нашему предположению. Значит, = 3. СуботношениеШтейнера для при этом будет равно 23 .Так как суботношение Штейнера для четырехточечного множестване может быть меньше 34 , то суботношение Штейнера типа 4 для ℋ(R)равно 23 .Этот пример непосредственно обобщается на случай ℋ(R ), все рассуждения сохраняют силу, и только их запись становится более громоздкой.К сожалению, так и не удалосьдоказать гипотезу, что ssr (ℋ(R )) =Гипотеза 2.10.ssr (ℋ(R )) =2(−1) .2(−1)Рис.
4: Сверху вниз: 1 , 2 , 3 , 4223Суботношения Штейнера типа 4 для5 дляR3иR2Как было упомянуто ранее, суботношение Штейнера для евклидовойплоскости для трех- и четырех-точечных множеств было получено в [11]и оказалось равно 23 , а отношение Громова-Штейнера, соответственно,34 . Как следствие результата была выдвинута гипотеза о том, что и дляслучая произвольного количества точек эти соотношения сохранятся. Ксожалению, это оказалось неверно, был получен пример пятиточечногомножества с меньшим суботношением Штейнера.Тем не менее, гипотеза оказалась верной для выпуклых пятиточечных множеств, что было показано, как и пример невыпуклого множества, в [Ssr5]. В трехмерном евклидовом пространстве любое трехточечное множество лежит в одной плоскости вместе с кратчайшей сетью и,следовательно, суботношениеШтейнера равно таковому в случае плос√3кости, а именно, 2 .
Четырехточечное суботношение Штейнера также√√было получено в [Ssr5] и равно 17 (2 3 + 5).3.1Пятиточечное суботношение Штейнера для плоскости3.1.1Общий случайРассмотрим пятиточечное множество, образованное вершинами двух одинаковых правильных треугольников, пересекающихся по одной вершинеи повернутых таким образом, что две их стороны находятся под углом2 (см. рисунок 5). Очевидно, что, если принять длину стороны треугольников за 1, то длина минимального остовного дерева будет равна√ 4, а, √как следствие, кратчайшая сеть будет иметь длину не больше4 23 = 2 3. А. О.
Иванов и А. А. Тужилин написали программу на языке Wolfram Mathematica, которая находит минимальное заполнение и еговес для заданного конечного метрического пространства, перебирая всевозможные топологии минимального заполнения и решая задачу линейного программирования для каждой топологии. Найденный с ее помощью вес минимальногозаполнения данного пространства оказался равен√√отношение Громова-Штейнера2 + (1 + 3)/(2 2) < 3. Таким√образом,√данного множестваравно√√равно2+(1+ 3)/(2 2)√2 3Теорема 3.1.√<32 .2+(1+ 3)/(2 2)4< 34 , а суботношение ШтейнераЭто приводит нас к следующему утверждению:Для евклидовой плоскости выполнены следующие нера-венства:1) ssr5 (R2 ) ≤√13+√1+√ 34 6√<3223Рис. 5: Пример пятиточечного множествана плоскости, для которого√3суботношение Штейнера меньше 22) sgr5 (R ) ≤23.1.212+√1+√ 38 2<34Выпуклый случайДля рассмотрения выпуклого случая нам понадобится определение бабочки.
Подробнее про описание обходов пятиточечного множества можнопрочитать в [19]. Пусть имеется некоторый граф — цикл на пяти вершинах. Тогда бабочками для этого цикла будут называться такие циклы наэтих же вершинах, что они имеют с исходным циклом ровно два общихребра, которые не имеют общих вершин (см. рисунок 6). Нетрудно заметить, что каждому циклу соответствует ровно пять бабочек и каждаяиз них однозначно определяется одной вершиной, которая называетсяносик. Длиной бабочки назовем полусумму длин всех ее ребер.Пусть имеется цикл и отображение его вершин в евклидову плоскость.
Если образ цикла является выпуклым пятиуголь√ником (как на рисунке 6), то любая бабочка имеет длину не менее 23длины кратчайшей сети.Лемма 3.2.Доказательство. Рассмотрим произвольную бабочку выпуклого пятиугольника. Ее можно представить как объединение трех треугольников,сумма полупериметров которых равна длине бабочки. Для произвольного треугольника длина кратчайшей сети не больше, чем √23 его полупериметра.
Кратчайшие сети треугольников можно объединить в сеть, затягивающую вершины пятиугольника, при этом ее длина будет не больше √23 сумм их полупериметров, а, значит, длины бабочки (см. рисунок24Рис. 6: Исходный цикл (слева сверху) и пять его бабочекРис. 7: У выпуклого цикла все бабочки большиеРис. 8: Единственно возможная бинарная топология минимального заполнения на пяти вершинах25Рис. 9: Примеры бабочек, являющихся планарными обходами для всехвозможных бинарных графов с вершиной , лежащей не на усах и вложения, показывающие, что бабочки действительно являются планарными обходами.267).В [18] была предложена формула для веса минимального заполнения, которая основывается на понятии планарных мультиобходов.
Нампотребуется лишь упрощенная часть этой формулы. Обходом дерева будем называть циклическую последовательность вершин дерева. Длинойобхода назовем полусумму расстояний между соседними относительнообхода вершинами. Обход будем называть планарным, если существуетвложение этого дерева в плоскость такое, что можно соединить вершины дерева в порядке обхода жордановой кривой без самопересечений, непересекающей дерево. Из формулы Еремина веса минимального заполнения непосредственно следует следующее утверждение.([18]).
Вес минимального параметрического заполнения не меньше максимума длин его планарных обходов.Утверждение 3.3Суботношение Штейнерадля вершин выпуклого пяти√3угольника на плоскости не меньше 2 .Теорема 3.4.Доказательство. Для пяти точек существует 15 различных бинарныхдеревьев, способных быть типами минимального параметрического заполнения, но все они эквивалентны с точностью до перестановки вершин(см. рисунок 8).В ситуации с выпуклым пятиугольником можно фиксировать вершину, расположенную не на усах. Тогда нужно рассмотреть всего 3 случая.Как видно из рисунка 9, в каждом из этих случаев существует обход,планарный для выбранного графа и являющийся бабочкой для пятиугольника.По лемме 3.2 эти обходы имеют полупериметр не меньше,√чем 23 длины кратчайшей сети, следовательно, для каждого √типа сетивес минимального параметрического заполнения не меньше 23 длиныкратчайшей сети, откуда непосредственно следует утверждение.3.2Четырехточечное суботношение Штейнера длятрехмерного пространстваРассмотрим произвольное конечное множество точек метрического пространства и бинарное дерево , в котором вершинами степени один будут эти точки.
Тогда параметрическим суботношением Штейнера типа G для этого множества будем называть отношение веса минимального параметрического заполнения типа к длинеминимального дерева с топологией (оно будет также локально минимальным), будем обозначать данное отношение ssrp ( ). Для некоторого семейства конечных подмножеств метрического пространстваОпределение 3.5.27параметрическим суботношением Штейнера типа G будем называтьвеличину ssrp () = inf ssrp ( ). ∈Рассмотрим четыре точки , , , ∈ R3 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
