Геометрия минимальных сетей в пространствах ограниченной кривизны в смысле А.Д. Александрова тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

ФГБОУ ВО "МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА"

На правах рукописи

Завальнюк Евгений Анатольевич

ГЕОМЕТРИЯ МИНИМАЛЬНЫХ СЕТЕЙ В ПРОСТРАНСТВАХ ОГРАНИЧЕННОЙ КРИВИЗНЫ В СМЫСЛЕ А.Д. АЛЕКСАНДРОВА

Специальность 01.01.04 - геометрия и топология

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

1 7 АВГ т

005561412

Москва - 2015

005561412

Работа выполнена на кафедре дифференциальной геометрии и приложений Механико-математического факультета ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова"

Научный руководитель:

Иванов Александр Олегович,

доктор физико-математических наук, профессор

Официальные онноненты:

Берестовский Валерий Николаевич,

доктор физико-математических наук, в.н.с. (ФГБУН Институт математики им. С.Л. Соболева СО РАН, лаборатория геометрического анализа)

Стрелкова Наталия Павловна,

кандидат физико-математических наук, учитель математики (ГБОУ "Школ! №171", структурное подразделение 15 "Школа №54")

Ведущая организация:

ФГАОУ ВПО "Волгоградский государственный университет"

Защита диссертации состоится 9 октября 2015 г. в 16 ч. 45 мин. на заседании диссертационного совета Д 501.001.84 на базе ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова", по адресу: 119991, Москва, ГСП-1, Ленинские горы, д. 1, ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова", Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментально:! библиотеке ФГБОУ ВО "Московский государственный университет имени М.В. Ломоносова" по адресу: Москва, Ломоносовский проспект, дом 27, сектор А, http://mech.math.msu.su/~snark/index.cgi, http://istina.msu.ru/dissertations/9624993.

Автореферат разослан 9 сентября 2015 г. У 0 /

Ученый секретарь диссертационного совета Д.501.001.84 на базе ФГБОУ ВО МГУ им. М.В.Ломоносова А. С. Иванов

доктор физико-математических наук, профессор

Общая характеристика работы Актуальность темы

Простейший вариант проблемы Штейнера, известный как задача Ферма, был решен в XVII веке Б. Кавальери и Э. Торичелли. В 1836 г. К. Гаусс1 затрагивает данную проблему, решая практическую задачу проектирования железной дороги, соединяющей четыре немецких города. В XX веке благодаря работе Р. Куранта и Г. Робинса2 проблема Штейнера получила широкую известность.

Проблема Штейнера формулируется следующим образом: в данном метрическом пространстве соединить конечный набор точек посредством графа таким образом, чтобы сумма длин его ребер (расстояний между его концами) была наименьшей. Если такой граф существует, то непременно является деревом, называемым деревом Штейнера. В нем точки соединяемого множества называются граничными, кроме них дерево также может содержать дополнительные вершины, называемыми точкалш Штейнера.

В пространствах со строго внутренней метрикой, также именуемых геодезическими пространствами, деревья Штейнера реализуются в виде минимальных сетей (т.е. разветвленных геодезических). Интерес к проблеме Штейнера особенно актуален в настоящее время в связи с активным развитием транспортной инфраструктуры, компьютерных сетей, а также анализа молекулярных структур.

Задача поиска минимальных сетей для большинства известных пространств является NP-трудной.3 NP-трудность обусловлена большим количеством структур деревьев, соединяющих конечный набор точек. Наличие точек Штейнера также является одной из причин комбинаторного взрыва. Изучение локальных свойств минимальных сетей позволяет говорить о глобальных свойствах, способных существенно сократить перебор структур. Для некоторых классов пространств с внутренней метрикой, в которых корректно говорить об углах между кратчайшими, одним из таких свойств является принцип 120 градусов — утверждение, что угол между смежными ребрами-отрезками минимальной сети в их общей вершине больше или равен 120°.

Первый систематический анализ минимальных сетей был осуществлен

'Gauss С.F. Briefwechsel Gauss Schumacher, в книге» Werke Bd. X, 1, pp. 459 - 4G8, Güttingen, 1917.

2Курант. P., Робине. Г. Что такое математика? : Элементарный очерк идей и методов, 3-е изд., испр. и доп., M., МЦНМО, 2001.

3Prömcl H.J., Stcger A. The Steiner tree problem: A tour through graphs, algorithms, and complexity, first edition. Vieweg, Braunschwcig. 2002.

