Минимальные деревья Штейнера в пространстве метрических компактов (848704)
Текст из файла
Московский Государственный УниверситетМеханико-математический факультетМинимальные деревья Штейнерав пространстве метрических компактов.Дипломная работа студентки 503 группыНиколаевой Надежды КонстантиновныНаучный руководитель: д.ф.–м.н., профессор Тужилин А. А.Москва, 2015 год1. Введение11ВведениеОбозначим через M пространство всех метрических компактов (рассматриваемых с точностью до изометрии) с метрикой Громова–Хаусдорфа. Известен ряд свойств пространства M, например, что оно — линейно связное,полное, сепарабельное, но не ограниченно компактное. Тужилин А.А.
поставил задачу об исследовании существования минимальных деревьев Штейнера (кратчайших деревьев) в пространстве метрических компактов. В процессе исследования данной задачи возник другой вопрос: является ли метрика Громова–Хаусдорфа строго внутренней? Мы покажем, что ответ — положительный. Кроме того, мы докажем, что для границ, состоящих толькоиз конечных метрических пространств, всегда существует кратчайшее дерево, причем такое, у которого дополнительные вершины (точки Штейнера)также являются конечными метрическими пространствами.Проблема Штейнера изучается уже давно, изначально она была поставлена для точек евклидовой плоскости, где ее можно наглядно интерпретировать как задачу проектирования системы дорог, соединяющей некоторое число городов так, чтобы затраты на строительство были наименьшими (при условии, что затраты на постройку дороги пропорциональныее длине).
В пространстве метрических компактов с метрикой Громова–Хаусдорфа построение пространства, минимизирующего суммарное расстояние до заданных пространств, можно также наглядно представлять какпостроение “среднего” изображения, наиболее похожего на ряд имеющиеся,заданных заранее изображений.Автор благодарен своему научному руководителю профессору Тужилину А.А., а также профессору Иванову А.О. за постановку задачи и постоянное внимание к работе.2Основные определения и предварительныерезультатыВсе определения и утверждения из этого раздела можно найти в [1] – [3].Пусть X — произвольное метрическое пространство.
Расстояние междуего точками x и y будем обозначать через |xy|. Для каждых x ∈ X и непустого A ⊂ X определим |xA| как точную нижнюю грань расстояний |xa| повсем a ∈ A; для непустых A, B ⊂ X определим d(B, A) как точную верхнююгрань расстояний |bA| по всем b ∈ B; наконец, для тех же A и B положимdH (A, B) = max{d(A, B), d(B, A)}. Число dH (A, B) называется расстояниемХаусдорфа. Хорошо известно, что на множестве всех замкнутых ограниченных подмножеств пространства X функция dH является метрикой.Пусть X и Y — метрические пространства.
Тройку (X ′ , Y ′ , Z), состоящую из метрического пространства Z и двух его подмножеств X ′ и Y ′ ,изометричных соответственно X и Y , назовем реализацией пары (X, Y ).Расстоянием dGH (X, Y ) Громова–Хаусдорфа между X и Y называется точная нижняя грань чисел r, для которых существует реализация (X ′ , Y ′ , Z)2. Основные определения и предварительные результаты2пары (X, Y ) такая, что dH (X ′ , Y ′ ) ≤ r. Хорошо известно, что на множестве M всех компактных метрических пространств функция dGH являетсяметрикой.Напомним, что отношением между множествами X и Y называетсякаждое подмножество декартова произведения X × Y . Множество всех отношений между X и Y обозначим через P(X, Y ).
Если πX : X × Y → X иπY : X × Y → Y — канонические проекции, т.е. πX (x, y) = x и πY (x, y) = y,то теми же символами будем обозначать ограничения этих отображений накаждое отношение σ ⊂ P(X, Y ).Отношение R между X и Y называется соответствием, если ограничение канонических проекций πX и πY на R — сюръекции. Иными словами,для каждого x ∈ X существует y ∈ Y , находящийся с x в отношении Rи, обратно, для каждого y ∈ Y существует x ∈ X, находящийся с y в отношении R. Множество всех соответствий между X и Y обозначим черезR(X, Y ).Пусть X и Y — метрические пространства, тогда для каждого отношения σ ∈ P(X, Y ) определено его искажение dis σ:{}dis σ = sup |xx′ | − |yy ′ | : (x, y) ∈ σ, (x′ , y ′ ) ∈ σ .Если f : X → Y — отображение, то его искажением dis f назовем искажениеграфика отображения f .Следующий результат хорошо известен.Предложение 2.1.
Для любых метрических пространств X и Y имеемdGH (X, Y ) ={}1inf dis R | R ∈ R(X, Y ) .2Если X и Y — конечные метрические пространства, то множество R(X, Y )конечно, поэтому существует R ∈ R(X, Y ), для которого dGH (X, Y ) =12 dis R. Каждое такое отношение R назовем оптимальным.Нам понадобится еще несколько вспомогательных результатов.Предложение 2.2. Пусть X, Y — компактные метрические пространства, тогда верно следующее неравенство| diam X − diam Y | ≤ dGH (X, Y ) ≤ max{diam X, diam Y }.Предложение 2.3. Пусть X — произвольное метрическое пространство,Y — непустое подмножество X, а S — некоторая ε-сеть в X.
Тогда вY существует (2ε)-сеть, мощность которой не превосходит мощностимножества S.Пусть M ⊂ M — некоторое семейство метрических компактов. Будемговорить, что M равномерно вполне ограничено, если выполняются следующие два условия:2. Основные определения и предварительные результаты3(1) существует число D ≥ 0 такое, что для любого X ∈ M имеет местоdiam X ≤ D (диаметры пространств из M равномерно ограничены);(2) для каждого ε > 0 существует N (ε) ∈ N такое, что каждое X ∈ Mсодержит некоторую ε-сеть, состоящую не более чем из N (ε) точек(количества элементов ε-сетей равномерно ограничены).Предложение 2.4. Семейство M ⊂ M — предкомпактно, если и толькоесли оно — равномерно вполне ограничено.Обозначим MND ⊂ M все метрические пространства (точнее, их классыизометрии), состоящие не более чем из N точек и с диаметром, не превосходящем D.Предложение 2.5. Пространство MND — компактно.Предложение 2.6.
Если K — компактное пространство, то K f , где f ∈N, — тоже компактное пространство.Также напомним что такое графы в метрическом пространстве X. ПустьG = (V, E) — произвольный граф с множеством вершин V ⊂ X и множеством ребер E. Длиной ребра uv ∈ E назовем величину, равную расстояниюмежду вершинами, которые соединяет это ребро. Сумму длин всех реберграфа G назовем длиной графа G и обозначим через |G|.Пусть M — конечное подмножество X. Будем говорить, что связныйграф G соединяет множество M , если M ⊂ V .
Обозначим через G(M )множество всех (связных) графов в пространстве X, соединяющих M . Дляграфа G = (V, E) ∈ G(M ) его границей будем называть множество M ;элементы из M назовем граничными вершинами графа G, а элементы изS = V \ M — внутренними вершинами графа G. Будем говорить, что графы G1 , G2 ∈ G(M ) имеют один тип, если между ними существует изоморфизм, тождественный на их общей границе M .Точную нижнюю грань длин всех графов G ∈ G(M ) назовем длинойкратчайшего дерева и будем обозначать через smt(M ). Каждый граф G ∈G(M ), длина которого равна smt(M ), является деревом и называется кратчайшим деревом или минимальным деревом Штейнера с границей M .Множество таких деревьев обозначим через SMT(M ).Замечание 2.7.
Пусть G = (V, E) — кратчайшее дерево с границей M .Тогда G не содержит внутренних вершин степени 1, так как иначе деревоG можно укоротить, не меняя его границу, выбросив инцидентное такойвершине ребро.Предположим теперь, что G содержит внутреннюю вершину v степени2. Обозначим через e1 = vv1 и e2 = vv2 ребра дерева G, инцидентные v.Перестроим G, выкинув v из V и заменив e1 и e2 на ребро e = v1 v2 . ТогдаG также является кратчайшим деревом. Продолжая эту процедуру до техпор, пока в получившемся дереве не останется ни одной подвижной вершины степени 2, мы получим кратчайшее дерево. Тем самым, для описания3. Метрика пространства метрических компактов строго внутренняя.4кратчайших деревьев достаточно рассматривать лишь те деревья, которыене имеют подвижных вершин степени 2.В дальнейшем мы всегда будем считать, что граница M включает всевершины степени 1 и 2, а SMT(M ) состоит из всех кратчайших деревьев,не имеющих подвижных вершин степени 2.При таких ограничениях, внутренние вершины каждого кратчайшегодерева называются точками Штейнера.Обозначим через T (M ) подмножество в G(M ), состоящее из деревьев, укоторых степени внутренних вершин не меньше 3.Предложение 2.8.
Число типов деревьев из T (M ) конечно.Предложение 2.9. Имеем{}smt(M ) = inf |G| : G ∈ T (M ) и SMT(M ) ⊂ T (M ).3Метрика пространства метрических компактов строго внутренняя.Пусть X и Y — два конечных метрических пространства, и R — оптимальное соответствие между ними. Тогда, по определению, dGH (X, Y ) = 12 dis R.Определим на R функцию расстояния так. Выберем произвольное 0 ≤α ≤ 1 и пусть β = 1 − α.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
