Задача об оптимальном соединении в пространствах компактов (1102650), страница 6
Текст из файла (страница 6)
Существует три топологии бинарных деревьев с вершинами степени 1 в этих точках, которыеотличаются расположением усов. Выберем одну из них: пусть в бинарномдереве вершины и лежат на одних усах, а и , соответственно,на других. Семейство упорядоченных четырехточечных подмножеств таких, что для них существует минимальное заполнение топологии будемобозначать за .Для каждого множества из его параметрическое суботношение небольше его суботношения Штейнера.
Значит, ssrp ( ) ≤ ssr4 ( ). Приэтом суботношение Штейнера степени 4 достигает минимума на каком-точетырехточечном множестве, без ограничения общности можно считать,что — топология минимального заполнения на этом множестве, отсюдаследует, что ssrp ( ) ≤ ssr4 (R3 ).Семейство естественным образом разбивается на три: семействочетырехточечных множеств таких, что внутреннее ребро минимальнойпараметрической сети топологии вырождено (такое семейство будемобозначать 1 ), семейство четырехточечных множеств таких, что внутренне ребро минимальной параметрической сети топологии невырождено, но имеются другие вырожденные ребра (такое семейство будемобозначать 2 ) и семейство четырехточечных множеств таких, что вминимальной параметрической сети топологии нет вырожденных ребер (такое семейство будем обозначать 3 ).Семейство четырехточечных подмножеств R3 таких, что локальноминимальная сеть топологии невырождена, будем обозначать , аего замыкание — .
Значит, 3 = ∩ .Для доказательства следующих лемм нам понадобится утверждениео весе минимального заполнения для четырехточечного множества из[14]:Вес минимального параметрического заполнения,затягивающего точки , , , так, что точки и находятся на одних усах ( и , соответственно, тоже) равенУтверждение 3.6.mpf =)︀1 (︀((, ) + (, )) + max((, ) + (, ), (, ) + (, ))2Рассмотрим семейство четырехточечных множеств() = {1 (), 2 (), 3 (), 4 ()}, где () — непрерывные кривые. Можно представить вес минимального параметрического заполнения типа, как функцию от параметра . Если все () представляют собойотрезки, то функция mpf () выпукла.Лемма 3.7.28Доказательство. Расстояние между любыми двумя точками при такихусловиях выпукло как функция от параметра . Сумма и максимум выпуклых функций — это выпуклая функция, следовательно, функция изутверждения 3.6 выпукла.√ √1Лемма 3.8.
Параметрическое суботношение ssrp ( ) = (2 3+ 5).7При этом минимум достигается на четырехточечном множестве таком, что ∈ 3 .Доказательство. Пусть инфинум параметрического суботношения длячетырехточечных множеств достигается на множестве = {, , , }.Без ограничения общности можно считать, что внутреннее ребро минимальной параметрической сети имеет длину 1, длины ребер, инцидентных , , , обозначим как , , , .
Угол между плоскостями усовобозначим за ≤ 2 .Рассмотрим движение точек (), (), (), () такое, что (0) =, (0) = , . . ., причем точки движутся вдоль инцидентных ребер минимальной параметрической сети так, что длины ребер, лежащих на одних усах, «меняются местами»: () = + (1 − ), () = (1 − ) + ,() = + (1 − ), () = (1 − ) + . При этом длина минимальнойпараметрической сети не изменяется, а вес минимального заполнения —выпуклая функция от параметра по лемме 3.7, симметричная относительно точки = 21 , так как ((), ()) = ((1 − ), (1 − )) и т.п.Значит, без ограничения общности можно считать, что = , = .Рассмотрев аналогичное движение вида () = () = + (1 − ),() = () = + (1 − ), видим, что без ограничения общности можноположить = = = .Получили семейство четырехточечных множеств задающихся двумяпараметрами: — длина ребер при висячих вершинах и — угол междуплоскостями усов (напомним, что длину внутреннего ребра мы принялиравной единице).
Длина минимального параметрического дерева не зависит от параметра , а вес минимального параметрического заполненияравен√√︂3 + max(33( + 1)2 + 2 (1 ± cos )2 + 2 sin2 ) =4√︂4√333 + ( + 1)2 + 2 + 2 | cos |22.и достигает минимума при cos = 0, то есть, = 2 .Осталась лишь одна неизвестная величина, а именно, длина граничного ребра . Длина минимальной параметрической сети и вес минимального параметрического заполнения выражаются как функции от :29√√︁mpn () = 4 + 1, и mpf () = 3 + 32 2 + ( + 1)2 . Задача поискаминимального значения отношения при положительных решается поиском√нуля у производной, при этом в точке минимума√√ значение равно1215), а значение отношения равно 7 (2 3 + 5).7 (1 +√√Из леммы следует, что ssrp (3 ) = 17 (2 3 + 5).У множества из предыдущей леммы кратчайшая сетьимеет топологию .Лемма 3.9.Доказательство.
Вследствие симметрии множества кратчайшая сетьможет иметь две различные топологии: топология с усами и и топология с усами и (третий случай идентичен второму). Минимальная параметрическая сеть и ее длина известны из предыдущегоутверждения. Длина минимальной параметрической сети не меньше суммы √︁расстояний между элементами усов. Мы можем его найти, оно равно√2 * ( 3 + 1)2 + 12 2 = 7, 101.... При этом длина минимальной параметрической сети топологии равна 4 + 1 = 6, 569... < 7, 101.... Такимобразом, минимальная параметрическая сеть типа является кратчайшей сетью.Cледующая лемма непосредственно следует из теоремы косинусов.Пусть в треугольнике стороны имеют длины , и ,причемугол напротив стороны длины не меньше 120∘ , тогда ≥√32 ( + ).Лемма 3.10.1Лемма 3.11.
ssrp ( )√≥32 .Доказательство. Без ограничения общности можно считать, что минимальная параметрическая сеть топологии для устроена следующимобразом: есть вершина , от которой идут ребра к вершинам , , , длинами , , , соответственно. При этом углы между отрезками и , а также и не меньше 120∘ , иначе сеть не будет локально кратчайшей (утверждение 1.18).
Так√как mpf () ≥ ( + ),3топопредыдущейлеммеmpf()≥( + + + ) =2√32 mpn ().Аналогично лемме 3.8 доказывается следующая лемма.Лемма 3.12.Минимум inf 2 ssrp () не меньше минимума inf ssrp ()∈∈30Доказательство. Пусть минимум достигается на каком-то четырехточечном множестве ∈ 2 ().Если в минимальной параметрической сети вырождены оба ребра накаких-либо усах, то получается плоская конфигурация, при этом минимальная параметрическая сеть автоматически становится минимальной,а минимальное параметрическое заполнение — минимальным заполнением.
При этом мы знаем,√ что для трех точек на плоскости суботношениеШтейнера не меньше 23 > inf ssrp ().∈Пусть в минимальной параметрической сети вырождены два ребра наразных усах, без ограничения общности можно считать, что ребра, инцидентные вершинам и вырождены, а ребра, инцидентные вершинам и невырождены, углы между ними и вырожденным ребром не меньше 120 градусов. Если вращать ребро, инцидентное вершине , сохраняяего длину и угол с внутренним ребром, то меняется только длина ,без ограничения общности можем выбрать так, что она минимальна, это происходит, когда все четыре точки лежат в одной плоскости.Теперь, если уменьшать угол между ребром, инцидентным и внутренним ребром, то длина минимального параметрического заполнения небудет изменяться, а расстояния между точками не будут увеличиваться.Таким образом, можно считать, что в углы между ребрами и ивнутренним ребром равны 120 градусам.
Тогда ∈ ().Пусть невырождено ровно одно ребро, инцидентное вершине . Пустьвершины и лежат по одну сторону плоскости, проходящей черезвнутреннее ребро перпендикулярно плоскости усов. Обозначим () =( + + + )/mpn () ≤ ssrp () = ssrp (2 ). Пусть —вершина минимальной параметрической сети типа для множества .При повороте ребра вокруг внутреннего ребра с сохранением угламежду ними из расстояний, входящих в () изменится только .Повернем ребро таким образом, что плоскость станет перпендикулярна плоскости .
Если уменьшать угол между ребрами и , пока он не станет равным 120 градусам, то все расстояния,входящие в () не увеличатся. В результате этих операций получилинабор = {, , ′ , } ∈ , при этом ( ) ≤ () ≤ ssrp (2 ). Теперь мы можем добавить ребро ′ ненулевой длины и получить набор = {, , ′ , ′ }. Пусть длина ребер , , равна , , соответственно. Можно рассмотреть семейство наборов () = {(), (), ′ (), ′ ()},отличающихся длинами граничных ребер, равных + (1 − ), +(1 − ), (1 − ), соответственно. Можно также рассмотреть функцию () = (()).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
