Задача об оптимальном соединении в пространствах компактов

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТимени М. В. ЛОМОНОСОВАМЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТНа правах рукописиУДК 514.124+519.174.1Овсянников Захар НиколаевичЗадачи об оптимальном соединении в пространствахкомпактовСпециальность 01.01.04 —«геометрия и топология»Диссертация на соискание учёной степени кандидатфизико-математических наукНаучный руководитель:доктор физико-математических наук Иванов Александр ОлеговичМосква — 2016СодержаниеВведение1Необходимые определения и предварительные результаты81.1Расстояние Хаусдорфа, пространство компактов и его основные свойства . .

. . . . . . . . . . . . . . . . . . . . . .81.1.1 Свойства кратчайших в пространстве компактов срасстоянием Хаусдорфа . . . . . . . . . . . . . . . .9Кратчайшие сети, минимальные заполнения, различные фундаментальные отношения . . . . . . . . . . . . . . . . . . . 121.2234Различные отношения типа Штейнера для пространстваℋ(R )2.1 Определения и предварительные результаты . . . . . . .

.2.2 Отношения Штейнера и Громова-Штейнера . . . . . . . .2.3 Cуботношение Штейнера степени 3 и 4 . . . . . . . . . . .17R3 и 5 для R23.1 Пятиточечное суботношение Штейнера для плоскости . . .3.1.1 Общий случай . . . . . . . . . . . . . . . . . . . . .3.1.2 Выпуклый случай . . . . . . . . . . . . . . . . . .

.3.2 Четырехточечное суботношение Штейнера для трехмерного пространства . . . . . . . . . . . . . . . . . . . . . . . . .23Возможные количества кратчайших33Суботношения Штейнера типа 4 для4.14.253Определения и предварительные результаты4.1.1 Характеристики графа с выделеннойточки зрения реберных покрытий . .4.1.2 Атомарные графы . . . . . . . . . . .Основные результаты .

. . . . . . . . . . . .. . . . . . . .вершиной с. . . . . . . .. . . . . . . .. . . . . . . .Заключение171819232324273333353842Список литературы43A Исходный код программы, реализующей поиск возможного количества реберных покрытий двудольного графа 452ВведениеДиссертация посвящена изучению фундаментальных свойств пространства компактов евклидового пространства с метрикой Хаусдорфа, связанных с кратчайшими сетями и кратчайшими кривыми в этом пространстве, а также фундаментальных свойств евклидовых плоскости ипространства, связанных с кратчайшими сетями и минимальными заполнениями.Расстояние Хаусдорфа было введено в начале XX века и широко используется в различных прикладных областях, например, в распознавании изображений, компьютерной графике и финансовой математике.Неформально расстояние Хаусдорфа между двумя компактами в метрическом пространстве можно описать как минимальную величину, такую,что если мы «раздуем» какое-либо из множеств на эту величину, то оноцеликом покроет другое.

Функция расстояния Хаусдорфа задает метрику на множестве компактов метрического пространства. Естественнымобразом возникает интерес к кратчайшим кривым и кратчайшим сетямв пространстве компактов. Несложно показать, что метрика пространства компактов евклидового пространства является строго внутренней,то есть, длина кратчайшей кривой в пространстве компактов равна расстоянию Хаусдорфа (пример доказательства можно найти в [16]). В серии работ, рассматривавшей количество различных кратчайших междудвумя фиксированными точками пространства компактов евклидовогопространства было показано, что «в большинстве случае»’ их количествобесконечно [2], затем были получен неожиданный результат, показавший,что между двумя компактами в этом пространстве не может быть 19кратчайших, но может быть любое другое количество кратчайших от 1до 36 [1], и, наконец, что 37 кратчайших быть не может [4].

Таким образом, поиск возможных количеств кратчайших представляет интерес какв связи с возможностью продолжения этой последовательности, так икак фундаментальная характеристика пространства компактов. В главе4 показывается возможность продолжения последовательности с помощью машинного перебора и приводятся результаты такового, показывающие, что между двумя компактами в данном пространстве не можетбыть 41, 59 или 67 кратчайших кривых.Одной из важных и интересных фундаментальных характеристикметрического пространства является отношение Штейнера, возникающее при изучении кратчайших сетей. Сеть, соединяющая заданный набор точек метрического пространства, называемых граничными, это набор кривых в метрическом пространстве, возможно, имеющих общиеконцы, таких, что из любой граничной точки в любую другую ведетцепочка кривых с общими концами.

Длиной такой сети называется сумма длин этих кривых, она очевидным образом ограничена снизу. Сеть,3соединяющая заданный набор граничных точек, имеющая минимальновозможную длину, называется (если она существует) кратчайшей. Можно представить граничные точки городами, которые нужно соединитьдорогами (или телефонной сетью) так, чтобы из каждого города можнобыло бы доехать (или позвонить) в каждый другой.

