Связь вида нормы и геометрии минимальных сетей (1104796)
Текст из файла
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИМ.В. ЛОМОНОСОВАМЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТна правах рукописиУДК 514.77, 519.176, 517.982.22ЛАУТ ИЛЬЯ ЛЕОНИДОВИЧСВЯЗЬ ВИДА НОРМЫ И ГЕОМЕТРИИ МИНИМАЛЬНЫХ СЕТЕЙ01.01.04 — геометрия и топологиядиссертация на соискание ученой степеникандидата физико-математических наукНаучный руководитель:Доктор физико-математических наук А.О. ИвановМосква – 20162СодержаниеВведение13Различимость нормированных пространств по устройству кратчайших и по точкам Ферма81.1Необходимые определения .
. . . . . . . . . . . . . . . . . . . . . . .81.2Различимость нормированных пространств по устройству кратчайших81.3Различимость нормированных пространств по местоположению точек Ферма. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112 Различимость нормированных пространств по устройству минимальных сетей Штейнера212.1Необходимые определения и предварительные результаты . .
. . .212.2Достаточное условие гомотетичности норм . . . . . . . . . . . . . .393 Минимальные параметрические сети47Заключение54Список литературы553Введение.Диссертация посвящена изучению связи между видом нормы и геометрией минимальных сетей в нормированных пространствах. Большинство задач, исследуемыхв диссертации, являются частными случаями следующей общей постановки вопроса. Пусть дана некоторая информация о геометрии минимальных сетей Штейнерав нормированном пространстве. Требуется узнать, что тогда можно сказать просаму норму.Неформально, сетью в метрическом пространстве называется набор кривых(будем называть их ребрами сети), некоторые из которых имеют общие концы. Будем говорить, что сеть соединяет граничное множество M точек, если, во-первых,M лежит в множестве концов ребер сети, и, во-вторых, можно перейти между любыми точками граничного множество, проходя по ребрам сети.
Длина сети естественным образом определяется как сумма длин ее ребер. Сеть минимальной длины, соединяющая данное граничное множество, называется минимальной сетьюШтейнера этого граничного множествам.Впервые формулировку задачи, равносильной задаче поиска минимальной сетиШтейнера для трех точек на евклидовой плоскости, предложил Пьер Ферма (см.[1]). Ответом к задаче является сеть из трех отрезков, соединяющих данные точкис точкой, называемой точкой Ферма. Если у треугольника с вершинами в данныхточках все углы меньше2π,3то точка Ферма — это такая (единственная) точка, изкоторой все стороны треугольника видны под угломесть угол, больший либо равный2π,32π.3Если же в треугольникето точка Ферма совпадает с вершиной этогоугла, а один из отрезков вырождается в точку.
Обзор проблематики, связанной сточкой Ферма, можно найти в [10].В 1934 году Ярник и Кесслер сформулировали задачу поиска минимальнойсети Штейнера для произвольного числа точек на евклидовой плоскости (см. [2]);по традиции эта задача называется задачей Штейнера. Есть простая практическаяинтерпретация этой задачи: представим, что имеется несколько городов, и требует-4ся построить сеть дорог, чтобы из каждого города можно было доехать в каждый.Собственно, самым коротким (и, как правило, самым дешевым) вариантом будетминимальная сеть Штейнера.Имеются и другие практические задачи, сводящиеся к решению задачи Штейнера, такие как поиск наиболее вероятных эволюционных цепочек в филогенетических пространствах или трассировка микросхем.
Одной из задач оптимальнойтрассировки микросхем является минимизация длины дорожек проводника (здесьвидно сходство с интерпретацией про дороги и города). Но в случае разводки микросхем присутствует ограничения на множество направлений, в которых могутпрокладываться дорожки. В частности, если возможно прокладывать только вертикальные и горизонтальные отрезки, то задача минимизации длины дорожек проводника становится задачей Штейнера на плоскости с `1 -нормой, также называемой манхэттенской нормой: k(x, y)k1 = |x| + |y|.Первые работы по изучению минимальных сетей Штейнера в нормированныхплоскостях появились в шестидесятыx годаx XX века.
В статьях [4, 9, 14, 15, 16]можно найти подробную историческую справку по данному вопросу.Хорошо известно, что в некоторых нормированных пространствах кратчайшаялиния, соединяющая две точки, не всегда единственна. Рассмотрим, например,двумерную манхэттенскую плоскость `21 . Для точек (0, 0) и (1, 1), расстояние между которыми равно 2, любая непрерывная кривая с параметром t такая, что x(t)и y(t) — монотонно неубывающие функции x(0) = y(0) = 0, x(1) = y(1) = 1 ,имеет длину 2. С другой стороны, для обычной евклидовой плоскости кратчайшая всегда единственна.
Соответственно, манхэттенская и евклидова плоскостиразличимы по тому, какие кратчайшие кривые в них возможны. Однако, по видувозможных кратчайших можно различить между собой лишь некоторые нестроговыпуклые нормы (см. критерий 1.1). Для любой же строго выпуклой нормы верно,что кратчайшая между двумя точками единственна и является прямолинейнымотрезком между ними. Возникает естественный вопрос: нельзя ли использоватьобобщение понятия кратчайшей для более детальной классификации нормирован-5ных пространств? В главе 1 изучается возможность различать нормы c точностьюдо гомотетии по устройству кратчайших сетей на трех точках. Две нормы будемназывать F3 -неразличимыми, если все кратчайшие сети на трех точках выглядят вних одинаково (строгое определение см. в разделе 1.3).
Оказывается, существуютнормы на двумерной плоскости, F3 -неразличимые с евклидовой нормой и отличныеот нее (см. теорему 1.1). При этом, в размерности больше двух евклидова нормаявляется в этом смысле уникальной (это прямое следствие из основной теоремыработы [7], приведенной здесь как теорема 1.3)Из теоремы 1.1 следует, что знать положения точек Ферма всех троек точекнедостаточно для того, чтобы отличить, например, евклидову норму от некоторыхдругих двумерных норм.
Естественным образом встает вопрос: можно ли гарантированно отличать друг от друга нормы, имея больше информации о них, а именно— основываясь на устройстве всех кратчайших сетей на всех конечных множествах точек? Теорема 2.5 положительно отвечает на этот вопрос в случае строговыпуклых дифференцируемых норм на плоскости.Результаты главы 3 продолжают изучение минимальных параметрических сетей и их деформаций, проведенное в [4]. Рассматривается случай границ, порождающих единственную невырожденную минимальную параметрическую сеть в данной двумерной строго выпуклой дифференцируемой норме.
Приводится альтернативное доказательство единственности минимальной параметрической сети дляграниц из малой окрестности границы рассматриваемого типа (этот факт впервыесформулирован и доказан в [4]), а также доказывается непрерывность координатподвижных вершин и естественность направления поворота при деформации границы рассматриваемого типа в ее малой окрестности (лемма 3.4 и теорема 3.1).Структура работыРабота состоит из введения, двух глав, заключения и списка литературы.6Список основных результатов, выносимых на защитуРезультаты диссертации являются новыми.
В диссертации получены следующиеосновные результаты:(1) Получено достаточное условие F3 -неразличимости данной нормы и евклидовой нормы на двумерной плоскости (см. теорему 1.1), а также необходимоеусловие этого для более узкого класса норм (см. теорему 1.2).(2) Получено достаточное условие гомотетичности двух норм в терминах минимальных сетей Штейнера (см. теорему 2.5).(3) Получены доказательства непрерывности координат подвижных вершин иестественности направления поворота при деформации границы рассматриваемого типа в ее малой окрестности (лемма 3.4 и теорема 3.1) для минимальныхпараметрических сетей в случае строго выпуклых норм.Методы исследованияВ диссертации применяются методы дифференциальной и метрической геометрии,геометрии нормированных пространств, топологии, теории графов, математического анализа.Апробация работыРезультаты диссертации докладывались на следующих семинарах и конференциях:• на семинаре «Оптимальные сети» под руководством профессора А.
О. Иванова и профессора А. А. Тужилина (МГУ, 2010 — 2014 г.г.)• на международных конференциях «Ломоносов» (МГУ, 2014 и 2015 г.г.)• на международных конференциях «Александровские чтения» (МГУ, 2012 и2016 г.г.)7• на семинаре «Геометрический анализ и вычислительная геометрия» в Волгоградском Государственном Университете, 2016 г.• на семинаре кафедры математического анализа в ЯрГУ им. П.Г. Демидова,2016 г.ПубликацииОсновное содержание диссертации опубликовано в работах [17], [18], [19], [20]и [21], первые две — в журналах из перечня ВАК (для работы [17] в переченьвходит версия журнала на английском языке).БлагодарностиАвтор выражает глубокую благодарность своему научному руководителю А. О.Иванову и профессору А.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
