Задача об оптимальном соединении в пространствах компактов (1102650), страница 2
Текст из файла (страница 2)
Текст диссертации изложен на 51 страницах.Список основных результатов, выносимых на защитуРезультаты диссертации являются новыми. В диссертации получены следующие основные результаты:1. Теорема 2.5 о минимальности отношений Штейнера и ГромоваШтейнера метрического пространства компактов евклидового пространства.2. Получена оценка суботношения Штейнера метрического пространства компактов евклидового пространства.3. Получена точная оценка минимума суботношений Штейнера выпуклых пятиточечных подмножеств евклидовой плоскости.4.
Теорема 4.16 о невозможности наличия ровно 41, 59 или 67 кратчайших между двумя компактами в евклидовом пространстве.Методы исследованияВ диссертации применяются методы геометрии, топологии, теории графов. Используется метод машинного перебора. Вводится новый подходк исследованию реберных покрытий через склейки графов с выделеннойвершиной и атомарные графы.6Апробация работыРезультаты диссертации докладывались на следующих семинарах и конференциях:∙ на семинаре «Оптимальные сети» под руководством профессораА. О. Иванова и А. А. Тужилина (МГУ, 2010-2014 гг.)∙ на второй международной конференции «Вероятность, анализ игеометрия» (МГУ, 2014 год)∙ на семинаре «Дифференциальная геометрия и приложения» подруководством академика А. Т. Фоменко (МГУ, 2014 год)∙ на семинаре «Дискретная геометрия и теория чисел» под руководством профессора М.
Д. Ковалева (МГУ, 2015 год)ПубликацииОсновное содержание диссертации опубликовано в работах [ShPaths],[GHSub] и [Ssr5], все — в журналах из перечня ВАК (для работ [GHSub]и [Ssr5] в перечень входит версия журнала на английском языке).БлагодарностиАвтор выражает глубокую благодарность профессору А. О. Иванову ипрофессору А. А. Тужилину за постановку задач, поддержку и вниманиек работе, а также П. А.
Бородину, Н. П. Стрелковой, И. Л. Лауту идругим слушателям и докладчикам семинара «Оптимальные сети» заполезные обсуждения и предложения.71Необходимые определения и предварительные результаты1.1Расстояние Хаусдорфа, пространство компактови его основные свойстваПусть — метрическое пространство с метрикой , ∈ — произвольная точка в нем, а ⊂ — произвольное непустоеподмножество. Тогда расстоянием между точкой и множеством будемназывать величину (, ) = inf (, ).Определение 1.1.∈Пусть — метрическое пространство с метрикой, а , ⊂ — некоторые его непустые подмножества. РасстояниемХаусдорфа между ними называется величинаОпределение 1.2.
(, ) = max(sup (, ), sup (, )).∈∈Вышеприведенное определение требует некоторых пояснений. Неформально, это наименьшая возможная величина на которую нужно «раздуть» множества таким образом, что раздутые множества покрываютоба исходных. Отметим что, во-первых, эта величина не всегда существует (например, если одно из множеств ограничено, а второе — нет),а, во-вторых, это расстояние весьма непохоже на обычно рассматриваемое «расстояние» между множествами как инфинум расстояний междуих элементами, которое на самом деле не является расстоянием в пространстве компактов.
Например, расстояние между пересекающимися,но не совпадающими компактами не равно нулю, в отличие от обычного«расстояния» между множествами.Несложно показать, что верно следующее утверждение (доказательство можно посмотреть, например, в [16]):Если рассмотреть пространство всех замкнутыхограниченных множеств в , то расстояние Хаусдорфа задает на немметрику.Утверждение 1.3.Пространство компактов из с заданной на немметрикой Хаусдорфа будем обозначать как ℋ(), в частности, пространство компактов из R будем обозначать как ℋ(R) .Определение 1.4.Это пространство обладает многими интересными свойствами, например, полнотой [16] и ограниченностью (там же).При этом в некотором смысле расстояние Хаусдорфа является естественным обобщением расстояния между точками.Расстояние Хаусдорфа между компактами, состоящими из одной точки, равно расстоянию между этими точками.Замечание 1.5.81.1.1Свойства кратчайших в пространстве компактов с расстоянием ХаусдорфаКривая, соединяющая точки , ∈ , называетсякратчайшей, если она имеет конечную длину и не существует кривой стеми же концами, но меньшей длиной.Определение 1.6.Кратчайшие в пространстве компактов в R с расстоянием Хаусдорфа довольно хорошо изучены.
Нам понадобится несколько утвержденийиз разных источников, в частности [3], [1], [4], [16].Метрика Хаусдорфа на пространстве компактовℋ(R ) является внутренней, то есть, расстояние Хаусдорфа равно инфинуму длин кривых, соединяющих компакты.Утверждение 1.7.Для любой пары компактов из ℋ(R ) существуетхотя бы одна кратчайшая.Утверждение 1.8.Из этих утверждений следует,что метрика Хаусдорфа являетсястрого внутренней, то есть, между любыми двумя точками существует кривая, длина которой будет равна расстоянию между ними.Пусть , ∈ℋ(R ) — произвольные компактыв пространстве R , и (, ) —расстояние Хаусдорфа между ними.
Если существует пара точек ∈ , ∈ такая, что(, ) < (, ), то существует бесконечное количество крат- Рис. 1: Расстояние Хаусдорфа межчайших, соединяющих их (напри- ду большим кругом и маленькиммер, [2]).равно радиусу большого кругаУтверждение 1.9.Это утверждение показывает,что лишь очень узкий класс паркомпактов может иметь конечное количество кратчайших.Реберным покрытием графа = (, ) с множеством вершин и множеством ребер называется любое подмножестворебер ′ ⊂ такое, что для любой вершины ∈ графа существуетхотя бы одно ребро из ′ , инцидентное данной вершине.Определение 1.10.9Пусть , ∈ ℋ(R ) — произвольные компакты впространстве R , и — конечное количество кратчайших между ними.
Тогда существует двудольный граф такой, что он имеет ровно реберных покрытий.Обратно, пусть — произвольный двудольный граф и > 0 —количество его реберных покрытий. Тогда существует > 0 и двакомпакта , ∈ ℋ(R ) такие, что количество кратчайших междуними равно .Утверждение 1.11.Приведем здесь краткий ходдоказательства. Сначала показывается, что для двух компактов и в евклидовом пространстве, находящихся на расстоянии в смысле Хаусдорфа, количество кратчайших равно количеству компактов в -положении длянекоторого 0 < < , а именно,компактов, расстояние Хаусдорфаот которых до компакта равно ,а до компакта равно − . Приэтом конкретное значение не имеет значения.
Из предыдущих работизвестно, что хотя бы один компакт в⋃︀-положении⋃︀ есть, а именно, Рис. 2: Квадрат имеет 7 реберных= () ∩ ( − ) ̸= ∅, покрытий∈∈более того, любой другой компактв -положении является его подмножеством. Здесь () — замкнутый шар радиуса с центром в точке. Затем показывается, что если существуют точки ∈ и ∈ нарасстоянии (, ) < (, ), то число компактов в -положении бесконечно. В самом деле, если взять открытый шар достаточно маленькогоразмера int (), выбрав центр шара из () ∩ ( − ), и вырезатьего из компакта , то получится компакт ∖ int (), который такжебудет находиться в -положении.Таким образом, конечным числом кратчайших могут обладать лишьпары компактов, точки которых попарно находятся на расстоянии неменее расстояния Хаусдорфа.
Для простоты будем рассматривать конечные компакты, но в исходной работе те же утверждения доказывалисьдля произвольных компактов. Пусть и — конечные компакты, такие,что для любой точки ∈ верно (, ) = (, ), и, аналогично, длялюбой точки ∈ верно (, ) = (, ). Тогда множество будетсостоять из точек, которые находятся на расстоянии от какой-либо точ10ки ∈ и − от какой-либо точки ∈ . При этом расстояние междуточками и должно быть равно , для каждой точки из такая пара точек определяется единственным образом и для каждой пары точек ∈ , ∈ , находящихся на расстоянии , такая точка единственна (последние два свойства как раз обеспечивает евклидовость пространства).Можно представить точки из компактов и как вершины некоторого графа, а точки из — как его ребра, соединяющие соответствующиевершины из и .
Получили двудольный граф, при этом каждому компакту в -положении можно однозначно сопоставить подмножество реберэтого графа. При этом, компакт находится в -положении тогда и толькотогда, когда для любой точки ∈ есть точка из этого компакта, находящаяся на расстоянии от него, и для любой точки ∈ есть точкаэтого компакта, находящаяся от нее на расстоянии − . Переведя этоутверждение на язык графов, получим, что для каждой вершины графадолжно быть ребро из подмножества ребер, инцидентное этой вершине,то есть, это подмножество является реберным покрытием.В обратную сторону, пусть есть двудольный граф в котором нетвершин степени 0, множество его вершин разбивается на две доли, = {1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
