Геометрия минимальных сетей в пространствах ограниченной кривизны в смысле А.Д.Александрова Завальнюк Евгений Анатольевич

Содержание к диссертации

Введение

1 Определения и предварительные результаты 12

1.1 Пространства ограниченной кривизны 12

1.1.1 Определения и свойства 12

1.1.2 Примеры пространств ограниченной кривизны 16

1.2 Проблема Штейнера 21

1.2.1 Деревья Штейнера и отношение Штейнера 21

1.2.2 Минимальные сети 24

1.2.3 Локально минимальные сети 25

2 Локальная структура минимальных сетей в пространствах ограниченной кривизны 26

2.1 Достаточное условие существования минимальных сетей 26

2.2 Теорема о локальной структуре минимальных сетей в пространствах с кривизной, ограниченной сверху

2.2.1 Вспомогательные леммы о треугольниках на сфере 27

2.2.2 Доказательство теоремы 31

2.2.3 Следствия 34

3 Отношение Штейнера поверхностей Адамара 36

3.1 Поверхности Александрова и поверхности Адамара 36

3.1.1 Продолжимость кратчайших на поверхностях Адамара 38

3.1.2 Полный угол на поверхностях Адамара 40

3.1.3 Пример точек Штейнера сколь угодно большой степени 40

3.2 Теорема об отношении Штейнера неограниченных поверхно стей Адамара кривизны к 0 42

3.2.1 Частный случай: гиперболические плоскости 42

3.2.2 Доказательство теоремы 47

Литература 50

• Примеры пространств ограниченной кривизны
• Деревья Штейнера и отношение Штейнера
• Теорема о локальной структуре минимальных сетей в пространствах с кривизной, ограниченной сверху
• Полный угол на поверхностях Адамара

Введение к работе

Актуальность темы

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

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

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

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

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

¹Gauss C.F. Briefwechsel Gauss Schumacher, в книге: Werke Bd. X, 1, pp. 459 - 468, Gottingen, 1917.

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

³Promel H.J., Steger A. The Steiner tree problem: A tour through graphs, algorithms, and complexity, first edition. Vieweg, Braunschweig. 2002.

в работе Э. Джилберта и Г. Пол лака.⁴ Также изучались сети на сфере (А. Хеппес⁵), на гиперболических плоскостях (А. Эдмондс, Д. Эвинг, Р. Кулкарни⁶), на римановых многообразиях (А.О. Иванов, А.А. Тужи-лин⁷) и в нормированных пространствах (А.О. Иванов, А.А. Тужилин⁸ и К. Сванепоел⁹).

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

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

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

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

⁵Heppes. A. Isogonal spherischen Netze. Ann. Univ. Sci., 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. 1982. 166, pp. 113-132.

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

⁸Иванов А. О., Тужилин А. А. Разветвленные геодезические в нормированных пространствах. Изв. РАН. Серия матем. 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.

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

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

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

В работах И.П. Стрелковой¹⁷'¹⁸'¹⁹'²⁰ исследовались минимальные сети на поверхностях выпуклых многогранников и в пространствах Александрова неположительной кривизны (так называемых CAT(0)-пространствах). Были найдены необходимые условия существования замкнутых минимальных сетей на поверхностях выпуклых многогранников, а также описаны некоторые классы многогранников, на которых такие сети существуют. Была доказана устойчивость локально минимальных сетей в САТ(О)-пространствах.

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

¹²Swanepoel К. J. The Local Sterner Problem in Normed Planes. Networks. 2000. 36, pp. 104-113.

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

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

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

¹⁶Innami N., Naya S. A comparison theorem for Steiner minimum trees in surfaces with curvature bounded below. Tohoku Mathematical Journal. 2013. 65, № i_{; pp}. 131-157.

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

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

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

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

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