в работе Э. Джилберта и Г. Поллака.4 Также изучались сете на сфере (А. Хенпес5), на гиперболических плоскостях (А. Эдмондс, Д. Эвинг, Р. Кулкарни6), на римановых многообразиях (А.О. Иванов, A.A. Тужи-лин7) и в нормированных пространствах (А.О. Иванов, A.A. Тужилин8 и К. Сваненоел9).

Наряду с минимальными сетями изучают также локально мин шальные сети, являющиеся минимальными в некоторой окрестности каждой своей точки. Любая минимальная сеть является локально минимальной, поэтому оказывается полезным выявление необходимых и достаточных условий локальной минимальности сети. А.О. Иванов и A.A. Тужилин10 показали, что для римановых многообразий следующие условия являются критерием локальной минимальности: (1) ребра сети суть отрезки геодезичзских; (2) вершины степени 1 принадлежат границе сети; (3) если некоторая вершина степени 2 не является граничной, то она принадлежит геодезической, соединяющей смежные с ней вершины; (4) угол между смежными ребрами сети больше или равен 120°.

По мере изучения нормированных пространств стало понятно, что локально минимальные сети не обязательно являются минимумами функционала длины, поэтому нужно также изучать экстремальные, или критические сети. Сеть называется экстрелшлъной для некоторого класса деформаций, если она является кратчайшей в классе этих деформаций. А.О. Иванов, A.A. Тужилин и В.Л. Хонг11 получили необходимые и достаточные условия экстремальности для сетей в пространстве R2 с манхеттен-ской нормой относительно параметрических деформаций.

Отдельное внимание было уделено исследованию экстремальных сетей на нормированных плоскостях, в которых единичная окружность представляет собой правильный 2А-угольник. Такие нормированные плоскости получили название Х-нормированных плоскостей. Полное описание локально

4Gilbert Е. N., Pollak Н. О. Steiner minimal trees. SIAM J. Appl. Math. 1968. 16, № 1, pp. 1-29.

5Heppes. A. Isogonal spherischen Netze. Ann. Univ. Sei., Budapest, Sect. Math. 1964. 7, pp. 41-48.

"Edmonds A. L., Ewing. J. H., Kulkarni R. S. Regular tessellations of surfaces and (p,q,2)-triangle groups. Ann. Math. 1082. 166, pp. 123-132.

7Пванов А. О., Тужилин А. А. Теория экстремальных сетей. Москва, Ижевск, Институт компьютерных исследований, 2003.

8Иванов А. О., Тужилин А. А. Разветвленные геодезические в нормированных пространствах. Изв. РАН. Серия матем. 2002. 66, № 5, сс. 33-82.

"Swanepoel К. J. The Local Steiner Problem in Normed Planes. Networks. 2000. 36, pp. 104-113.

'"Иванов А. О., Тужилин А. А. Геометрия минимальных сетей и одномерная проблема Плато. Успехи матем. наук. 1992. 47, № 2, сс. 53-115.

"Иванов А. О., Хонг В. Л., Тужилин А. А. Плоские сети, локально минимальные и критические д.ия манхэттенского функционала длины. Зап. научн. сем. ПОМИ. 2001. 279, сс. 111-140.

минимальных сетей для любого А получено в работах К. Сванепоела12 и Д.П. Ильютко.13 В нормированных плоскостях при А = 2,3,4,6 могут возникать точки Штейнера степени 4. К. Сванепоел показал, что только при вышеупомянутых А возникают точки Штейнера степени 4. Д.П. Илыотко получил критерий экстремальности сети на A-нормированной плоскости при А = 5 и А > 6.

Общие пространства ограниченной кривизны в смысле А. Д. Александрова, являются естественным обобщением поверхностей ограниченной гауссовой кривизны, и в них корректно определены углы между кратчайшими. С точки зрения минимальных сетей пространства Александрова стали изучать недавно, хотя случай поверхностей многогранников рассматривался А.О. Ивановым и A.A. Тужилиным.14'15.

Н. Иннами и С. Найя16 показали, что принцип 120 градусов имеет место для пространств с кривизной, ограниченной снизу.

В работах Н.П. Стрелковой17'18,19,20 исследовались минимальные сети на поверхностях выпуклых многогранников и в пространствах Александрова неположительной кривизны (так называемых САТ(О)-пространствах). Были найдены необходимые условия существования замкнутых минимальных сетей на поверхностях выпуклых многогранников, а также описаны некоторые классы многогранников, на которых такие сети существуют. Была доказана устойчивость локально минимальных сетей в САТ(О)-пространствах.

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

12Swanepoel К. J. The Local Steiner Problem in Normed Planes. Networks. 2000. 36, pp. 104-113.

13Ильютко Д. II. Локально минимальные сети в N-нормированных пространствах. Матем. заметки. 2003. 74, № 5, ее. 657-669.

