Геометрия локально минимальных и экстремальных сетей в пространствах с нормами (1102759)
Текст из файла
Х1ОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА МЕХАНИКΠ— МАТЕМАТИНЕСКИЙ ФАКУЛЬТЕТ На правах рукописи Ильютко Денис Петрович УДК 514.77+517.982.22+519.711.72 ГЕОМЕТРИЯ ЛОКАЛЬНО МИНИМАЛЬНЫХ И ЭКСТРЕМАЛЬНЫХ СЕТЕЙ В ПРОСТРАНСТВАХ С НОРМАМИ 01.01.04 геометрия и топология ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико математических наук Научный руководитель: профессор, доктор физико- -математических наук, А.
А. Тужилин Москва 2005 Введение Задачи, связанные с изучением локально минимальных сетей, т.е. кратчайших в малом, и экстремальных сетей, т.е. критических точек функционала нормировйнной длины, строгое определение которых см. н1лже, пояВляются П1эи Оооощении следуюш"и клйссическои задй'1и. известной в литературе как проблема Штсйнера: среди всех сетей, затягивающит, донное конечное множество Х точек «вкяидовой плоскости« найти сеть наименьлией длины.
Решение этой задачи называется крат; чайиаей или абсолютно минимальной сетьн. затягивающей множество Х. Отметим., что с точки зрения римановой геометрии. локально минимальные сети являются естественным обобщением обычных геодезических. Действительно. локально минимальная сеть, затягиваюшая две произвольные точки на некотором римановом многообразии, представляет собой обычную геодезическую, т.е.
кратчайшую в малом кривую. Более подробньпл исторический обзор. посвященный проблеме Штейнера. можно найти в [4. 5, 25, 31]. Тр«ад11цллонно Оольше Внимйния уделяется изучени1о локйльно минимальных и кратчайших сетей. чем изучению экстремальных сетей. Это связано с тем.
что в случае функционала римановой длины, если раз- решено расщеплять вершины. классы локально минимальных и экстремальных сетей совпадают. см. [15]. В даннолл работе рассматриваются сети нй Л-нормированных плоскостях, т.е. на нормированных плоскостях (11Л'.. р1), для которых единичная окружность Е = 1х Е К $ рл(х) = 11 соВпйдйет с прйвильным 2Л-угольником, Одна из осси симметрии которого лежит на осп аосцисс. Важными отличиями этих норм1лрованных плоско- ст«и От стандартнои евклидовои плОскОсти являются Отсутствия гл««адкости единичной окружности Е п строгой выпуклости единичного круга, ограниченного Е.
Часто нормы, для которых единичная окружность Е является гладкой, называют гладкилли, а нормы, для которых единичный круг строго выпуклый строго вынзукяылли. Ока~ывается, на этих Л- нормированных плоскостях. ввиду отсутствия гладкости нормы. класс локально минллмальных сетей существенно шире класса экстремальных сетей. Первые работы, посвященные изучению проблемы Штейнера на нормированных плоскостях, появились в 60-е годы ХХ века, см. [6], в связи с оурным развитием электроники и робототехники. В 1966 г.
Ханан [8] провел исследование кратчатипх прямоугольных деревьев. т.е. кратчаиших сетей на 2-нормированной. так называемой манхеттенской. плоско- стп. и описал несколько важных общих геометрических свойств таких сетей. Он указал максимальную степень, которую могут иметь как вну- '1'РСННИС, '1'с)К И ГРННИ 1НЫС ВСРШИНЫ КРа'Г 1с1ИШСИ С1'ГИ Нс1 Мс1НХСТТСНСКО11 плоскости., а именно. что эта степень равна 4 для всех вершин. Так)ке Ха- нан показал.
что всегда существует кратчаишее прямоугольное дерево. которое является подмножеством 1)еи~еп)ни Ханинп множества всех вертикальных и горизонтальных прямых, проходящих через граничные точки. Позже Хванг [9] описал структуру некоторых кратчайших сетей на манхсттснской плоскости, но эффективный алгоритм. строящ1лй кратчайшую сеть, найти нс удалось.
В 1977 г. Гэри и Джонсон [7] показали,. что задача поиска кратчайшего прямоугольного дерева, затягивающего и, различных точек плоскости., является ХР-полной. Последнее означает., что, скорее всего, для этой проблемы нс существует полллномиального алгоритма, т.е. алгоритма, решающего задачу за время 0(11~), где Л некоторое фиксированное число. Тем не менее.
на практике приходится строить кратчайшие деревья, затягивающие большое количество точек плоскости, поэтому изучение ограничений на структуру кратчайших сетей является важным для приложений. Эти ограничения позволяют со- КращаТЬ набор П1)СТСНдСНТОВ На кратчайшую СЕТЬ. Нсаир1ЛМер, ХОРОШО известно, что степени вершин кратчайших сетей на стандартной евклидовой плоскости должны быть не больше 3, что существенно снижает перебор при построении кратчайшего дерева. Такие же эффекты можно получить, исходя из геометрии граничного множества.
Например. если в качестве граничного множества Л рассматривается правильный много- УсГОЛЬНИК, ТО ДЛЯ ТаКО1'О Л УДсн!'ГСЯ ПОЛУс1ИТЬ ПОЛНЫИ СПИСОК КРаТЧНИШИХ сетей, его затягивающих, см. [4]. Также имек)тся существенные продвижения и в задаче описания локально минимальных сетей. затягивак)щих Х, см. [13, 14. 35, 36].
В 90-х годах ХХ века проблемой Штейнера на нормированных плоскостях занимались многие ученые. Опишем некоторые важные результаты. касающиеся сетей на нормированных плоскостях. Рассмотрим вопрос о максимальной степени вершины. В случае., когда норма является гладкои и строго выпуклои. степень вершин нс превосходит 3, см. [1]. Как было отмечено выше, если мы откажемся от условий гладкости и строгой выпуклости нормы (как это имеет место. например, на манхеттенской плоскости), то степень вершин может быть больше 3. Рассмотрим нормированные плоскости, которые удовлетворяют только одному из обсуждаемых условий, т.е.
либо норма. является гладкой, либо строго выпуклой. Оказывается, что сущсству1от нормированные плоскости со строго выпуклой нормой и кусочно-гладкой единичной окружно- стью, на которых внутренние вершины кратчаиших сетей могут иметь степень 4, см. [1]. Заметим. что упомянутая выше манхеттенская плоскость не удовлетворяет условик) строгой выпуклости единичного крута. Лаулор и Морган [28] обобшили результаты, полу пенные в [1].
и показали, что на нормированных плоскостях с гладкой нормой и без условия ее строгои выпуклости степень внутреннеи вершины все равно не превосходит 3. Но в некоторых случаях условие строгой выпуклости нормы играет существенную роль при ограничении степени вершин. Если норма строго выпуклая, но не обязательно гладкая, то Альфаро и др. [1] показали, что степень внутренней вершины не больше 4, а Цислик в работе [2] доказал это ограничение для всех вершин.
Подводя итоги вышесказанного., мы можем заключить, что на нормированных плоскостях с гладкой нормой степени вершин не превосходят 3. а со строго выпуклой нормой 4. Более того, Цислик показал [2], что на нормированных плоскостях, не изометричных 3-но))ми1)ованной плоскости. степень вершин не может быть больше 5. Сванепол уточнил этот результат [32] и доказал, что на лн)бой нормированной плоскости степень внутренней вершины не превосходит 4, а. г$)анпчнои 6.
п))ичем граничив.я вершина. мо)кот иметь степень 5 или 6 только на плоскостях., изометричных 3-нормированной плоскости. Локальная структура локально мцнпмальных сетей на Л-нормированных плоскостях, .Л ~ 2, т.е. возможные степени вершин и углы ме кду сме кными ребрами, была описана Саррафзаде и Вонгом [30]. а также 1и и Шеном Щ. Но в этих двух работах описание было не полным., так как отсутствовали некоторые возмокные структуры вершин ст~ пени 3 для 2Л = 0 (шос1 3). Полный же ответ был независимо получен Сванеполом [32] и автором настояшей диссертации [18].
Отметим, что проблемой Штейнера занимались многие известные математики, такие как Винтер, Гилберт, Гильдебрандт, Грехем. Гэри, Джонсон. Ду, Иванов. Кокейн, Мантуров, Мелзак, Морган, Поллак, Рубинштейн. Смит, Томас, Тужилин. Фоменко, Ханан. Хванг, Цислик и другие Одна из причин этого неослаоевак)щего инте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}
