Преобразования метрик, сохраняющие типы одномерных минимальных заполнений

Московский государственный университет имениМ.В.ЛомоносоваМеханико-математический факультетПреобразование метрик, сохраняющие типы одномерныхминимальных заполненийДипломная работа студента 603 группы Липатова Степана ЮрьевичаНаучный руководитель: профессор Тужилин Алексей АвгустиновичМосква, 2017.Преобразование метрик, сохраняющие типыодномерных минимальных заполненийС.

Ю. Липатов25 мая 2017 г.ВведениеПроблема Штейнера — это задача об оптимальном соединении конечногомножества точек метрического пространства. По-видимому, первые формулировки этого типа возникли в трудах Ферма, поставившего вопрос опоиске такого расположения точки на плоскости, что сумма расстояний отнее до вершин заданного треугольника наименьшая из возможных. В течении нескольких столетий был получен полный ответ, из которого ясно,что, соединяя три точки на плоскости, бывает выгодно добавить четвертую точку-развилку. Важность таких дополнительных точек прекрасно понимал Гаусс, обсуждавший в переписке с Шумахером задачу о том, каксоединить Гамбург, Бремен, Ганновер и Брауншвейг кратчайшей системойдорог.

В 1934 году Ярник и Кесслер сформулировали общую задачу, которая теперь известна как классическая проблема Штейнера. Фактически, ихзадача представляет собой обобщение задачи Ферма и Гаусса о кратчайшемсоединении на случай произвольного конечного множества точек плоскости. Что касается самого Штейнера, то он занимался другим обобщениемзадачи Ферма: найти в пространстве такую точку, для которой сумма расстояний до заданных точек будет наименьшей возможной. Отметим, чтонедоразумение о приоритете возникло благодаря популярной книге Куранта и Роббинса “Что такое математика?”, где задача Ферма была приписанаШтейнеру, а задача Ярника и Кесслера была названа просто обобщениемпроблемы Штейнера.Сетью в псевдометрическом пространстве X = (X, d), параметризованной произвольным связным графом G = (V, E), или сетью типа G,называется отображение Γ : V → X ([1]). Вершинами и ребрами сети Γ называются ограничения отображения Γ соответственно на вершины и ребраграфа G.

Длиной ребра Γ : vw → X назовем число d(Γ(v), Γ(w)), а длиной d(Γ) сети Γ — сумму длин всех ее ребер. Границей ∂Γ сети Γ назовем ограничение отображения Γ на ∂G. Если M ⊂ X — конечное множество и M ⊂ Γ(V ), то будем говорить, что сеть Γ соединяет множествоM .

Вершины графов и сетей, не являющиеся граничными, будем называть1внутренними. Число smt(M ) = inf{d(Γ)|Γ — сеть, соединяющая M } назовем длиной кратчайшей сети. Сеть, для которой d(Γ) = smt(M ), называется кратчайшей сетью ([2]). Понятие минимального заполнения появилосьв работах Громова в следующем виде: пусть M = (M, ρ), где M — замкнутое многообразие c функцией расстояния ρ на нём, а W = (W, d), где W —компактное многообразие с краем, равным M , таково, что d не уменьшает расстояния между точками из M , тогда W называется заполнением M.Задача Громова состоит в описании точной нижней грани объемов заполнений, а также описании тех пространств W, называемых минимальнымизаполнениями, на которых эта нижняя грань достигается.В контексте проблемы Штейнера естественно рассмотреть в качествеM конечное метрическое пространство. Тогда возможные заполнения —метрические пространства, имеющие структуру одномерных стратифицированных многообразий (которые можно рассматривать как реберно взвешенные графы с неотрицательными весовыми функциями).

Графы отдельно от весовых функций будем называть типами заполнений. При этом будем рассматривать только такие типы, в которых вершинам степени 1 и 2соответствуют точки метрического пространства M . Объяснения, почемуможно ограничиться такими типами, будет дано ниже.Ивановым и Тужилиным [1] было доказано, что преобразования типаρ 7→ λρ + a для a > λaρ , λ > 0, где aρ — некоторое число, зависящееот метрики ρ, сохраняют типы G минимальных заполнений метрическогопространства, точки которого соответствуют вершинам степени 1 графов G.Число a может быть отрицательным; существует такое aρ ≤ 0, для которогоλρ+a — метрика при всех a > λaρ , и не является метрикой при всех a < λaρ(при a = λaρ можем получить как метрику, так и псевдометрику).Общая задача была сформулирована следующим образом: задан классF метрических пространств и семейство преобразований T метрики.

Нужнобыло описать семейство преобразований T 0 ⊂ T , которые переводят F в себяи сохраняют некоторые типы минимальных заполнений. Был рассмотренслучай,• когда F — класс всех конечных метрических пространств,T = {(M, ρ) → (M, f ◦ ρ) : f : R>0 → R>0 }, а элементы T 0 сохраняютвсе невырожденные типы минимальных заполнений четырехточечныхметрических пространств и конечных невырожденных звёзд, и доказано, что T 0 = {(M, ρ) → (M, λρ + a) : a > λaρ } (опубликовано в [3]);• когда F — класс всех конечных метрических пространств, класс Tсостоит из отображений ρ → N ρ, где матрицы N имеют вид 2.7 (суммаположительной диагональной матрицы A и матрицы с одинаковымистроками из неотрицательных элементов), а элементы T 0 сохраняютвсе минимальные заполнения типа невырожденных звезд, и доказано,что T 0 состоит из таких отображений ρ → N ρ, где A — скалярна;• когда F — класс всех конечных аддитивных метрических пространств,T — класс всех линейных отображений, задаваемых матрицами, а эле2менты T 0 сохраняют все невырожденные типы минимальных заполнений, и доказано, что для четырёхточечных метрических пространствT 0 — множество преобразований, заданных скалярными матрицами;• когда F — класс всех конечных ультраметрических пространств, T— класс всех линейных отображений, задаваемых матрицами, и доказано, что для трёхточечных пространств матрицы имеют вид A =R(B + λE), где B — матрица из одинаковых строк из положительныхэлементов, а R — перестановка точек (1, 0, 0), (0, 1, 0) и (0, 0, 1).Кроме того, получены доказательства некоторых свойств конечныхультраметрических пространств и способ описания множества пространств с одинаковыми типами минимальных заполнений.Автор благодарен своему научному руководителю профессору Тужилину А.А., а также профессору Иванову А.О.