Изучение отношения Штейнера метрических пространств естественно началось с евклидовой плоскости, для которой хорошо известна верхняя оценка sr(IR²) < л/3/2, равная отношению Штейнера вершин равностороннего треугольника. В 1968 г. Э. Джилберт и Г. Поллак сформулировали гипотезу о том, что отношение Штейнера евклидовой плоскости в точности равно \/3/2. С тех пор гипотеза была доказана для п-точечных множеств при п = 4 (Г. Поллак²¹, Д. Ду, Ф. Хванг и Е. Яо²²), п = 5 (Д. Ду, Ф. Хванг и Е. Яо²³), п = 6 (Й. Рубинштейн и Д. Томас²⁴), п = 7 (П.О. де Вет²⁵), а также были получены некоторые нижние оценки, близкие к л/3/2. В 1992 г. Д. Ду и Ф. Хванг опубликовали доказательство гипотезы Джилберта-Поллака. Доказательство содержало пробелы, на которые указывали разные специалисты²⁶, таким образом, вопрос о точном значении отношения Штейнера евклидовой плоскости до сих пор остается открытым.

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

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

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

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

²²Du D.Z., Yao E.Y. and Hwang F.K. A Short Proof of a Result of Pollak on Steiner Minimal Trees. J. Combin. Theory, Ser. A. 1982. 32, pp. 396 - 400.

²³Du 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.

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

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

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

²⁷Иванов А. О., Тужилин А. А., Цислик Д. Отношение Штейнера для римановых многообразий. Успехи матем. наук. 2000. 55, №6, ее. 139-140.

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

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

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

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

Цель работы.

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

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

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

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

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

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

³⁰Cieslik D. The Steiner ratio of L^d_2k. Discrete Applied Mathematics. 1999. 95, pp. 217-221.

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

³²Овсянников 3. H. Отношения Штейнера, Штейнера-Громова и суботношения Штейнера для пространства компактов в евклидовой плоскости с расстоянием Хаусдорфа. Фундамент, и прикл. мат. 2013. 18, № 2, ее. 157-165.

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации.

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

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

Примеры пространств ограниченной кривизны

Кривой в метрическом пространстве X называется непрерывное отображение некоторого отрезка [а, /3] в X. Длина кривой определяется как точная верхняя грань длин всех вписанных в кривую ломаных. Если у кривой длина конечна, то она называется спрямляемой.

Метрика d метрического пространства (X, d) называется внутренней, если расстояние i(a, Ь) между произвольными точками а, Ъ Є X равно точной нижней грани длин спрямляемых кривых в X, соединяющих а и Ъ. Если при этом для каждой пары а, Ъ Є X существует кривая в X, длина которой равна d(a} b), то метрика d называется строго внутренней. Пространство со строго внутренней метрикой называется геодезическим пространством.