14Иванов А. О., Тужнлин А. А. Геометрия минимальных сетей и одномерная проблема Плато. Успехи матем. наук. 1992. 47, № 2, ее. 53-115.

15Иванов А. О., Тужилин А. А. Теория экстремальных сетей. Москва, Ижевск, Институт компьютерных исследований, 2003.

16Innami N., Naya S. A comparison theorem for Steiner minimum trees in surfaces with curvature bounded below. Tohoku Mathematical Journal. 2013. 65, № 1, pp. 131-157.

17Стрелкова Н.П. Реализация плоских графов как замкнутых локально минимальных сетей на выпуклых многогранниках. Доклады РАН. 2010. 435, ЛГ| 4, сс.1-3

18Стрелкова Н. П. Замкнутые локально минимальные сети на поверхностях тетраэдров. Матем. сб. 2011. 202, № 1, сс. 141-160.

10Стрелкова Н. П. Замкнутые локально минимальные сети на поверхностях выпуклых многогранников. Моделирование и анализ информационных систем. 2013. 20, К< 5, сс. 116-145.

Стрелкова Н.П. Устойчивость локально минимальных сетей. Труды семинара по векторному и тензорному анализу с их приложениями к геометрии, механике и физике. 2013, 29, сс. 148-170.

ной ошибки приближения кратчайшего дерева минимальным оетовным в данном пространстве.

Изучение отношения Штейнера метрических пространств естественно началось с евклидовой плоскости, для которой хорошо известна верхняя оценка sr(R2) < л/3/2, равная отношению Штейнера вершин равностороннего треугольника. В 1968 г. Э. Джилберт и Г. Поллак сформулировали гипотезу о том, что отношение Штейнера евклидовой ш.оскости в точности равно \/3/2. С тех нор гипотеза была доказана для п-точсчных множеств при п — 4 (Г. Поллак21, Д. Ду, Ф. Хванг и Е. Яо22), п = 5 (Д. Ду, Ф. Хванг и Е. Яо23), п = 6 (Й. Рубинштейн и Д. Томас24), п = 7 (П.О. де Вет25), а также были получены некоторые нижние оценки, близкие к V3/2. В 1992 г. Д. Ду и Ф. Хванг опубликовали доказательство гипотезы Джилберта-Поллака. Доказательство содержало пробелы, на которые указывали разные специалисты26, таким образом, вопрос о точном значении отношения Штейнера евклидовой плоскости до сих пор остается открытым.

Для произвольного метрического пространства X справедлива оценка на его отношение Штейнера: 1/2 < sr(X) < 1, причем все промежуточные значения достигаются.

Существует лишь немного классов пространств, для которых удалось точно вычислить отношение Штейнера, хотя часто удается найти некоторые оценки. А.О. Иванов, А.А. Тужилин и Д. Цислик27 показали, что если X — произвольное тг-мерное риманово многообразие, то sr(X) < sr(Rn). В частности, при п > 2 получается sr(X) < \/3/2. Р. Грэм и О. Хванг28 получили нижнюю оценку на отношение Штейнера n-мерного эвклидова пространства: sr(Rn) > 1/V3.

Б. Гао, Д. Ду и Р. Грэм29 получили оценку для отношения Штейнера

2IPoIlak. Н.О. Some remarks on the Steiner Problem. J. Combin. Theory, Ser. A. 1978. 24, pp. 278 - 295.

22Du D.Z., Yao E.Y. and Hwang F.K. A Short Proof of a Result of Pollak on Steiner Mi.iimal Trees. J. Combin. Theory, Ser. A. 19S2. 32, pp. 396 - 400.

23Du D.Z., Hwang F.K. and Yao E.N. The Steiner ratio conjecture is true for five points. J. Combin. Theory. Ser. A. 1985. 38, pp. 230 - 240.

24Rubinstein J.H. and Thomas. D.A. The Steiner Ratio conjecture for six points. J. Combia. Theory, Ser. A. 1991. 58, pp. 54 - 77.

25De Wet P.O. Geometric Steiner Minimal Trees. Dissertation for the degree of Doctor of Philosophy, University of South Africa. 2008.

2eIvanov A., Tuzhilin A. The Steiner ratio Gilbert-Pollak conjecture is still open. Algorithmica. 2012. 62, №1-2, pp. 630-632.

"Иванов А. О., Тужилин А. А., Цислик Д. Отношение Штейнера для римановых многообразий. Успехи матем. наук. 2000. 55, »6, сс. 13М40.

