Минимальные деревья Штейнера в пространстве метрических компактов (848704), страница 2
Текст из файла (страница 2)
Положим(x, y)(x′ , y ′ ) = α|xx′ | + β|yy ′ |.αОчевидно, полученная функция положительно определена и симметрична.Проверим неравенство треугольника. Имеем(x, y)(x′ , y ′ ) + (x′ , y ′ )(x′′ , y ′′ ) = α|xx′ | + β|yy ′ | + α|x′ x′′ | + β|y ′ y ′′ | ≥αα≥ α|xx′′ | + β|yy ′′ | = (x, y)(x′′ , y ′′ ) .αТаким образом, | · |α является метрикой на R при каждом 0 < α < 1, а приα = 0, 1 — псевдометрикой.Обозначим через Rx ⊂ X × R и Ry ⊂ R × Y соответствия, определенныетак:{(}{(}))Rx = x, (x, y) : x ∈ X, (x, y) ∈ R , Ry = (x, y), y : (x, y) ∈ R, y ∈ Y .Вычислим искажения этих соответствий. Имеем{}dis Rx = max |xx′ | − α|xx′ | − β|yy ′ | : x, x′ ∈ X, (x, y), (x′ , y ′ ) ∈ R ={}= β max |xx′ | − |yy ′ | : (x, y), (x′ , y ′ ) ∈ R = β dis R3. Метрика пространства метрических компактов строго внутренняя.5(аналогично, dis Ry = α dis R).Следовательно, dGH (X, R) ≤ β dGH (X, Y ) и dGH (R, Y ) ≤ α dGH (X, Y ).Но в силу неравенства треугольника dGH (X, R) + dGH (R, Y ) ≤ dGH (X, Y ),откудаd) GH (X, R) = β dGH (X, Y ), а dGH (R, Y ) = α dGH (X, Y ), т.е.
Rα :=(R, | · |α лежит между X и Y . В частности, при α = 1/2 пространство Rαявляется серединой между X и Y .Итак, мы доказали следующий результат.Предложение 3.1. У любых двух конечных метрических пространствсуществует середина в M.Середину между конечными пространствами, построенную описаннымвыше способом, назовем канонической серединой, построенной по оптимальному соответствию R, и будем обозначать той же буквой R.Рассмотрим отображение Γ : [0, 1] → M такое, что X, α = 0,Rα , α ∈ (0, 1),Γα =Y, α = 1.Покажем, что Γ — непрерывное отображение.
Для этого достаточно проверить, что это отображение — изометрическое вложение отрезка, т.е. длялюбых α1 , α2 ∈ [0, 1] выполняется dGH (Γα1 , Γα2 ) = |α1 − α2 | dGH (X, Y ).Действительно, как ранее было замечено, для любого α ∈ (0, 1) выполняетсяdGH (Γ0 , Γα ) = dGH (X, Rα ) = α dGH (X, Y )иdGH (Γ1 , Γα ) = dGH (Y, Rα ) = (1 − α) dGH (X, Y ).Для любых α1 , α2 ∈ (0, 1) таких, что α1 ≤ α2 , рассмотрим тождественноесоответствие Rα1 ,α2 между Rα1 и Rα2 , тогдаdis Rα1 ,α2 ={}max α1 |xx′ | + (1 − α1 )|yy ′ | − α2 |xx′ | − (1 − α2 )|yy ′ | : (x, y), (x′ , y ′ ) ∈ R ={}= (α2 − α1 ) max |xx′ | − |yy ′ | : (x, y), (x′ , y ′ ) ∈ R = (α2 − α1 ) dis R.ПолучаемdGH (Γα1 , Γα2 ) =1= dGH (Rα1 , Rα2 ) ≤ (α2 − α1 ) dis R = (α2 − α1 ) dGH (X, Y ).2В силу обобщенного неравенства треугольника, имеемdGH (Γα1 , Γα2 ) == dGH (Rα1 , Rα2 ) ≥ dGH (X, Y ) − dGH (X, Rα1 ) − dGH (Rα2 , Y ) =()1= 1 − α1 − (1 − α2 ) dis R = (α2 − α1 ) dGH (X, Y ),23. Метрика пространства метрических компактов строго внутренняя.6таким образом, и в этом случае dGH (Γα1 , Γα2 ) = |α1 − α2 | dGH (X, Y ).Тем самым, мы доказали следующее утверждение.Предложение 3.2.
Отображение Γ есть кратчайшая кривая, соединяющая X и Y .Пусть теперь X и Y — произвольные метрические компакты. Для каждого n ∈ N обозначим через Xn и Yn некоторые конечные 1/n-сети в X и Yсоответственно, и пусть Rn — каноническая середина между Xn и Yn . Покажем, что множество {Rn }n∈N ⊂ M — предкомпактно. Так как Xn → Xи Yn → Y , то, по критерию предкомпактности Громова (предложение 2.4),существует D ∈ R такое, что diam Xn ≤ D и diam Yn ≤ D при всех n ∈ N, атакже для каждого ε > 0 существует N (ε) > 0 такое, что во всех Xn и Ynсуществуют ε-сети Xn′ и Yn′ , состоящие не более чем из N (ε) точек каждая.Определим на Xn × Yn расстояние по тому же принципу, что и на Rn , аименно, положим()(x, y), (x′ , y ′ ) = 1 |xx′ | + |yy ′ | .2Ясно, что ограничение этого расстояния на Rn совпадает с расстоянием,заданным на Rn выше.
Кроме того, diam Rn ≤ diam(Xn × Yn ) ≤ D, такчто множество {Rn } равномерно ограничено. Наконец, Xn′ × Yn′ являетсяε-сетью для Xn × Yn , состоящей не более чем из N (ε)2 точек. Но тогда,в силу предложения 2.3, в Rn имеется (2ε)-сеть, состоящая не более чемиз N (ε)2 точек. Таким образом, выполняются условия критерия Громовапредкомпактности, откуда и вытекает предкомпактность множества {Rn }.Без ограничения общности, будем считать, что последовательность Rnсходится в M к некоторому R. Из непрерывности функции расстояния вытекает, что R — середина между X и Y . Таким образом, мы доказали следующий результат.Предложение 3.3.
У любых двух компактный метрических пространствсуществует середина в M.Хорошо известно, что M — полное метрическое пространство, а в полномметрическом пространстве существование середин равносильно тому, чтометрика является строго внутренней. Тем самым, мы доказали следующуютеорему.Теорема 3.1. Метрика пространства M всех метрических компактов,рассматриваемых с точностью до изометрии, является строго внутренней.4. Кратчайшие деревья в пространстве метрических компактов.47Кратчайшие деревья в пространстве метрических компактов с границей, состоящей изконечных метрических пространств.В настоящем разделе мы докажем следующую теорему.Теорема 4.1.
Пусть M = {m1 , . . . , mp } ⊂ M — некоторое множествоконечных метрических пространств. Тогда в M существует кратчайшеедерево Штейнера с границей M , причем все точки Штейнера этого дерева— также конечные метрические пространства.Доказательство. Положим r = smt(M ) и покажем, что существует G ∈T (M ), для которого |G| = r и у которого все точки Штейнера — конечныеметрические пространства.По предложению 2.9, для любого n ∈ N можно выбрать дерево Gn =(Vn , En ) ∈ T (M ) такое, что |Gn | ≤ r+ n1 .
Более того, имеет место следующийрезультат.Лемма 4.1. Пусть D — максимальный диаметр пространств из M . Тоb =гда для любого n ∈ N диаметры пространств из Vn не превосходят DD + r + 1.Доказательство. По определению, диаметр каждого m ∈ M не превосхоb поэтому для таких m предложение доказано.дит D, а, значит, и D,Положим Sn = Vn \ M .
Нам осталось доказать предложение для s ∈ Sn .Пусть m ∈ M , тогда, в силу неравенства треугольника, имеемdGH (s, m) ≤ |Gn | ≤ r +1≤ r + 1.nПо предложению 2.2, имеемdGH (s, m) ≥ | diam s − diam m|.Из последних двух неравенств следует, что| diam s − diam m| ≤ r + 1,поэтому diam s ≤ diam m + r + 1 ≤ D + r + 1.По предложению 2.8, в последовательности Gn существует подпоследовательность, состоящая из деревьев одного типа.
Переходя, если необходимо, к такой подпоследовательности, без ограничения общности будем считать, что все деревья Gn имеют один и тот же тип. Обозначим через f числовершин, а через g — число ребер деревьев Gn , и пусть Sn = {s1n , . . . , sfn−p }— множество внутренних вершин дерева Gn . Мы предполагаем, что sin приразных n соответствуют друг другу при изоморфизмах графов Gn , тождественных на M (эти изоморфизмы существуют в силу того, что графы Gnимеют один и тот же тип).4. Кратчайшие деревья в пространстве метрических компактов.8nДля каждых n ∈ N и uv ∈ En существует такое соответствие Ruv∈11nR(u, v), что dGH (u, v) ≥ 2 dis Ruv − n .
Выберем произвольное m ∈ M ипроизвольную точку xm ∈ m. Рассмотрим ребро mv ∈ En . По определениюnсоответствия существует xv ∈ v такая, что (xm , xv ) ∈ Rm,v. Пусть точка′xv′ ∈ v уже выбрана, тогда для каждого ранее не рассмотренного ребраv ′ v ′′ ∈ En существует точка xv′′ ∈ v ′′ такая, что (xv′ , xv′′ ) ∈ Rvn′ ,v′′ . Выбираяточки xw до тех пор, пока не исчерпаем все множество вершин дерева Gn ,мы получим множество {xw }w∈Vn , которое назовем сечением дерева Gn ,выпущенным из x ∈ m.Из каждой точки x каждого множества m ∈ M выпустим одно произвольное сечение дерева Gn . Заметим, что если N — максимальное числоточек в пространствах из M , то количество построенных сечений не превосходит N ′ = p N .Пусть ŝin ⊂ sin — множество всех лежащих в sin узлов построенных сечений.
Ясно, что число точек в метрическом пространстве ŝin не больше N ′ .b поэтому также diam ŝin ≤ D.b СледоВ силу леммы 4.1, имеем diam sin ≤ D,′Nibbbвательно, ŝn ∈ MDb . Обозначим через Gn = (Vn , En ) граф, полученный изGn заменой внутренних вершин sin на ŝin . Тогда∪{}Vbn = Mŝ1n , . . . , ŝfn−p .b n | → smt(M ) при n → ∞. Легко видеть, что для каждоПокажем, что |Gb n ограничениего ребра uv графа Gn и соответствующего ребра ûv̂ графа Gnна û × v̂ также является соответствием, которое мы обосоответствия Ruvnnbn . Так как Rbn ⊂ Ruvbn ≤ dis Ruvзначим через R, имеем dis R.ûv̂ûv̂ûv̂Через построенные соответствия оцениваются длины ребер ûv̂:dGH (û, v̂) ≤111nnbûv̂dis R≤ dis Ruv≤ dGH (u, v) + .22nb n , получимПросуммировав неравенство по всем ребрам графа Gb n | ≤ |Gn | + g ≤ r + (g + 1) ,r ≤ |Gnnb n | → smt(M ) при n → ∞.поэтому |GУпорядочим точки из Vbn , например Vbn = (m1 , .
. . , mp , ŝ1n , . . . , ŝfn−p ), то((′ )f′ )f. В силу предложений 2.5 и 2.6, пространство MpNгда Vbn ∈ MNbbDDкомпактно, поэтому из последовательности Vn можно выбрать подпосле(′ )fдовательность, сходящуюся к некоторому V ∈ MN. Без ограниченияbDобщности будем считать, что сама последовательность Vn сходится к V .b n заменой их верПусть G = (V, E) — дерево, полученное из деревьев Gbnшин v̂ni ∈ Vbn на пределы v i = limn→∞ v̂ni (напомним, что все деревья Gbимеют один и тот же тип). Тогда |G| = limn→∞ |Gn | = smt(M ), поэтому′G — кратчайшее дерево на M . Так как V ∈ MNb , то все точки ШтейнераDдерева G — конечные метрические пространства.
Теорема полностью доказана.4. Кратчайшие деревья в пространстве метрических компактов.9Список литературы[1] Бураго Д. Ю., Бураго Ю. Д., Иванов С. В. Курс метрической геометрии. Москва-Ижевск, Институт компьютерных исследований, 2004.[2] Иванов А. О., Тужилин А. А. Элементы метрической геометрии и геометрической теории графов спецкурс 2014-2015http://dfgm.math.msu.su/courses.php?comments=19.[3] Иванов А.
О., Тужилин А. А. Теория экстремальных сетей. МоскваИжевск: Институт компьютерных исследований, 2003..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
