Геометрия локально минимальных и экстремальных сетей в пространствах с нормами

• Автор: Ильютко, Денис Петрович
• Шифр специальности: 01.01.04
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 139 с. : ил.

Задачи, связанные с изучением локально минимальных сетей, т.е. кратчайших в малом, и экстремальных сетей, т.е. критических точек функционала нормированной длины, строгое определение которых см. ниже, появляются при обобщении следующей классической задачи, известной в литературе как проблема Штейнера: среди всех сетей, затягивающих данное конечное множество X точек евклидовой плоскости, найти сеть наименьшей длины. Решение этой задачи называется крат-чайшей или абсолютно минимальной сетью, затягивающей множество X. Отметим, что с точки зрения римановой геометрии, локально минимальные сети являются естественным обобщением обычных геодезических. Действительно, локально минимальная сеть, затягивающая две произвольные точки на некотором римановом многообразии, представляет собой обычную геодезическую, т.е. кратчайшую в малом кривую. Более подробный исторический обзор, посвященный проблеме Штейнера, можно найти в [4, 5, 25, 31].
Традиционно больше внимания уделяется изучению локально мини-^ мальных и кратчайших сетей, чем изучению экстремальных сетей
связано с тем, что в случае функционала римановой длины, если разрешено расщеплять вершины, классы локально минимальных и экстремальных сетей совпадают, см. [15]. В данной работе рассматриваются сети на А-нормированных плоскостях, т.е. на нормированных плоскостях (К2,рл), для которых единичная окружность Е = {хе Ж2| р{х) = 1} совпадает с правильным 2А-угольником, одна из осей симметрии которого лежит на оси абсцисс. Важными отличиями этих нормированных плоскостей от стандартной евклидовой плоскости являются отсутствия гладкости единичной окружности Е и строгой выпуклости единичного круга, ограниченного Е. Часто нормы, для которых единичная окружность Е является гладкой, называют гладкими, а нормы, для которых единичный круг строго выпуклый, — строго выпуклыми. Оказывается, на этих А-нормированных плоскостях, ввиду отсутствия гладкости нормы, класс локально минимальных сетей существенно шире класса экстремальных сетей.
Первые работы, посвященные изучению проблемы Штейнера на нормированных плоскостях, появились в 60-е годы XX века, см. [6], в связи с бурным развитием электроники и робототехники. В 1966 г. Ханан [8] провел исследование кратчайших прямоугольных деревьев, т.е. кратчайших сетей на 2-нормированной, так называемой манхеттенской, плоско-

сти, и описал несколько важных общих геометрических свойств таких сетей. Он указал максимальную степень, которую могут иметь как внутренние, так и граничные вершины кратчайшей сети на манхеттенской плоскости, а именно, что эта степень равна 4 для всех вершин. Также Ха-нан показал, что всегда существует кратчайшее прямоугольное дерево, которое является подмножеством решетки Хапана — множества всех вертикальных и горизонтальных прямых, проходящих через граничные точки. Позже Хванг [9] описал структуру некоторых кратчайших сетей на манхеттенской плоскости, но эффективный алгоритм, строящий кратчайшую сеть, найти не удалось. В 1977 г. Гэри и Джонсон [7] показали, что задача поиска кратчайшего прямоугольного дерева, затягивающего п различных точек плоскости, является ХР-полной. Последнее означает, что, скорее всего, для этой проблемы не существует полиномиального алгоритма, т.е. алгоритма, решающего задачу за время 0(пк), где к — некоторое фиксированное число. Тем не менее, на практике приходится строить кратчайшие деревья, затягивающие большое количество точек плоскости, поэтому изучение ограничений на структуру кратчайших сетей является важным для приложений. Эти ограничения позволяют сокращать набор претендентов на кратчайшую сеть. Например, хорошо р известно, что степени вершин кратчайших сетей на стандартной евклидовой плоскости должны быть не больше 3, что существенно снижает перебор при построении кратчайшего дерева. Такие же эффекты можно получить, исходя из геометрии граничного множества. Например, если в качестве граничного множества X рассматривается правильный многоугольник, то для такого X удается получить полный список кратчайших сетей, его затягивающих, см. [4]. Также имеются существенные продвижения и в задаче описания локально минимальных сетей, затягивающих X, см. [13, 14, 35, 36].
В 90-х годах XX века проблемой Штейнера на нормированных плоскостях занимались многие ученые. Опишем некоторые важные результаты, касающиеся сетей на нормированных плоскостях.
Рассмотрим вопрос о максимальной степени вершины. В случае, когда норма является гладкой и строго выпуклой, степень вершин не превосходит 3, см. [1]. Как было отмечено выше, если мы откажемся от условий гладкости и строгой выпуклости нормы (как это имеет место, например, на манхеттенской плоскости), то степень вершин может быть больше 3. Рассмотрим нормированные плоскости, которые удовлетворяют только одному из обсуждаемых условий, т.е. либо норма является гладкой, либо строго выпуклой. Оказывается, что существуют нормированные плоскости со строго выпуклой нормой и кусочно-гладкой единичной окружно-