28Graham R. L., Hwang F. К. A remark on Steiner minimal trees. Bull, of the Inst, of Mf.th. Ac. Sinica. 1976. 4, pp. 177-182.

29Gao В., Du D. Z., Graham R. L. A tight lower bound for the Steiner ratio in Minkowski planes. Discrete Mathematics. 1995. 142, pp. 49-C3.

плоскостей Банаха-Мннковского: sr(£2) > 2/3, причем если единичный шар В на С2 представляет собой параллелограмм, то в формуле имеет место равенство. Д. Цислик30 получил ряд оценок для отношения Штейнера пространств Банаха-Минковского большей размерности.

Известны немного классов пространств, для которых отношение Штейнера равно 1/2. Таковыми являются, в частности, филогенетические пространства. Н. Иннами и Б. Ким31 показали, что таковыми являются поверхности постоянной отрицательной гауссовой кривизны. З.Н. Овсянниковым32 было показано, что отношение Штейнера для пространства компактов в евклидовом пространстве с метрикой Хаусдорфа также равно 1/2.

Цель работы.

Настоящая работа посвящена развитию теории минимальных сетей применительно к пространствам Александрова. Целью работы является исследование локальной структуры минимальных сетей в пространствах Александрова и вычисление отношения Штейнера для определенного класса полных односвязных поверхностей Александрова неположительной кривизны (называемых также поверхностями Адамара).

Научная новизна.

Все основные результаты являются новыми, получены автором самостоятельно н заключаются в следующем:

1. Доказан принцип 120 градусов для минимальных сетей в пространствах ограниченной сверху кривизны в смысле А.Д. Александрова.

2. Предложен новый способ вычисления отношения Штейнера поверхностей постоянной отрицательной гауссовой кривизны, допускающий непосредственные обобщения на более широкие классы поверхностей.

3. Вычислено отношение Штейнера для неограниченных поверхностей Адамара кривизны не больше к < 0.

30Cieslik D. The Steiner ratio of C\k. Discrete Applied Mathematics. 1999. 95, pp. 217-221.

31Innami N., Kim В. H. Steiner ratio for hyperbolic surfaces. Proc. Japan Acad. 2006. 82, Ser. A.

З20всяшгаков 3. H. Отношения Штейнера, Штейнера-Громова и суботнтиения Штейнера для пространства компактов в евклидовой плоскости с расстоянием Хаусдорфа. Фундамент, и прикл. мат. 2013. 18, № 2, сс. 157-1С5.

Методы исследования.

В диссертации применяются методы метрической, дискретной и дифференциальной геометрии, также методы теории графов, вариационного исчисления, методы теории минимальных сетей. Используются классические модели поверхностей постоянной гауссовой кривизны и методы сравнения их геометрии с внутренней геометрией пространств Александрова.

Теоретическая и практическая ценность работы.

Диссертация имеет теоретический характер. Полученные в диссертации результаты представляют интерес для специалистов по метрической геометрии, дискретной математике, теории минимальных сетей, геометрическим вариационным задачам и теории пространств ограниченной криьизны.

Апробация работы.

Результаты диссертации докладывались на следующих научно-исследовательских семинарах и научных конференциях:

1. семинаре кафедры «Алгебра и геометрия» Рурского Университета (г. Бохум, Германия, 7 февраля 2013 года)

2. научной конференции «Ломоносовские чтения» (МГУ, 22 апреля 2013 года)

3. семинаре летней школы международной лаборатории «Дискретная и вычислительная геометрия» им. Б. Н. Делоне (Ярославль-Демино, 31 июля 2013 года.)

4. международной конференции «Воронежская зимняя математическая школа С. Г. Крейна» (г. Воронеж, 28 января 2014 года)

5. семинаре «Дифференциальная геометрия и приложения» под руководством академика А. Т. Фоменко (МГУ, 17 февраля 2014 года)

6. семинаре «Узлы и теория представлений» (МГУ, 25 марта 2014 года)

7. семинаре «Экстремальные сети» под руководством профессоров А. О. Иванова и А. А. Тужилина (МГУ, 2008 - 2013 гг.)

Публикации.

Основные результаты диссертации опубликованы в 4 работах [1-4], две из них в журналах из перечня ВАК. Список работ приведен в конце автореферата.

Структура и объем диссертации.

Работа состоит из введения, трех глав и списка литературы. Текст диссертации изложен на 53 страницах и содержит 4 рисунка. Слисок литературы включает 45 наименований.

Краткое содержание работы

Во введении к диссертации излагается история рассматриваемой проблемы, формулируются основные результаты, приводится краткое описание работы.

Содержание главы 1