Естественно, длину получившейся сети хочется сделать минимальной для экономии на еестроительстве. Задача нахождения кратчайшей сети по данному набору граничных точек называется задачей Штейнера и имеет множестворазличных применений, от трассировки печатных плат до отслеживанияэволюционных процессов. Существует ряд алгоритмов для решения этойзадачи, например, алгоритм Мелзака [21] или Мелзака-Хванга [22] дляевклидовой плоскости. К сожалению, задача Штейнера является NPполной (см.

[20]), а значит, скорее всего, для нее не существует алгоритма, работающего за полиномиальное время от количества граничныхточек.Вследствие этого представляют интерес алгоритмы по поиску приближенного решения задачи Штейнера, «почти кратчайшей» сети. Одним из приближений кратчайшей сети является минимальное остовноедерево, для которого существует алгоритм построения квадратичной сложности на плоскости [23] и алгоритм сложности (2 log ) в общем случае.

Остовное дерево — это сеть, соединяющая данный набор точек кривыми между ними. В общем случае длина минимального остовного дерева не совпадает с длиной кратчайшей сети, при этом не меньше ее.Однако минимальное остовное дерево является хорошим приближением кратчайшей сети в том смысле, что отношение длины кратчайшейсети к длине минимального остовного дерева ограничено снизу. Это отношение называется отношением Штейнера и для любого метрическогопространства и конечного множества граничных точек оно не меньше12 (см., например, [12]).

Известная гипотеза Гильберта-Поллака говорит,что для евклидовой плоскости минимальное остовное дерево еще лучше приближает кратчайшую сеть и отношение Штейнерадля любого√3конечного множества граничных точек не меньше 2 . Несмотря на рядпопыток доказать эту гипотезу, она все еще остается недоказанной дляобщего случая (см., например, [14]). Отношением Штейнера метрического пространства называется инфинум отношений Штейнера для всехвозможных конечных граничных подмножеств. Отношение Штейнерапространства является его важной фундаментальной характеристикой.В различных работах были получены оценки и точные значения дляотношений Штейнера евклидовой плоскости и различных частных множеств граничных точек (например, [8], [9], [10]), евклидового пространства ([24]), манхэттенской плоскости ([25]) и многих других метрическихпространств.

В главе 2 настоящей диссертации показывается, что значение отношения Штейнера для пространства компактов евклидового4пространства достигает минимально возможного значения.Отношение Штейнера на пространстве компактов евклидового пространства с метрикой Хаусдорфа достигает минимальновозможного значения 12 .Теорема 1.Другими важными характеристиками метрического пространства являются отношения Громова-Штейнера и суботношение Штейнера, основывающиеся на понятии минимального заполнения, введенного в [14].В одной из интерпретаций, минимальное заполнение конечного метрического пространства или конечного подмножества метрического пространства — это сеть минимальной длины, выбранная среди всех сетейво всех возможных метрических пространствах, с множеством граничных точек, изометричным данному конечному метрическому пространству.

Она всегда существует и ее длина называется весом минимальногозаполнения. Вес минимального заполнения является своеобразной оценкой снизу для длины кратчайшей сети, и отношение веса минимальногозаполнения к длине кратчайшей сети, называемое суботношением Штейнера, не больше 1. В [17] показано, что существуют банаховы метрические пространства, для конечных подмножеств которых это суботношение всегда равно 1. Аналогично отношению и суботношению Штейнераконечного подмножества метрического пространства вводится отношение Громова-Штейнера, являющееся отношением веса минимального заполнения к длине минимального остовного дерева.

Несложно заметить,что отношение Громова-Штейнера — это произведение отношения и суботношения Штейнера. По аналогии можно определить эти отношенияи для метрического пространства. Задача поиска отношения ГромоваШтейнера и суботношения Штейнера метрического пространства тесносвязана с поиском отношения Штейнера для него. Были найдены оценки и точные значения суботношения Штейнера для евклидовой плоскости в [11] и пространств Линденштраусса (в частности, манхэттенскойплоскости) в [17]. Также любая оценка на отношение Штейнера, очевидно, дает оценку на отношение Громова-Штейнера.

В главе 2 находитсяотношение Громова-Штейнера для пространства компактов евклидовапространства с метрикой Хаусдорфа и оценка для суботношения Штейнера того же пространства. Также в главе 3 приводятся оценки на этиотношения для евклидовых плоскости и пространства, опровергается рядимевшихся гипотез.Структура работыРабота состоит из введения, четырех глав, списка литературы и приложения.5В первой главе вводятся понятия сетей, различных отношений дляконечных множеств и пространств, реберных покрытий и формулируются результаты, необходимые для доказательства основных утверждений диссертации, в том числе отношение между реберными покрытиямидвудольного графа и кратчайшими в пространстве компактов.Во второй главе доказываются оценки на отношения Штейнера, ГромоваШтейнера и суботношение Штейнера для метрического пространствакомпактов в евклидовом пространстве.В третьей главе доказываются оценки на суботношение Штейнерадля различных граничных множеств в евклидовой плоскости и евклидовом пространстве.В четвертой главе получены результаты, позволившие разработать иобосновать алгоритм машинного перебора для поиска возможного количества кратчайших кривых между двумя фиксированными компактамив метрическом пространстве компактов и приводятся его основные результаты.В приложении приводится исходный код программы, производящейпоиск возможного количества кратчайших.Библиография содержит 28 наименований.