стью, на которых внутренние вершины кратчайших сетей могут иметь степень 4, см. [1]. Заметим, что упомянутая выше манхеттенская плоскость не удовлетворяет условию строгой выпуклости единичного круга. Лаулор и Морган [28] обобщили результаты, полученные в [1], и показали, что на нормированных плоскостях с гладкой нормой и без условия ее строгой выпуклости степень внутренней вершины все равно не превосходит 3. Но в некоторых случаях условие строгой выпуклости нормы играет существенную роль при ограничении степени вершин. Если норма строго выпуклая, но не обязательно гладкая, то Альфаро и др. [1] показали, что степень внутренней вершины не больше 4, а Цислик в работе [2] доказал это ограничение для всех вершин. Подводя итоги вышесказанного, мы можем заключить, что на нормированных плоскостях с гладкой нормой степени вершин не превосходят 3, а со строго выпуклой нормой
— 4. Более того, Цислик показал [2], что на нормированных плоскостях, не изометричных 3-нормированной плоскости, степень вершин не может быть больше 5. Сванепол уточнил этот результат [32] и доказал, что на любой нормированной плоскости степень внутренней вершины не превосходит 4, а граничной — 6, причем граничная вершина может иметь степень 5 или 6 только на плоскостях, изометричных 3-нормированной
k плоскости.
Локальная структура локально минимальных сетей на А-нормирован-ных плоскостях, А Ф 2, т.е. возможные степени вершин и углы между смежными ребрами, была описана Саррафзаде и Вонгом [30], а также Ли и Шеном [29]. Но в этих двух работах описание было не полным, так как отсутствовали некоторые возможные структуры вершин степени 3 для 2А = 0 (mod 3). Полный же ответ был независимо получен Сванепо-лом [32] и автором настоящей диссертации [18].
Отметим, что проблемой Штейнера занимались многие известные математики, такие как Винтер, Гилберт, Гильдебрандт, Грехем, Гэри, Джонсон, Ду, Иванов, Кокейн, Мантуров, Мелзак, Морган, Поллак, Рубинштейн, Смит, Томас, Тужилин, Фоменко, Ханан, Хванг, Цислик и другие. Одна из причин этого неослабевающего интереса специалистов к минимальным сетям состоит в том, что у проблемы Штейнера имеется много различных интерпретаций и приложений. Например, заданное конечное множество X можно интерпретировать как набор конечных (терминальных) пунктов. Если, например, терминальные пункты
— города, которые требуется соединить сетью дорог, то в этом случае минимальная сеть — это самая дешевая транспортная система, обеспечивающая коммуникации между данными конечными пунктами. Здесь естественно предполагается, что стоимость коммуникаций пропорцио-

2.2.4. Вершины, инцидентные точечным ребрам
Пусть Г — произвольное погруженное локально минимальное дерево на A-нормированной плоскости, иг — его внутренняя вершина, инцидентная точечным ребрам.
Утверждение 2.8. Дерево Г экстремально, если и только если экстремальны все максимальные поддеревья в V, у которых, по крайней мере, одно из ребер, инцидентных вершине г, является 1 -граничным.
Доказательство. Пусть вершина z = {Г: v —» R2} инцидентна точечным ребрам у* = {Г: [г, пД —> К2}, направления которых приходят в вершины pik из Е, и пусть Г*: Gfc —>• М2 — максимальные поддеревья в Г, у которых ребро 7к является 1-граничным, к — 1, 2, 3. Докажем экстремальность дерева Г в предположении, что каждое дерево ГД экстремально.
Пусть Г7: G' —У М2 - - произвольный базовый тип расщепления сети Г. Обозначим базовые типы расщеплений сетей Г*,, которые являются подсетями сети Г', через r'fc: G'k —> Ж2. По предположению, сети Гг экстремальны, поэтому выполнены неравенства 0(ГД, щ) ^ 0 для любых деформаций Vck —> К2. Экстремальность сети Г равносильна выполнению неравенства £>(Г',ц) ^ 0 для любой деформации г/: Vc —*■ М2. Проверим выполнение последнего неравенства.
Рассмотрим произвольную деформацию у: Vc -> Ж2. Прямые, содержащие инцидентные z ребра, разбивают плоскость М2 на 6 частей. Пусть r](v) лежит в секторе, образованном лучами с направлениями (cos jip, sin jip) и — (cos |г9, siring), и пусть ip — угол между Tj(v) и (cos jip, sin jip).
Представим r][y) в виде г}'(и)--г]"(и), где T]'(v) = а(cos jip, sin jiP), а ^ О, и г]"{у) — — b(cos jiq, sin fig), 6^0.
Определим отображения r]p: Vc —> Ж2, rjq: Vc —> Ж2, положив T}p(dG'p) = 0, r)q(dG'q) = 0,
1) Г)р{и) = Г)(и) для любой вершины и € Vg'p Vcq ,
sin(ar + (р) sina9
rjp(w)
sin ar sin(a9 — для любой вершины w € Vq'p VG> и Tjp(v) = rf(v)
2) t]qiu) = T](u) для любой вершины и £ VG' Vc ,