Пусть а, Ь — точки геодезического пространства (X, d), и / = d(a} Ъ). Кратчайшей в пространстве X с началом в а и концом в Ъ называется изометрич-ное отображение 7: [0, /] — X, для которого 7(0) = а, 7(0 = Ъ. Такое отображение существует в силу определения строго внутренней метрики. Отрезком [ab] мы будем называть образ отрезка [0, /] при отображении 7, а треугольником — объединение трех отрезков, попарно соединяющих три различные точки. Когда будет ясно, о какой метрике идет речь, расстояние между точками а и Ъ мы будем обозначать через \аЪ\.

Открытой (соотв., замкнутой) є-окрестностью точки х геодезического пространства (X, d) мы будем называть множество U(x) = {у Є X \ d(x, у) є} (соотв., V(x) = {у Є X\d(x,y) є}). Под просто окрестностью будет подразумеваться некоторая открытая є-окрестность. Таким образом, все окрестности, с которыми мы будем работать, — шаровые.

Определение 1. Величиной угла в геодезическом пространстве (X, d) в точке а между отрезками [ab] и [ас] называется предел если этот предел существует. Мы будем обозначать эту величину через Zbac там, где будет понятно, о каких отрезках идет речь. Замечание 1. В силу определения угол между отрезками лежит в промежутке [0,7Г]. Определение 2. Полная односвязная поверхность постоянной гауссовой кривизны к называется к-плоскостью. Иными словами, при k = 0 это есть евклидова плоскость, при к 0 — сфера радиуса 1/у/к с ее внутренней метрикой, при к 0 — полуплоскость {(ж, у) Є IR2 у 0} с римановой метрикой, коэффициенты которой имеют вид:

Мы будем обозначать / -плоскость через Р&, а расстояние между точками а, Ъ на ней — через \ab\k Определение 3. Пусть Aabc — треугольник в геодезическом пространстве (X,d). Треугольником сравнения на / -плоскости для Aabc называется треугольник Aabc С Рк такой, что \db\k = а&, \bc\k = \Ьс\, \dc\k = \ас\. Мы также будем обозначать его через Akabc. Заметим, что треугольник сравнения однозначно определен с точностью до движения / -плоскости.

Определение 4. В условиях определения 3, углом сравнения на / -плоскости для Zabc называется угол Zdbc треугольника сравнения Adbc. Его мы будем обозначать также через Z abc.

Замечание 2. Угол между отрезками [ab] и [ас], согласно определению 1, есть предел углов сравнения на евклидовой плоскости, поэтому, если он определен и равен в, то для любого є 0 найдется 5 0 такое, что для р є [ab], q Є [ас] угол сравнения Zopaq в треугольнике Aoapq С М2 окажется меньше или равен в + є, если \ар\ 5, \aq\ 5.

Определение 5. Пусть а: [0, є) — X и /3: [0, є) — X — кривые в пространстве X с внутренней метрикой, исходящие из точки р = а(0) = /3(0). Величиной угла между а и [5 называется следующий предел

Определение 6. Геодезическое пространство (X, d) называется пространством кривизны к (соотв., к), если в некоторой окрестности каждой точки выполнено одно из следующих эквивалентных условий: (a) условие сравнения треугольников: для каждого треугольника АаЪс, лежащего в этой окрестности, и каждой точки h Є [ас] справедливо неравенство \bh\ \bh\k (соотв., \bh\ \bh\k), где h — такая точка на стороне [ас] треугольника сравнения Adbc С Pk, что \dh\k = \ah\; (b) условие сравнения углов: углы Zabc, Zbca, Zcab каждого треугольника АаЪс, лежащего в этой окрестности, существуют и удовлетворяют неравенствам Zabc Zkabc, Zbca Z bca, Zcab Z cab (соотв. Zabc Zkabc, Zbca Z bca, Zcab Z cab), и, кроме того, в случае кривизны к для любых двух кратчайших [pq] и [rs], где г — внутренняя точка кратчайшей \pq]: справедливо равенство Aprs + Zsrq = 7г; (с) условие монотонности углов: если а(х) и /3(у) — кратчайшие, исходящие из точки р и содержащиеся в этой окрестности, а /.ьа(х)р/3(у) — угол при вершине р треугольника сравнения Аьа(х)р/3(у) С Pk, то функция 9(х,у) = /-ьа(х)р/3(у) является неубывающей (соотв., невозрастающей) по каждой из переменных ж, у.

Если не уточняется константа к: то говорят от пространстве ограниченной сверху (соотв., снизу) кривизны.

Замечание 3. Образно говоря, пространство X кривизны к (соотв., к) оказывается не более (соотв., не менее) искривленным, чем Р&. Определение 7. Окрестность, о которой идет речь в определении 6, называется нормальной. Пространством Александрова называется пространство ограниченной сверху или снизу кривизны. Доказательство эквивалентности условий сравнения треугольников, углов и условия монотонности углов можно посмотреть в [36, глава 4], также как и доказательство следующей теоремы. Теорема 2. Если к\ hi, то пространство кривизны hi является пространством кривизны к\.

Деревья Штейнера и отношение Штейнера

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

Теорема 4 (см. [37, теорема 4.5.9]). Пусть (Х,р) — метрическое пространство, в котором любой замкнутый шар В может быть наделен компактной метризуемой топологией т таким образом, что метрика р является т-полунепрерывной снизу в В х В. Тогда для любого конечного множества S С X существует минимальное дерево Штейнера.

Для выполнения условий теоремы 4 оказывается достаточным локальной компактности метрического пространства. Пространство Александрова по определению обладает строго внутренней метрикой, поэтому если оно локально компактно, то для него справедлива теорема 4. Пусть (X,d) — локально компактное пространство Александрова. Тогда для любого конечного множества М С X существует минимальная сеть в X, соединяющая М.

Теорема 5 (Завальнюк Е. А.). Пусть X — пространство Александрова кривизны k, М — конечный набор точек в X и Г — минимальная сеть, соединяющая М. Тогда для любых двух ребер в Г, имеющих общую вершину, угол между ними в этой вершине больше или равен 27г/3.

Рассмотрим сферу радиуса Л с ее внутренней метрикой, и пусть ж, у — две различные точки на сфере. Существует по меньшей мере две геодезические, соединяющие ж, у. Они лежат в диаметральных сечениях, проходящих через ж, у. Для расстояния между ж, у справедлива следующая оценка:

Если р(х, у) = 7гЛ, то точки х и у диаметрально протипоположны, и найдется бесконечное число геодезических (меридианов), соединяющих ж,у. Они также являются кратчайшими. Если р(х,у) 7гЛ, то существует лишь две геодезические, лежащие в диаметральном сечении, проходящем через ж, у, при этом одна из них оказывается короче другой. Более короткая геодезическая является кратчайшей, соединяющей ж, у.

Рассмотрим теперь на сфере три различные точки а, 6, с. Поскольку для каждой пары вершин существует по крайней мере две соединяющие их геодезические, то существует по меньшей мере восемь различных геодезических треугольников, имеющих а, 6, с своими вершинами. В данном разделе мы будем рассматривать такие сферические треугольники, стороны которого являются кратчайшими. Если все расстояния между вершинами меньше, чем 7гЛ, то такой треугольник единственен, его мы будем обозначать через Aabc. Если зафиксировать три числа ui, (І2і зJ удовлетворяющие условиям d\ + d2 dz, d\ + із d2} d2 + d% d\, d\ TTR, d2 TTR, d% TTR, то сферических треугольник со сторонами d\1d2l d% существует и единственен с точностью до движения сферы.

Лемма 2. Пусть R, а Є (0, ) — фиксированные числа. При каждом х Є (О, R] рассмотрим треугольник АахЬхсх на сфере радиуса R со сторонами \ахЬх\ = \ахсх\ = х, \bxcx\ = 2xsina. Тогда найдется такое z R, что для любого х Є (0, z] Доказательство. Пусть hx — середина [6жсж]. В силу равнобедренности треугольника АахЬхсх имеем Zaxhxbx = , и по теореме синусов сферической геометрии для треугольника Aaxbxhx получаем

Доказательство. Пусть при каждом х Є (О, Л] для треугольника Aaxbxcf справедливо \ахЬх\ = \ахсх\ = х, \Ьхсх\ 2:rsin x Рассмотрим для каждого х треугольник /\ахЬхсх такой, что \ахЬх\ = \ахсх\ = х, \Ьхсх\ = 2:rsin x По уже доказанному найдется такое z R, что для любого х Є (0, z) выполнено неравенство

Прежде чем доказывать теорему, сделаем небольшой комментарий. Как мы видели в теореме 2, пространство Александрова кривизны к при к 0 является также пространством кривизны 0. В последующем доказательстве будет удобнее в качестве поверхности сравнения рассматривать поверхность постоянной гауссовой кривизны к = тах{0, &}, т.е. евклидову плоскость при к 0 или сферу радиуса R = 4= при к 0.

Лемма 5. Пусть X — пространство Александрова кривизны k, [pq], [рг] — отрезки кратчайших в X, стыкующиеся в точке р под углом 9 27г/3. Тогда найдется такое х, что для точек q\ Є [pq], Г\ Є [pr], \pqi\ = \pr\\ = x, треугольник сравнения /\q\pf\ С Pk имеет угол Aq\pf\, меньший, чем 27г/3. В случае к 0 можно дополнительно добиться выполнения неравенства

Теорема о локальной структуре минимальных сетей в пространствах с кривизной, ограниченной сверху

На поверхностях постоянной гауссовой кривизны степень точек Штейнера в точности равна 3. В [9] были приведены примеры нормированных плоскостей, на которых возникают точки Штейнера степени 4. В теореме 6 мы видели, что на поверхностях Александрова с кривизной, ограниченной снизу, степень точек Штейнера равна 3. Причиной этому явился тот факт, что полный угол на таких поверхностях не превосходит 2-7Г, и, в частности, для выпуклых многогранников это было показано в [5, п. 1.6.3] в терминах углов при вершине, по сути являющихся полными углами в вершинах. Вышеописанное свойство степеней точек Штейнера не имеет места, вообще говоря, для пространств с кривизной, ограниченной сверху.

Предложение 3. Для произвольного п 3 существует поверхность Ада-мара, ее конечное подмножество М и кратчайшая сеть, соединяющая М, степень одной из точек Штейнера которой равна п.

Доказательство. Рассмотрим конус К с полным углом при ным —, и с естественной внутренней метрикой а (которая, к тому же, является строго внутренней). Очевидно, К является двумерным многообразием, полным и односвязным как метрическое пространство; кроме того, К является пространством неположительной кривизны (утверждение 1). Следовательно, конус К является поверхностью Адамара.

Рассмотрим множество М = {А\ ..., Ап} точек на К, отстоящих на расстоянии 1 от вершины О, таких что ZAiOAi+\ = , і = 1,..., п, Ап+\ = A\. Для любого і = 1,...,п ближайшими к точке АІ будут две точки АІ_\ И Д;+і, и d(A{,A{_i) = d(A{,A{+\) = л/3, поэтому минимальное остовное дерево представляет собой многоугольник А\А% ... Ап без одной стороны, и его длина равна rf(mst(M)) = (п - 1) \/3. Множество SMT(M) деревьев Штейнера для М непусто в силу следствия 2. Заметим также, что сумма отрезков Y l=i d(0, АІ) равна п, что строго меньше, чем d(mst(M)), поэтому любое дерево Т Є SMT(M) отлично от минимального остовного, а значит, содержит точки Штейнера.

Пусть Г — минимальная сеть для М, и пусть Р — точка Штейнера в ней. Предположим, что Р отлична от О. Тогда любая достаточно малая окрестность точки Р локально изометрична плоскости. Значит, степень Р в Г равна 3 и все три угла в Р при ребрах Г равны 120 (теорема 1) . Для некоторого і точка Р принадлежит замкнутому сектору Si: ограниченному лучами ОАІ,ОАІ+\. В силу того, что ZAiOAi+\ = 120, какой-то из отрезков сети Г, исходящий из точки Р, содержится, за исключением, быть может, самой точки Р, во внутренности сектора Si. Следовательно, другой конец Р\ этого отрезка также является точкой Штейнера в Г. Применяя то же рассуждение к точке Pi, мы получим точку Штейнера Р2, также лежащую во внутренности сектора Si: и так далее. Так как число точек Штейнера не превосходит п — 2, мы приходим к противоречию.

Н. Иннами и Б. Ким показали в [31], что отношение Штейнера гиперболической плоскости равно 1/2. В качестве граничных множеств, приближающих отношение Штейнера к 1/2, рассматривались вершины правильных многоугольников. В частности, было показано, что все точки Штейнера правильного n-угольника находятся в некоторой окрестности центра многоугольника, независимо от удаленности граничных вершин от центра; размер окрестности зависит лишь от п.

Ниже предлагается иное доказательство теоремы Иннами-Ким. Точное устройство деревьев Штейнера для множества вершин правильного многоугольника окажется, как мы увидим, несущественным для вычисления отношения Штейнера. Оказывается достаточным получить лишь верхнюю оценку отношения Штейнера, рассмотрев вместо деревьев Штейнера «немного» более длинные деревья, но существенно проще устроенные. Значимость предлагаемого доказательства заключается в том, что его можно обобщить для неограниченных поверхностей Адамара кривизны к 0.

Пусть (Pk,dk) — поверхность постоянной гауссовой кривизны к 0. Рассмотрим ее модель Пуанкаре в круге. Пусть D = {(х,у) Є Ш2 х2 + у2 1} Рис. 3.2: Модель Пуанкаре гиперболической плоскости открытый диск с метрикой dl2 = 1 1/ 2,. 2)2- Начало координат обозначим через О. Пусть а Є (0, ) — величина некоторого угла, t Є (0,1) — некоторое число, АОАВ — равнобедренный треугольник с вершинами в точках О, A = {t cos a, t sin а), В = (t cos a,—t sin а) и углом 2а при вершине О, см. рис. 3.2.

Кратчайшая на Р&, соединяющая точки А и В, представляет собой в модели Пуанкаре дугу окружности, перпендикулярной к абсолюту х2 + у2 = 1. Обозначим эту окружность через C{F, г), где F и г — ее центр и радиус соответственно. Пусть Н — точка пересечения кратчайшей [АВ] с осью абсцисс системы координат. Очевидно, что ОН — высота, медиана и биссектриса в треугольнике АОАВ. Нетрудно вычислить абсциссу центра F и радиус г окружности:

Лемма 8. Пусть X — пространство Александрова кривизны к, Аа Ь с — треугольник, лежащий в некоторой нормальной окрестности в X, а АаЬс — такой треугольник на к-плоскости, что \а Ъ \ = \ab\k, \а с \ = \ac\k, Zb a c1 Abac. Тогда \b d\ \bc\k Доказательство. Пусть АаЬс — треугольник сравнения на / -плоскости для Аа Ь с1, т.е. \а Ъ \ = \ab\k, \a d\ = \ac\k, \b c \ = \bc\k- Условие сравнения углов дает Zb a d Abac. Следовательно, Abac Zb a d bac. По лемме 1 для треугольников АаЬс и АаЬс на / -плоскости \bc\k \bc\k = \Ь с \. Отметим также, что на неограниченной поверхности Адамара в силу определения поверхности каждая точка обладает замкнутой окрестностью, гомео-морфной двумерному диску, из чего следует локальная компактность такой поверхности. Тогда в силу следствия 2 для произвольного конечного множества на поверхности существует соединяющая его минимальная сеть, и корректно говорить об отношении Штейнера рассматриваемых в доказательстве множеств.

Доказательство теоремы В. Пусть (S,d) — неограниченная поверхность Адамара кривизны к 0. По теореме 12 полный угол в{х) вокруг точки х больше или равен 2-7Г. Возьмем натуральное п 4. Выпустим из точки х в окрестности V(ж), фигурирующей в определении полного угла вокруг ж, натурально параметризованные кратчайшие 7ь 7п такие5 чт0 /(7г-,7і+і) = 27г/п, і = 1,..., п — 1. Заметим, что Z(7i,7n) — 27г/п. В силу следствия 6 эти кратчайшие бесконечно продолжимы и нигде в дальнейшем не пересекаются.

Полный угол на поверхностях Адамара

Прежде чем доказывать теорему, сделаем небольшой комментарий. Как мы видели в теореме 2, пространство Александрова кривизны к при к 0 является также пространством кривизны 0. В последующем доказательстве будет удобнее в качестве поверхности сравнения рассматривать поверхность постоянной гауссовой кривизны к = тах{0, &}, т.е. евклидову плоскость при к 0 или сферу радиуса R = 4= при к 0.

Лемма 5. Пусть X — пространство Александрова кривизны k, [pq], [рг] — отрезки кратчайших в X, стыкующиеся в точке р под углом 9 27г/3. Тогда найдется такое х, что для точек q\ Є [pq], Г\ Є [pr], \pqi\ = \pr\\ = x, треугольник сравнения /\q\pf\ С Pk имеет угол Aq\pf\, меньший, чем 27г/3. В случае к 0 можно дополнительно добиться выполнения неравенства \q\T\\

Доказательство теоремы 5. Обозначим через Т дерево Штейнера, соответствующее минимальной сети Г. Пусть [pq] и [рг] — ребра сети Г, стыкующиеся в точке р под углом в. Докажем, что в 2-7г/3. Предположим противное, т.е. что 9 27г/3. По лемме 5 найдутся точки q\ Є [pq], Г\ Є [pr], \PQi\ = Iwili чт0 соответствующий треугольник сравнения Aq\pr\ С Pk имеет угол Aq\pf\ 27г/3. Пусть s и s — середины [q\r\\ и [q\f\\ соответственно. Условие сравнения треугольников Apq\T\ и Apq\f\ дает \ps\ \ps\k . Пусть p q is f i С Pk — четырехугольник, составленный из треугольников сравнения Apfq[sf и Apfr[sf для треугольников Apq\s и Apr\S соответственно. Тогда, в частности, \p q[\k = \pff[\k = х, \q[s \ki = \r[sf\k .

Рассмотрим такую точку s" на отрезке [ps], что \ps"\k = \ps\ = \p s \k . Поскольку треугольник Aqipri равнобедренный, то Zqip = Z.f\sp = . Рассмотрим треугольник Aqie"s и докажем, что l is"] (/ISA; . В случае к 0 неравенство верно, поскольку треугольник плоский; в случае к 0 в силу леммы 5 справедливо неравенство /іГі& 2R, откуда /ISA;/ R, и тогда требуемое неравенство следует из леммы 3. Далее, поскольку \q\s\k = \ \s \k i то l is" Iq[s \k - По лемме 1 для Aqips" и Aq[p s получаем Zq[p s Zqips". Аналогично Zr[p s Zr\ps". Следовательно,

Точка Штейнера в кратчайшем дереве, соединяющем три различные точки евклидовой плоскости либо три достаточно близкие различные точки сферы, обладает следующими свойствами: во-первых, она единственна; во-вторых, она лежит внутри самого треугольника; в-третьих, любой угол при ней между ребрами-отрезками дерева Штейнера больше или равен 27г/3. Тогда, если й — точка Штейнера для треугольника Aq p f , то в силу только что доказанного неравенства точка й отлична от р , и, кроме того, выполнено строгое неравенство \p u \k + \q iu \k + \г\й \к \p q \\k + \ї і\к - Так как треугольник Aq ipfr i равнобедренный, то й лежит на луче p s .

Предположим сначала, что й лежит вне отрезка [p s1]. Докажем при этом предположении, что Zq[s p 27г/3. Пусть Zq[s p 27г/3. Рассмотрим угол Zq[t p как функцию точки t Є [p s1]. Так как отрезок [p s1] — непрерывная кривая (на плоскости или сфере), то при движении т от т. р до т. угол Zq[tfpf изменяется непрерывно. В некоторой окрестности т. р величина этого угла больше 2-7г/3 (поскольку Zq p s 7г/3), авт.?- меньше или равна 27г/3. В силу непрерывности найдется точка t на отрезке [p s }, углы Zq[t p и Zf t p при которой равны 2-7г/3. Таким образом, точка т является точкой Штейнера для треугольника Aq p r , а значит должна совпасть с й , лежащей вне отрезка [p s }, противоречие. Итак, Zq[s p 27г/3. В силу леммы 4 и замечания 4 к ней

Таким образом, мы нашли точку й на отрезке [p s }, для которой справед ливо неравенство полученное из дерева Т добавлением вершины м, удалением ребер {pqi}, {рг\\ и добавлением ребер {ри}, {q\u\, {г\и\, оказалось короче дерева Т, что противоречит минимальности дерева Т. Теорема доказана.

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

Число точек Штейнера не превосходит п — 2. В своей статье авторы работали с поверхностями Александрова, однако доказательство свойства (2) дословно переносится на общий случай — на пространства Александрова с кривизной, ограниченной снизу. Отметим также, что свойство (3) явилось следствием свойства (2) и того факта, что полный угол на полной поверхности с ограниченной снизу кривизной не превосходит 27Г (см. также [14]). Определение полного угла и более подробное его исследование будет приведено в разделе 3.1. Там же будет показано, что свойство (3), вообще говоря, не имеет места для поверхностей с кривизной, ограниченной сверху. Поэтому обобщить результаты теорем 5 и 6 мы можем лишь в следующем виде.

Определение пространства Александрова предполагает выполнение некоторых локальных условий на метрику. Предположим, что пространство Александрова (S, (Ї) является двумерным топологическим многообразием. В этом случае будем называть S поверхностью Александрова с кривизной, определенной для нее как для пространства Александрова. По определению, для произвольной точки х Є S найдется достаточно малое є 0 такое, что окрестность U(x) гомеоморфна либо кругу, либо полукругу. В первом случае назовем точку х внутренней, во втором — граничной. Объединение всех граничных точек поверхности S назовем границей поверхности и обозначим через dS. Если х — внутренняя точка, то граница dU(x) окрестности U(x) (где є такое, как выше) есть множество всех точек поверхности, удаленных от точки х на расстоянии є; она является образом некоторой простой замкнутой кривой на S. Замкнутая окрестность V (х) гомеоморфна в этом случае двумерному диску.

Пусть х — внутренняя точка, и 7ь72 Две кратчайшие, исходящие из ж и не имеющие в некоторой окрестности U(x) общих точек, за исключением х. Рассмотрим два замкнутых сектора Vi, V2, на которые кратчайшие