Первая глава носит вводный характер. В ней вводятся необходимые определения и перечисляются известные результаты. Приводятся примеры пространств ограниченной кривизны и примеры пространств с известными оценками и точно вычисленными значениями отношения Штейнера.

Содержание главы 2

Во второй главе приводятся достаточные условия существования минимальных сетей в пространствах Александрова и исследуется их локальная структура. Формулируются и доказываются некоторые свойства сферических треугольников.

Н. Иннами и С. Найя33 показали, что для минимальных сетей в пространствах Александрова ограниченной снизу кривизны справедлив принцип 120 градусов: угол между соседними ребрами сети больше или равен 27г/3. Данный результат допускает обобщение на весь класс пространств Александрова.

33Innami N., Naya S. A comparison theorem for Steiner minimum trees in surfaces with curvature bounded below. Tohoku Mathematical Journal. 2013. 65, № 1, pp. 131-157.

Теорема 1. Пусть X — пространство Александрова и Г — минимальная сеть в X. Тогда для любых двух ребер в Г, имеющих общую вершину, угол между ними в этой вершине больше или равен 27г/3.

Доказательство теоремы осуществляется путем сравнения расстояний в треугольниках пространства Александрова с расстояниями в соответствующих треугольниках на поверхности сравнения. При этом используются известные свойства точек Штейнера на римановых многообразиях, а именно, ее степень равна 3 и все три угла при ней равны 2w/3.

Следствие 1. Пусть (X,d) — пространство Александрова и Г — минимальная сеть в X. Тогда Г удовлетворяет следующим свойствам

(1) Ребра сети являются кратчайшими в X.

(2) Вершины степени 1 принадлежат границе сети.

(3) Угол между смежными ребрами сети в их общей вершине не меньше, чем 2ж/2>.

(4) Число точек Штейнера не превосходит п — 2.

Вопрос о том, являются ли условия (1) - (4) достаточными для локальной минимальности сети, остается открытым.

Содержание главы 3

В третьей главе рассматриваются поверхности Александрова. Исследуется полный угол, в точках поверхности. Показывается, что в случае неположительной кривизны его величина не меньше, чем 2я\ Как следствие, в классе поверхностей неположительной кривизны могут возникать точки Штейнера сколь угодно большой степени.

Исследуется важный класс поверхностей Александрова — неограниченные поверхности Адамара с кривизной < к < 0. Они являются обэбщением гиперболических поверхностей. Н. Иннами и Б. Ким34 вычислил ! отношение Штейнера гиперболических плоскостей. Оно оказалось равным 1/2.

Далее вводится конструкция бесконечной "звезды" на поверхности постоянной кривизны. Оказалось, что эта конструкция допускает обобщение на случай неограниченных поверхностей Адамара отделенной от нуля кривизны, что позволило вычислить отношение Штейнера для таких поверхностей.

34Innami N., Kim В. H. Steiner ratio for hyperbolic surfaces. Proc. Japan Acad. 2006. 82, !!er. A.

Теорема 2. Отношение Штейнера неограниченной поверхности Адамара кривизны < к < 0 равно 1/2.

Благодарности

Автор выражает глубокую благодарность своему научному руководителю д.ф.-м.н., профессору Александру Олеговичу Иванову за постановку задач и неоценимую помощь во время работы над диссертацией. Автор благодарен д.ф.-м.н., профессору Алексею Августиновичу Тужилину за постоянный интерес, советы и многочисленные обсуждения.

Автор признателен участникам семинара ''Экстремальные сети" за полезные замечания, комментарии и дискуссии. Автор глубоко признателен всему коллективу кафедры дифференциальной геометрии и приложений Механико-математического факультета МГУ за творческую атмосферу, постоянную поддержку и внимание.

Работа выполнена iipn поддержке проекта №477 базовой части государственного задания на НИР ЯрГУ.

Список публикаций по теме диссертации

[1] Завальнюк Е. А. Отношение Штейнера поверхностей Адамара кривизны не больше к < 0. Фундамент, и прикл. мат. 2013. 18, № 2, сс. 35-51.

[2] Завальнюк Е. А. Локальная структура минимальных сетей в пространствах Александрова. Вестн. Моск. ун-та. Сер. 1. Математика, механика. 2014. 69, № 5, сс. 54-58.

[3] Завальнюк Е. А. Поверхности Адамара и их отношение Штейнера. Материалы международной конференции «Воронежская зимняя математическая школа С. Г. Крейна — 2014», с. 132-133.

[4] Zavalnyuk Е. Steiner Ratio for Hadamard Surfaces of Curvature at Most k < 0. J. of Math. Sei. 2014. 203, № 6, pp. 777-788.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж¡60экз. Заказ № 23