за постановку задачи и постоянное внимание к работе.1Предварительные результатыПриведем необходимые для дальнейшего определения и результаты. Подробности см. в [1].Определение 1.1. Псевдометрикой на множестве M называют такуюсимметричную функцию ρ : M 2 → R, для которой ρ(a, a) = 0 при всех a ивыполнены неравенства треугольника: ρ(i, j) ≤ ρ(i, k) + ρ(k, j) для любыхi, j, k ∈ M . Отметим, что из неравенства треугольника вытекает неотрицательность функции ρ, так как 0 = ρ(a, a) ≤ 2ρ(a, b). Метрикой на множествеM называют такую псевдометрику d, что для любых различных a, b ∈ Mвыполнено d(a, b) 6= 0.Пусть M — произвольное конечное множество и G = (V, E) — некоторый связный граф.

Будем говорить, что G соединяет M , а M — границаграфа G, если M ⊂ V . Границу графа G будем также обозначать через∂G. Вершины графов и сетей, не являющиеся граничными, будем называтьвнутренними. Пусть теперь M = (M, ρ) — конечное псевдометрическоепространство (в отличие от метрики, расстояния между разными точкамимогут быть равны нулю), G = (V, E) — связный граф, соединяющий M ,и ω : E → R+ — некоторое отображение в неотрицательные вещественныечисла, называемое обычно весовой функцией и порождающее взвешенныйграф G = (G, ω). Весом взвешенного графа G называется величина ω(G),равная сумме весов всех ребер этого графа.

Функция ω задает на V псевдометрику dω , а именно, расстоянием между вершинами графа G назовемнаименьший из весов путей, соединяющих эти вершины. Если для любыхточек p и q из M выполняется ρ(p, q) ≤ dω (p, q), то взвешенный граф Gназывается заполнением пространства M, а граф G — типом этого заполнения. Число mf(M) = inf ω(G) по всем заполнениям G пространства3M назовем весом минимального заполнения, а заполнение G, для которогоω(G) = mf(M), — минимальным заполнением.Соглашение 1.2. Не будем рассматривать типы, в которых есть внутренние вершины степени 1 или 2: если есть заполнение с таким типом, то можноубрать вершины степени 2 с сохранением веса заполнения и убрать вершины степени 1 вместе с входящими в них рёбрами и при этом вес заполненияне увеличится. Поэтому всегда среди минимальных заполнений будут несодержащие внутренних вершин степени 1 или 2.Конечное псевдометрическое пространство M = (M, ρ) называется аддитивным, если M можно соединить взвешенным деревом G = (G, ω) длякоторого ρ совпадает с ограничением dω на M ([1]).

Дерево G в этом случаеназывается порождающим. Взвешенные графы и заполнения с положительными весами будем называть невырожденными.Утверждение 1.3 ([1]). У каждого аддитивного пространства единственным невырожденным минимальным заполнением является его невырожденное порождающее дерево.Утверждение 1.4 ([1]). Пространство M = (M, ρ), минимальное заполнение G = (G, ω) которого представляет собой звезду, в которой внутренняя вершина v соединена со всеми точками pi ∈ M , 1 ≤ i ≤ n, n ≥ 3,аддитивно.Пусть G = (V, E) — произвольное дерево.

Пусть v ∈ V — внутренняявершина степени (k+1) ≥ 3, смежная с k вершинами w1 , . . . , wk из ∂G. Тогдамножество вершин {w1 , . . . , wk }, а также множество ребер {vw1 , . . . , vwk },называются усами. Число k назовём степенью, а v — общей вершиной этихусов.Теорема 1.5 ([1]). Преобразования типа ρ 7→ λρ+a для a > λaρ сохраняюттипы G минимальных заполнений метрического пространства, точки которого соответствуют вершинам степени 1 графов G.Будем называть дерево бинарным, если каждая его вершина имеет степень 1 или 3, а граница состоит в точности из всех вершин степени 1.Утверждение 1.6 ([1]). Пусть M = {p1 , p2 , p3 , p4 }, и ρ — произвольнаяпсевдометрика на M .

Положим ρij = ρ(pi , pj ). Тогда вес минимальногозаполнения G = (G, ω) пространства M = (M, ρ) дается формулой1min{ρ12 + ρ34 , ρ13 + ρ24 , ρ14 + ρ23 } + max{ρ12 + ρ34 , ρ13 + ρ24 , ρ14 + ρ23 } .2Если минимум в этой формуле равен ρij + ρrs , то тип минимальногозаполнения — бинарное дерево, усы которого суть {pi , pj } и {pr , ps }.Утверждение 1.7 ([1]).