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

На правах рукописи УДК 514.77+517.982.22+519.711.72

ИЛЬЮТКО Денис Петрович

ГЕОМЕТРИЯ ЛОКАЛЬНО МИНИМАЛЬНЫХ И ЭКСТРЕМАЛЬНЫХ СЕТЕЙ В ПРОСТРАНСТВАХ С НОРМАМИ

01.01.04 — геометрия и топология

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

Москва - 2005

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

Научный руководитель — доктор физико-математических наук,

профессор А. А. Тужилин.

Официальные оппоненты — доктор физико-математических наук,

профессор Н. П. Долбилин; кандидат физико-математических наук Г. А. Карпунин.

Ведущая организация — Волгоградский государственный

университет.

Защита диссертации состоится 18 ноября 2005 г. в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете имени М. В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 18 октября 2005 г.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В. Н. Чубариков

zoo 6-4

-<6 908

Общая характеристика работы "

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

Задачи, связанные с изучением локально минимальных сетей, т.е. сетей, кратчайших в малом, и экстремальных сетей, т.е. критических точек функционала нормированной длины, строгое определение которых см. ниже, появляются при обобщении* следующей классической задачи, известной в литературе как проблема Штейнера: среди всех сетей, затягивающих данное конечное множество X точек евклидовой плоскости, найти сеть наименьшей длины. Решение этой задачи называется абсолютно минимальной или кратчайшей сетью, затягивающей множество X. Очевидно, что абсолютно минимальная сеть не может иметь циклов, поэтому в данной диссертации мы ограничимся рассмотрением сетей, являющихся деревьями. Отметим, что с точки зрения римановой геометрии, локально минимальные сети являются естественным обобщением обычных геодезических. Более подробный исторический обзор, посвященный проблеме Штейнера, можно найти в1,2'3,4.

Традиционно больше внимания уделяется изучению локально минимальных и кратчайших сетей, чем изучению экстремальных сетей. Это связано с тем, что в случае функционала римановой длины, если разрешено расщеплять вершины, классы локально минимальных и экстремальных сетей совпадают5. В данной работе рассматриваются сети на А-нормированных плоскостях, т.е. на нормированных плоскостях (К2,/>д), для которых единичная окружность Е = {х б К2| р\{х) — 1} совпадает с правильным 2А-угольником, одна из осей симметрии которого лежит на оси абсцисс. Эти нормированные плоскости характеризуются теми условиями, что для любого А единичный круг не является строго выпуклым и единичная окружность Е не является гладкой. Ввиду отсутствия гладкости единичной окружности, класс локально минимальных сетей существенно шире класса экстремальных сетей на этих А-нормированных плоскостях (Х-экстремальньгх сетей).

Первые работы, посвященные изучению проблемы Штейнера на норми-

1D. Z. Du, F. К. Hwang and J. F. Weng. Steiner minimal trees for Regular Polygons // Disk, and Comp. Geometry. Vol. 2. 1987. Pp. 65-84.

2 P. Fermat. Abhandlungen über Maxima und Minima // В книге: Oswalds, Klassiker der Exakten Wissenschalten. 1934. N 238.

3 V. Jarnik and M Kössler. О minimalnich grafeth obeahujiicich n danijch bodu // Cas. Pest. Mat. a Fys. Vol. 63. 1934. Pp. 223-235.

* W. D. Smith. How to find Steiner minimal trees in Euclidean d-space // Algoritmica. 1992. N 7. Pp. 137-177.

M. 0. Ivanov, A. A. Tuzhtlin. Branching Solutions to One-Dimensional Variational Probleme. — World Scientific Publishing Co. Pte. Ltd. Singapore 912805. 2001.

рованных плоскостях, появились в 60-е годы XX века® в связи с бурным развитием электроники и робототехники. В 1966 г. Ханан7 провел исследование кратчайших сетей на манхеттенской плоскости, т.е. на 2-нормированной плоскости (так называемых кратчайших прямоугольных деревьев). Он показал, что всегда существует кратчайшее прямоугольное дерево, которое является подмножеством решетки Ханана — множества всех вертикальных и горизонтальных прямых, проходящих через граничные точки. Позже Хванг8 описал структуру некоторых кратчайших сетей на манхеттенской плоскости, но эффективный алгоритм, строящий кратчайшую сеть, не удалось найти. В 1977 г. Гэри и Джонсон9 показали, что задача поиска кратчайшего дерева является JVP-полной. Последнее означает, что, скорее всего, для этой проблемы не существует полиномиального алгоритма, т.е. алгоритма, решающего задачу за время порядка 0(пк), где к — некоторое фиксированное число. Тем не менее, на практике приходится строить кратчайшие деревья, затягивающие большое количество точек плоскости, поэтому изучение ограничений на структуру кратчайших сетей является важным для приложений. Эти ограничения позволяют сокращать набор претендентов на кратчайшую сеть. Например, хорошо известно, что степени вершин кратчайших сетей на стандартной евклидовой плоскости должны быть не больше 3, что существенно снижает перебор при построении кратчайшего дерева. Такие же эффекты можно получить, исходя из геометрии граничного множества. Например, если в качестве граничного множества X рассматривается правильный многоугольник, то для такого X удается описать все кратчайшие сети, его затягивающие1,3,10'11'12. В настоящей диссертации сформулирован и доказан геометрический критерий А-экстремальности дерева при А ф 2, 3, 4, б, который позволяет существенно сократить количество претенден-

'R. L. Francis A note on the optimum location of new machines in existing plant layouts // J. of Induit. Engrg. Vol. 14. 1963. Pp. 57-59.

7M. Horton. On Steiner's Problem with Rectilinear Distance // SIAM J. of Appl. Math. Vol. 14. 1966. Pp. 255-265.

"F. K. Hwang. On Steiner minimal trees with rectilinear distance // SIAM J. of Appl. Math. Vol. 30. 1976. Pp. 104-114.

'M. R. Garey and D. S. Johnson. The Rectilinear Steiner Problem is NP-Complete // SIAM J. of Appl. Math. Vol. 32. 1977. Pp. 826-834.

"M. О. Иванов, А. А Тужил им. Классификация минимальных скелетов с правильной границей // Успехи мат. наук. 1996. Т. 51. N 4. С. 157-158.

'М. О. Иванов, А. А. Тужилин. Разветвлённые геодезические. Геометрическая теория локально минимальных сетей. — The Edwin Mellen Press. Lewiston-Queenston-Lampeter 1999.

"A.A. Тужилин. Полная классификация локально минимальных бинарных деревьев с правильной границей, двойственные триангуляции которых являются скелетами // Фундаментальная и прикладная математика. 1996. Т. 2. N 2. С. 511-562.

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

Отметим, что проблемой Штейнера занимались многие известные математики, такие как Винтер, Гилберт, Гильдебрандт, Грехем, Гэри, Джонсон, Ду, Иванов, Кокейн, Мантуров, Мелзак, Морган, Поллак, Рубинштейн, Смит, Томас, Тужилин, Фоменко, Ханан, Хванг, Цислик и другие. Одна из причин этого неослабевающего интереса специалистов к минимальным сетям состоит в том, что у проблемы Штейнера имеется много различных интерпретаций и приложений. Например, заданное конечное множество X можно интерпретировать как набор конечных (терминальных) пунктов. Если, например, терминальные пункты — города, которые требуется соединить сетью дорог, то в этом случае минимальная сеть — это самая дешевая транспортная система, обеспечивающая коммуникации между данными конечными пунктами. Здесь естественно предполагается, что стоимость коммуникаций пропорциональна их длине. Другие приложения проблемы Штейнера — это разводка микросхем и филогенетические пространства. Основная проблема при разводке микросхем — это минимизация длины проводников на печатных платах. Эти проводники имеют вид ломанных линий, составленных из горизонтальных и вертикальных отрезков. Таким образом, разводка микросхем имеет непосредственное отношение к проблеме Штейнера на манхеттенской плоскости.

Цель работы.

Целью настоящей диссертации является разработка методов и техники проверки экстремальности произвольного дерева на А-нормированной плоскости, а также применение полученных результатов к изучению вопросов реализации произвольного дерева в виде А-экстремального и асимптотики А-экстремальных деревьев при А —► оо.

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

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

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

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

1) Показано, что для проверки А-экстремальности сети достаточно рассматривать лишь конечное число деформаций, которые полностью описаны.

2) Получен геометрический критерий А-экстремальности дерева при А ф 2, 3, 4, 6.

3) Доказаны теоремы о топологической и планарной реализации произвольного дерева в виде локально минимального или экстремального дерева на А-нормированной плоскости.

4) Исследована асимптотика А-экстремальных деревьев при А —»■ оо.

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

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

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

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

-— на семинаре А. О. Иванова и А. А. Тужилина по теории минимальных сетей (механико-математический факультет МГУ);

— на семинаре Г. Книпера (Рурский университет, г. Бохум, Германия) в июле 2002 г.;

— на семинаре "Теория узлов" под руководством В. В. Трофимова и В. О. Мантурова (механико-математический факультет МГУ) в октябре 2002 и 2003 гг.;

— на семинаре "Алгоритмические проблемы топологии многообразий малых размерностей" под руководством С. В. Матвеева (ЧГУ) в ноябре 2003 г.;

— на секции "Теория функций и функциональный анализ" в ВЗМШ-2004 (Воронежская зимняя математическая школа) в январе 2004 г.;

— на секции "Дискретная геометрия" на Восьмом Международном семинаре "Дискретная математика и ее приложения" (МГУ) в феврале 2004 г.;

— на секции "Алгебраические и топологические методы в геометрии" Международной школы-конференции по анализу и геометрии (Новосибирск) в августе 2004 г.;

— на секции "Геометрия" Международной школы-семинара по геометрии и анализу (Абрау-Дюрсо) в сентябре 2004 г.;

— на семинаре "Дискретная геометрия" под руководством И. X. Сабитова (механико-математический факультет МГУ) в октябре 2004 г.;

— на семинаре "Дифференциальная геометрия и приложения" под руководством А. Т. Фоменко (механико-математический факультет МГУ) в фе-

врале 2005 г.;

— на семинаре "Дискретная геометрия и геометрия чисел" под руководством С. С. Рышкова, М. Д. Ковалева, Н. П. Долбилина, Н.Г. Мощевитина (механико-математический факультет МГУ) в апреле 2005 г.;

— на XXVII Юбилейной Конференции молодых ученых (механико-математический факультет МГУ) в апреле 2005 г.;

— на секции "Теория графов и комбинаторика" на XIV Международной конференции "Проблемы теоретической кибернетики", посвященной 80-летию со дня рождения С. В. Яблонского, (ПГУ) в мае 2005 г.;

— на семинаре "Геометрический анализ и его приложения" под руководством А. Г. Лосева и В. М. Миклюкова (ВолГУ) в июне 2005 г;

— на международной конференции "Contemporary Geometry and Related Topics" (Belgrade, Serbia and Montenegro) в июне 2005 г.

Публикации.

Основное содержание диссертации опубликовано в 7 работах, список которых приведен в конце автореферата [1-7].

Структура и объем работы.

Диссертация состоит из введения, пяти глав и списка литературы. Текст диссертации изложен на 139 страницах. Список литературы содержит 36 наименований.

Содержание работы

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

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

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

Пусть Р G G — некоторая точка из G. Допустимой окрестностью U С G точки Р графа G называется замыкание связной окрестности этой точки, не содержащее вершин графа G, отличных от Р, если Р — вершина. Наделим

окрестность II структурой графа, объявив вершинами все точки из 81/1) {Р}, а ребрами — внутренности отрезков в и, соединяющих эти точки. Полученную звезду обозначим через (ту и будем называть локальным графом с центром в точке Р. Определим каноническую границу дйц локального графа (?{/, включив в нее все вершины из 81/, а также вершину Р, если Р — граничная вершина графа <7, т.е. ЗСу = (0(7 П 17) и (С П 811).

Определение. Граничное ребро графа й называется 1-граничпым, если оно инцидентно граничной вершине степени 1. Совокупность всех смежных 1-граничных ребер, из общей вершины которых выходит не более одного не 1-граничного ребра, назовем усами. Вершину графа £7, инцидентную усам, назовем вершиной усов. Если усы состоят из I ребер, то назовем их 1-усами.

Определение. Линейной сетью типа (7 или, более коротко, сетью типа <3 называется непрерывное отображение Г из С? в К", аффинное на каждом ребре графа С7. Граф О в этом случае называется параметризующим графом сети Г или ее типом. Ограничения отображения Г на вершины, ребра, границу, связный подграф параметризующего графа, локальный граф называются соответственно вершинами, ребрами, границей 8Г, подсетью, локальной сетью сети Г.

Определение. Ребро 7 сети Г называется вырожденным, если оно является отображением в точку. Вырожденная компонента сети Г — это связная компонента множества вырожденных ребер сети. Приведенная компонента сети Г — это или ее вырожденная компонента, или вершина, которая не принадлежит вырожденным компонентам.

Определение. Линейная сеть Г называется погруженной, если она не содержит вырожденных ребер. Погруженную сеть Г назовем вложенной, если отображение Г взаимно однозначно с образом. Для простоты изложения мы часто будем отождествлять вложенную сеть с ее образом.

Определение. Непрерывное отображение Ф: б х [0,1] К" такое, что для каждого ребра е из Сг и t € (0,1] отображение является аффинным,

и для всех д € С? имеет место равенство Ф(<7,0) = Г(<?), называется деформацией сети Г. Положим Ф(д, £) = Г4(д), и в дальнейшем будем называть деформацией само однопараметрическое семейство {Г^ С К2}. Всегда, если не оговорено противное, будем предполагать, что деформация неподвижна на границе, т.е. Ф(и,£) = Г(и) для любой вершины V € дй и любого £ € [0,1].

Рассмотрим теперь траекторию движения каждой точки сети Г при деформации Для этого фиксируем некоторую точку 5 Е С и рассмотрим

Т, / V г, г, ¿Г4(о)|

кривую ГДд). Вдоль Г определено поле —-— , которое называется полем

аъ 1*=о

деформации Г(.

Пусть Н — произвольный подграф в топологическом графе С. Обозначим через С/тН топологическое пространство, полученное из б отождествлением точек каждой связной компоненты графа Я. Пространство С/ШЯ наделяется естественной структурой топологического графа. Граф С?/ШЯ называется слабым фактор-графом графа С? по подграфу Я. При этом каноническую проекцию 7г: С? —> (7/шЯ будем называть слабой проекцией. Будем говорить, что граф С?2 может быть слабо спроецирован на граф если существует Я С <?2, Для которого С?1 =

Пусть Г,: <7, -4 К", г = 1, 2, — произвольные линейные сети.

Определение. Будем говорить, что сеть Г2 может быть слабо спроецирована на сеть Гх, если существует слабая проекция ж: бг —У (?1 такая, что Г2 = Г1 о 7Г.

I Пусть Г и Г' — произвольные сети, причем Г' может быть слабо спроеци-

рована на Г.

Определение. Произвольную деформацию сети Г' назовем деформацией ; с расщеплением сети Г. При этом сеть Г' будем называть типом такого

расщепления.

Пусть Г: <7 -> К" — произвольная линейная сеть в нормированном пространстве (К", р). Тогда длиной /(Г) сети Г назовем сумму длин ее ребер, т.е. следующее выражение:

'(Г)= £ р(Г(«}-Г(»)),

«о б£(С)

г где .£7(<?) — множество ребер графа £?.

Определение. Сеть Г называется критической или экстремальной, если для любой деформации с расщеплением Г/ сети Г выполнено соотношение

<Й 1*=о+

Из критерия экстремальности произвольной сети (теорема 1.3 диссертации) и из линейности сети вытекает, что для проверки экстремальности сети достаточно знать поле деформации только в вершинах сети и рассматривать только линейные деформации, т.е. деформации, при которых каждая точка сети движется прямолинейно и равномерно. Поскольку между полями вдоль сети Г, равными нулю на границе, и линейными деформациями сети Г имеется взаимно однозначное соответствие, то в дальнейшем будем отождествлять поля деформации с самими деформациями и называть их просто деформациями сети.

Определение. Будем говорить, что сеть Г затягивает множество X, если im 9Г = X.

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

Утверждение 1. Каждая подсеть локально минимальной (экстремальной) сети является локально минимальной (экстремальной).

Следующая теорема, теорема 1.1 диссертации, связывает два определения локальной минимальности и экстремальности.

Теорема 1. Каждая погруженная экстремальная сеть в нормированном пространстве (Rп,р) является локально минимальной.

Отметим, что обратное утверждение не всегда верно. Существуют нормированные пространства, на которых локально минимальные сети не являются экстремальными.

Опишем структуру локально минимальных сетей на А-нормированных плоскостях.

Определение. Нормированная плоскость (R2, р\) называется Х-норми-рованной плоскостью, если единичная окружность £ = {х е R2 | р\(х) = 1} для нормы р\ совпадает с правильным 2А-угольником, вершины которого — это точки Hi = (cos ji, sin ji), 0 < t < 2A — 1.

Пусть Г: G -¥ R2 — произвольная погруженная линейная сеть, и 7 — некоторое ребро сети Г, ориентированное одним из двух возможных способов. Если направление этого ребра приходит во внутреннюю точку стороны [fii, 2А-угольника Е, то замыканием направления ребра 7 назовем интервал (т, fii+i), а если направление этого ребра приходит в вершину щ из Е, то замыканием направления ребра 7 назовем точку щ. В первом случае ребро 7 называется неточечным, а во втором — точечным. Замыкание направления ребра 7 обозначим через fl(7).

Для любых подмножеств А и В из Е обозначим через а{А, В) точную нижнюю грань, а через jв(А, В) — точную верхнюю грань углов между радиус-векторами точек х € А я у € В. Если 71 и 72 — два смежных ребра, то в выражениях a(fl(7i), А(7г)) и /3(fl(7i)i А(7г)) под замыканиями 8(7,) будем понимать замыкания для ребер 7,-, i = 1, 2, ориентированных от их общей вершины.

Приведем описание локальной структуры локально минимальных сетей13'14.

Теорема 2. Погруженная линейная сеть Г: G —> R2 с некоторой границей на \-нормированной плоскости (R2, р\) является локально минимальной, если и только если одновременно выполняются следующие условия:

1) каждая вершина степени 1 — граничная;

2) для любых двух смежных ребер -уi и jj выполняется неравенство

3) если 7i и 72 — смежные ребра, инцидентные внутренней вершине степени 2, то a(fl(7i),fl(72)) > я- - -;

4) для любых двух смежных ребер 7, и 7j, инцидентных внутренней вершине степени к, к^ 3, выполняется неравенство

Пусть 7i и 72 — произвольные смежные ребра сети Г, г = 1, 2. Будем говорить, что пара (71,72) имеет погрешность к, и будем писать £all(7i, 72) = к, если

Следующие три главы посвящены экстремальным сетям на А-нормиро-ванных плоскостях, где 2А = х (mod 3), А ф 2, 3, 4, 6.

Во второй главе выделяется класс подсетей исходной сети Г. Сети из этого класса, существенные сети, имеют достаточно простую структуру, и экстремальность сети Г зависит только от экстремальности сетей из этого класса.

Пусть Г: G —)■ R2 — произвольная погруженная сеть.

Определение. Максимальный путь в Г, все внутренние вершины которого имеют в Г степень 2 и не являются граничными вершинами для Г, назовем нитью.

13Konrad J. Swancpod. The Local Steiner Problem in Normed Planes 11 Networks. Vol. 36. 2000. Pp. 104-113.

иД. П. Ильютко. Локально минимальные сети в //-нормированных пространствах // Матем. заметки. 2003. Т. 74. Вып. 5. С. 656-668.

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

Определение. Сеть Г/ будем называть линеаризацией сети Г, если она получена заменой всех нитей сети Г на прямолинейные отрезки.

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

Утверждение 2. Погруженная сеть Г: С К2 является Х-экстремаль-ной тогда и только тогда, когда все ее нити — монотонные кривые, и линеаризация Г; сети Г является Х-экстремальной сетью.

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

Определение. Погруженная сеть на А-нормированной плоскости, не являющаяся звездой, называется существенной, если она является деревом и одновременно удовлетворяет следующим условиям:

1) для любых двух смежных ребер 7¿ и 7;- выполняются неравенства

< "(АЫ.АЫ) < /9(ЯЫ,Я(7;)) < + 1),

причем в случае, когда 7¿ и 7инцидентны граничной вершине и х = О,

27Г

последнее неравенство усиливается: /3(й(7;), й(7;-)) ^ — (в частности, все

и

вершины сети имеют степени не выше 3);

2) все вершины степени 1 и 2 — граничные, а степени 3 — внутренние;

3) дерево является объединением пути, все неконцевые ребра которого — точечные, и 1-граничных ребер, инцидентных некоторым внутренним вершинам этого пути, причем дополнительные ребра точечны, за исключением случая к = 0, для которого ребра, смежные с концевыми ребрами пути, могут быть неточечными;

4) углы между единственным ребром 1-усов и смежным с ним ребром

7Г /Г2А - 1, \ строго меньше — Ц—-—] +

5) углы между ребрами, инцидентными вершине усов степени 3, не равны между собой.

Замечание. Любая существенная сеть является локально минимальной. Основная теорема второй главы формулируется следующим образом:

Теорема 3. Пусть Г: G —» R2 — произвольное погруженное локально минимальное дерево на Х-нормированной плоскости. Тогда дерево Г Х-экстре-мально, если и только если каждая максимальная по включению существенная подсеть в Г Х-экстремальна.

Третья глава посвящена описанию деформаций, которые достаточно рассмотреть для проверки экстремальности сети.

Рассмотрим произвольную существенную сеть Г: G —> R2 на А-нормиро-ванной плоскости. Из определения существенной сети следует, что сеть Г имеет всего один тип расщепления Г': G' -f R2 (базовый), который получается из Г расщеплением только граничных вершин степени 2. Пусть z = {Г: и —> R2} — произвольная вершина сети Г: G -* R2, инцидентная ребрам 7,-, которые ориентированы от нее. Обозначим через "H(z) = : Н(и) —>■ R2 приведенную компоненту сети Г' такую, что ~H(z) (#(-u)) = Г (и). При этом, если z является внутренней вершиной степени 3, то Н(и) — и' — и, и если z — граничная вершина степени 2, то Н(и) = [и', г/], где г/ — граничная вершина степени 1, aw' — внутренняя вершина степени 3. Положим т! = {Г': «' н- R2}.

Определение. Вершина z! называется представителем вершины z сети Г в сети Г'.

Определение. Пусть степень вершины z равна 2. Деформация г): V& R2 сети Г' называется допустимой в вершине J, если или т)(и') = 0, или угол

между т}(и') и направлением не 1-граничного ребра 7* равен ^ [—4—] > & угол

А о

тг Л I 2

между т)(и') и направлением ji, I ф к, не больше -[—-—].

Л <5

Пусть степень вершины z равна 3, и два ребра, скажем 72 и 73, являются неточечными. Этот случай имеет место только для 2Л = 0 (mod 3). Без ограничения общности будем считать, что fall(7i,72) = 3.

Определение. В сделанных предположениях, деформация rj: Vq> 4R2 сети Г' называется допустимой в вершине г?, если или г](и') = 0, или rj(u') имеет точечное направление, которое образует с направлением ребра л, i =

7Г

1, 2, угол не больше —.

О и V

Пусть степень вершины z равна 3, и, по крайней мере, два ребра являются точечными.

Определение. В сделанных предположениях, деформация rj: Vq< R2 сети Г' называется допустимой в вершине z', если вектор rj(u') коллинеарен точечному направлению некоторого ребра 7,-, причем оставшиеся из инцидентных z ребер не образуют усы. При этом, т](и') не сонаправлен с ребром

Ур, если одно из оставшихся ребер 7, и 7Г, где Я ф р, г ф р, скажем 7,, не является 1-граничным, а другое, 7Г, удовлетворяет одному из следующих условий:

А + 2

1) £а11(7ч, 7Г) > 3[—-—] - А, когда 7Г или не является 1-граничным ребром, или является неточечным,

А + 2

2) Га11(7?17Г) > 3[ ^ ] - А или £а1](тд, 7Г) = £а11(7Р, 7Г), когда 7Г является точечным 1-граничным ребром.

Аналогично, 77(1*') не противоположно направлен ребру 7Р, если одно из оставшихся ребер -уч и 7Г, где д Ф р, г ф р, скажем 7?, не является 1-граничным, а другое, 7Г, удовлетворяет одному из следующих условий:

1) £а11(7?, 7Г) < 3[-] — А, когда 7Г не является 1-граничным ребром,

х

2) £а11(79,7г) < 3[-] — А, когда 7Г является неточечным,

3Л

3) £а11(7„7г) < 3[-] - А или £а11(79,7г) = £а11(7р,7г), когда является точечным 1-граничным ребром.

Определение. Деформация 77: Уа> —► К2 сети Г' называется допустимой, если она допустима в каждой вершине сети Г' и удовлетворяет следующему условию: если 7 = {Г': [щ,и2] -» К2} — произвольное ребро сети Г', и векторы г}{и\) и т]{и2) одновременно не равны нулю и не параллельны образу ребра 7, то вектор г}{и{) — т)(и2) параллелен образу ребра 7 (условия т](щ) ф 0, г = 1, 2, и определение приведенной компоненты гарантируют, что 7 — невырожденное ребро).

Пусть х 6 К" — произвольная точка, и т; € Т^Д" «К" — любой вектор. Через р(т}) будем обозначать субградиент функции р\ в точке х, причем, если т} и х ф 0 коллинеарны, то р(т/) — любой такой ковектор, а если т} и х ф 0 линейно независимы, то р(т]) удовлетворяет следующему дополнительному условию: вектор р(т)) ортогонален, в смысле евклидова скалярного произведения, радиальной проекции луча х + 4 > 0, на сферу Для произвольного невырожденного ребра 7 = [х, у] и произвольных векторов VI, % € К" положим рг(7, щ, тц) = Р\{г)\ - %) = -Рг('й - VI), где р^г]) — субградиент р(т/), вычисленный в точке п, = (—1)'(у - х)/||у - х||. Здесь || • || — евклидова норма.

Основной результат главы 3 — это следующие две теоремы, показывающие, что для проверки экстремальности сети достаточно рассмотреть конечное число деформаций и проверить конечное число неравенств.

Теорема 4. Пусть Г: б К2 — произвольная существенная сеть на (К2,рл), и Г': С —> И2 — единственный базовый тип ее расщепления. Пусть Яг>(х)

— множество регулярных ребер сети Г', инцидентных вершине х сети Г". Тогда Г экстремальна, если и только если для каждой допустимой деформации г): Vg> -* R2 следующая сумма по всем приведенным компонентам H{z) : H (и) -*■ R2 сети Г', где z = {Г : и -* R2} — вершина сети Г, неотрицательна:

®(Г,ч)= £ (¿ЫтМА v№)), +

7i={r': [u',u;]->R2}€ бДг'М, «=1,2,3

+ £ {(h PuU •?(«'), *K«Î)). vin1)) + рл(г?(«'))} > 0.

€Дг'(г'), <=1,2

Определение. Деформация r): Va- R2 сети Г" называется строго допустимой, если она допустима, не равна нулю в каждой внутренней вершине графа G' и удовлетворяет следующему условию: если j — {Г': [«1,иг] —>• R2}

— произвольное не 1-граничное невырожденное ребро сети Г', то векторы t](ui) и T](u2) не параллельны, а вектор т)(щ)—r}{u-î) параллелен образу ребра у.

Замечание. Не для каждой существенной сети существует хотя бы одна строго допустимая деформация.

Замечание. Из равенства D(T',ar]) = о©(V,tj) для любого а ^ 0 вытекает, что неравенство V (Г', 77) ^ 0 достаточно проверить лишь для конечного числа строго допустимых деформаций. В качестве деформаций мы выбираем деформации т? с Ц77Ц = 1, где ||r?|| = maxvçva, ||т?(х)||. Пусть Л(Г') = {ш,- - ,Vk} — все строго допустимые деформации для Г" с единичной нормой.

Теорема 5. Пусть Г: G ->• R2 — произвольная существенная сеть на плоскости (R2,pa) с единственным базовым типом Г': G' —>• R2 своего расщепления, и Гт : Gm —» R2, m = 1,... , l, — все ее существенные собственные подсети с базовыми типами Г^ : G'm R2 своего расщепления. Тогда сеть Г экстремальна, если и только если для всех строго допустимых деформаций г] € Л(Г') и 6 Л(Г^) выполнены неравенства 3)(Г',Т}) > 0, Ю(Г'т,г/,„) ^ 0. Таким образом, условие экстремальности существенной сети сводится к проверке справедливости конечного числа неравенств на компоненты векторов Г) и Т)т.

В четвертой главе, используя результаты предыдущих двух глав, мы формулируем критерий экстремальности произвольного дерева на А-норми-рованной плоскости при А ф 2, 3, 4, 6.

Рассмотрим произвольную пару (7, У) смежных ребер, ориентированных от их общей вершины. Определим знак 6(7, У) этой пары следующим образом:

— для линейно независимых ребер 7 и 7' положим 6(7, У) = 1, если базис (7, У) положительно ориентирован на R2, и е(-у, У) = — 1 в противном случае;

— для линейно зависимых ребер 7 и У положим €(7, У) = 1.

Определим для пары (7, У) ориентированную погрешность fallo(7, У), положив: fallo(7,y) = 6(7,y)fall(7,y).

Рассмотрим произвольный ориентированный путь V — {7^... , 7„} в сети Г, где тi — последовательные ребра пути V. При каждом 1 ^ г < п — 1 внутренней вершине z¡ пути V, инцидентной ребрам 7¿ и 7¿+i, поставим в соответствие знак e(7¿, 7,+i).

Определение. Путь V называется правильно повернутым, если все внутренние вершины пути V, граничные в сети Г, имеют одинаковый знак. Ориентация правильно повернутого пути V называется канонической, если знак каждой внутренней вершины пути V, граничной в сети Г, положителен.

Определим для канонически ориентированного пути V, все внутренние ребра которого точечны, ориентированную погрешность fallo (Я), положив:

fallo (Р) = max (fallo (7Í', 72) + "¿? fallo (7¿, 7¿+i) + fello(7»-i, 7n)),

где 3fl(7g) = {7¿i7j}, 9 = 1 или n, — граница подмножества fl(79) из S.

Пусть П — множество канонически ориентированных путей в Г, все внутренние ребра которых точечны. Положим

Fallo(r) = max fallo (Р).

Геометрический критерий экстремальности произвольного дерева, доказываемый в диссертации, звучит следующим образом:

Основная теорема. Произвольное погруженное дерево Г: G R2, не содержащее внутренних вершин степени 2, экстремально на Х-нормированной плоскости тогда и только тогда, когда все вершины степени 1 являются граничными и Fallo (Г) < 3.

Пятая глава посвящена вопросам, касающимся топологической и пленарной реализации, а также поведению экстремальных сетей на А-нормиро-ванных плоскостях, когда А —► оо.

Определение. Будем говорить, что топологический граф б допускает топологическую Х-минимальную (X-экстремальную) реализацию, если существует вложенная локально минимальная (экстремальная) сеть Г: б —> Н2 на Л-нормированной плоскости.

Определение. Две вложенные сети Г^: С? К2 и Г2: (7 —> К2 называются планарно эквивалентными, если существует деформация в классе вложенных сетей, переводящая одну сеть в другую, причем граница переходит в границу. Будем говорить, что сеть Г: С К2 допускает планарную Х-минимальную (Х-экстремалъную) реализацию, если существует планарно эквивалентная ей локально минимальная (экстремальная) сеть Г': О К2 на Л-нормированной плоскости.

Определение. Дерево Т с некоторой границей называется деревом Штей-нера, ест степени всех вершин не больше 3, а все вершины степени 1 являются граничными.

Основная теорема позволяет доказать следующий результат.

Теорема 6. 1) Топологическое дерево Т допускает топологическую Х-минимальную (Х-экстремальную) реализацию тогда и только тогда, когда Т является деревом Штейнера.

2) Вложенное дерево Г: Т К2 допускает планарную X-минимальную (Х-экстремальную) реализацию тогда и только тогда, когда Т является деревом Штейнера.

Рассмотрим произвольную вложенную сеть Г: б —> К2 и последовательность вложенных сетей {Г„: —У К2}^, планарно эквивалентных сети Г.

Определение. Будем говорить, что последовательность сетей {Г,,}^ (строго) сходится к сети Г, если для каждой вершины ь из С последовательность {Г,,^)}^! сходится к Г (и) (и для каждой граничной вершины и> € дС справедливо равенство Г„(го) = Г(го) ). Под сходимостью здесь понимаем стандартную сходимость последовательности на стандартной евклидовой плоскости.

Определение. Дерево Т с некоторой границей называется бинарным, если все его граничные вершины имеют степень 1, а внутренние — 3.

В заключении мы формулируем и доказываем теорему об асимптотике А-экстремальных сетей при А —> оо.

Теорема 7. Для любого вложенного экстремального (бинарного) дерева Г на стандартной евклидовой плоскости существует последовательность вложенных планарно эквивалентных Г А-экстремальных деревьев, (строго) сходящаяся к Г при А —> оо.

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

Публикации автора по теме диссертации

[1] Д. П. Илъютко. Локально минимальные сети в iV-нормированных пространствах // Матем. заметки. 2003. Т. 74. Вып. 5. С. 656-668.

[2] Д. П. Илъютко. Геометрия экстремальных сетей на А-нормированных плоскостях // Вестник МГУ, сер. 1. Матем. Мех. 2005. N 4. С. 52-54.

[3] Д. П. Илъютко. iV-нормированные плоскости // В книге: А. О. Иванов, A.A. Тужилин. Теория экстремальных сетей, Москва-Ижевск: Институт компьютерных исследований. 2003. С. 319-341.

[4] Д. П. Илъютко. Локально минимальные и экстремальные сети на п-нормированных плоскостях // Труды Воронежской зимней математической школы 2004. Воронеж: ВорГУ. 2004. С. 82-88.

[5] Д. П. Илъютко. Экстремальные сети на плоскостях Минковского // Материалы VIII Международного семинара "Дискретная математика и ее приложения". Тезисы. Москва 2004. Издательство мех-мат МГУ. С. 392-395.

[6] Д. П. Илъютко. Геометрический критерий экстремальности произвольного дерева на A-нормированной плоскости, где 2А = 1 (mod 3) и А > 5 // Международная школа-конференция по анализу и геометрии, посвященная 75-летию академика Ю. Г. Решетняка. Тез. док. Новосибирск. 2004". С. 108-111.

[7] Д. П. Илъютко. Геометрический критерий экстремальности произвольного дерева на A-нормированной плоскости, где 2А = 2 (mod 3) и А ^ 7 // Труды участников международной школы-семинара по геометрии и анализу памяти Н. В. Ефимова. Тез. док. Ростов-на-Дону. 2004. С. 27-29.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. Подписано в печать ОЧ.Ш.ОВ Формат 60x90 1/16. Усл. печ. л. 1,0

Тираж 100 экз. Заказ Л

» 1 8 7 20

РНБ Русский фонд

2006-4 16008

Задачи, связанные с изучением локально минимальных сетей, т.е. кратчайших в малом, и экстремальных сетей, т.е. критических точек функционала нормированной длины,гое определение которых см. ниже, появляются при обобщении следующей классической задачи, известной в литературе как проблема Штейнера: среди всех сетей, затягивающих данное конечное множество X точек евклидовой плоскости, найти сеть наименьшей длины. Решение этой задачи называется кратчайшей или абсолютно минимальной сетью, затягивающей множество X. Отметим, что с точки зрения римановой геометрии, локально минимальные сети являются естественным обобщением обычных геодезических. Действительно, локально минимальная сеть, затягивающая две произвольные точки на некотором римановом многообразии, представляет собой обычную геодезическую, т.е. кратчайшую в малом кривую. Более подробный исторический обзор, посвященный проблеме Штейнера, можно найти в [4, 5, 25, 31].

Традиционно больше внимания уделяется изучению локально минимальных и кратчайших сетей, чем изучению экстремальных сетей. Это связано с тем, что в случае функционала римановой длины, если разрешено расщеплять вершины, классы локально минимальных и экстремальных сетей совпадают, см. [15]. В данной работе рассматриваются сети на А-нормированных плоскостях, т.е. на нормированных плоскостях (Е2,рл), для которых единичная окружность Е = {жб М2| р\(х) = 1} совпадает с правильным 2А-угольником, одна из осей симметрии которого лежит на оси абсцисс. Важными отличиями этих нормированных плоскостей от стандартной евклидовой плоскости являются отсутствия гладкости единичной окружности £ и строгой выпуклости единичного круга, ограниченного £. Часто нормы, для которых единичная окружность Е является гладкой, называют гладкими, а нормы, для которых единичный круг строго выпуклый, — строго выпуклыми. Оказывается, на этих А-нормированных плоскостях, ввиду отсутствия гладкости нормы, класс локально минимальных сетей существенно шире класса экстремальных сетей.

Первые работы, посвященные изучению проблемы Штейнера на нормированных плоскостях, появились в 60-е годы XX века, см. [6], в связи с бурным развитием электроники и робототехники. В 1966 г. Ханан [8] провел исследование кратчайших прямоугольных деревьев, т.е. кратчайших сетей на 2-нормированной, так называемой манхеттенской, плоскости, и описал несколько важных общих геометрических свойств таких сетей. Он указал максимальную степень, которую могут иметь как внутренние, так и граничные вершины кратчайшей сети на манхеттенской плоскости, а именно, что эта степень равна 4 для всех вершин. Также Ха-нан показал, что всегда существует кратчайшее прямоугольное дерево, которое является подмножеством решетки Ханана — множества всех вертикальных и горизонтальных прямых, проходящих через граничные точки. Позже Хванг [9] описал структуру некоторых кратчайших сетей на манхеттенской плоскости, но эффективный алгоритм, строящий кратчайшую сеть, найти не удалось. В 1977 г. Гэри и Джонсон [7] показали, что задача поиска кратчайшего прямоугольного дерева, затягивающего п различных точек плоскости, является Л^Р-полной. Последнее означает, что, скорее всего, для этой проблемы не существует полиномиального алгоритма, т.е. алгоритма, решающего задачу за время 0(пк), где к — некоторое фиксированное число. Тем не менее, на практике приходится строить кратчайшие деревья, затягивающие большое количество точек плоскости, поэтому изучение ограничений на структуру кратчайших сетей является важным для приложений. Эти ограничения позволяют сокращать набор претендентов на кратчайшую сеть. Например, хорошо I известно, что степени вершин кратчайших сетей на стандартной евклидовой плоскости должны быть не больше 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 можно интерпретировать как набор конечных (терминальных) пунктов. Если, например, терминальные пункты города, которые требуется соединить сетью дорог, то в этом случае минимальная сеть — это самая дешевая транспортная система, обеспечивающая коммуникации между данными конечными пунктами. Здесь естественно предполагается, что стоимость коммуникаций пропорциональна их длине. Другие приложения проблемы Штейнера — это разводка микросхем и построение эволюционных деревьев. Основная проблема при разводке микросхем — это минимизация длины проводников на печатных платах. Эти проводники имеют вид ломанных линий, составленных из горизонтальных и вертикальных отрезков. Таким образом, разводка микросхем имеет непосредственное отношение к проблеме Штейнера на манхеттенской плоскости. Эволюционные деревья часто моделируются кратчайшими сетями в филогенетических пространствах, т.е. в пространствах слов с соответствующей метрикой.

Теорией экстремальных сетей много занимались А. О. Иванов и A.A. Тужилин [12, 14, 15, 17]. В своих работах [15, 17] они показали, как по каждой сети можно построить систему неравенств, выполнение которых при каждом значении переменных равносильно экстремальности исходной сети. Функции, входящие в эту систему, устроены достаточно сложно, в них даже могут встречаться условные операторы, поэтому, в общем случае, проверка справедливости этих неравенств может оказаться чрезвычайно трудоемкой. Один из результатов настоящей диссертации состоит в том, что для условия экстремальности дерева на А-нормирован-ной плоскости достаточно показать справедливость неравенств системы для деревьев простого вида и лишь для конечного набора значений переменных. А. О. Иванов и А. А. Тужилин [15, 17] получили, используя систему обсужденных выше неравенств, геометрический критерий экстремальности локально минимальной сети на 2-нормированной плоскости. Настоящая диссертация дает геометрический ответ на вопрос, когда дерево является экстремальным на А-нормированной плоскости для всех А, за исключением А = 2, 3, 4, 6. Для получения этого ответа были выбраны методы теории экстремальных сетей, разработанные А. О. Ивановым и A.A. Тужилиным [12, 14, 15, 17]. Была построена характеристика дерева, ориентированная погрешность, которая является аналогом числа вращения дерева на евклидовой плоскости. Оказывается, что эта погрешность полностью отвечает за экстремальность дерева на А-нормированной плоскости. Сама ориентированная погрешность дерева считается достаточно просто: сначала определяется ориентированная погрешность между двумя смежными ребрами как кососимметричная функция от их направлений; затем для всех путей, входящих в дерево и удовлетворяющих некоторым дополнительным условиям, определяется ориентированная погрешность как сумма ориентированных погрешностей во внутренних вершинах; наконец, вычисляется максимум ориентированных погрешностей всевозможных ориентированных путей, удовлетворяющих некоторым дополнительным условиям.

Поскольку дерево содержит конечное число путей, для любого дерева мы можем за конечное число шагов вычислить ориентированную погрешность и проверить его экстремальность. Отметим, что ориентированная погрешность пути определяется только самим путем, т.е. ребра, не входящие в путь, но смежные с ним, не влияют на результат. Для некоторых деревьев критерий экстремальности в терминах погрешности позволяет достаточно быстро отвечать на вопрос об их экстремальности. Так, в диссертации критерий применяется к деревьям, которые представляют собой путь. Критерий, получаемый в этом случае, достаточно прост и нагляден, см. теорему 4.17. Также в диссертации исследуется вопрос о реализации дерева в виде локально минимального или экстремального дерева на Л-нормированной плоскости и поведение экстремального дерева на А-нормированных плоскостях при Л —оо. Как и следовало ожидать, при достаточно больших Л структура экстремального дерева на Л-нормированной плоскости близка к структуре экстремального дерева на евклидовой плоскости, т.е. степени вершин те же и углы между смежными ребрами приблизительно одни и те же.

Диссертация состоит из пяти глав.

Первая глава посвящена описанию основных используемых в работе понятий и результатов, связанных с теорией сетей. Эта глава основывается на [12, 14, 15, 17, 18, 29, 32]. В первом параграфе вводятся определения сети, границы сети, подсети, деформации сети, типа расщепления сети, которые будут использоваться в дальнейшем.

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

В параграфе 1.3 мы вводим понятие экстремальной и слабо экстремальной сети, кратчайшей и локально минимальной сети. Теорема 1.1 показывает, что в любом нормированном пространстве классы локально минимальных и локально экстремальных сетей совпадают. Итогом этого параграфа являются теоремы 1.3 и 1.4. В теореме 1.3 приведена формула первой вариации для сетей, а теорема 1.4 показывает, какие типы расщепления сети достаточно рассмотреть для проверки экстремальности. Эти типы расщепления называются базовыми.

Основным результатом четвертого параграфа является теорема 1.5. Эта теорема представляет собой геометрический критерий локальной минимальности произвольной сети на Л-нормированной плоскости. Также в этом параграфе вводятся важные понятия для ребер сети. Это точечное и неточечное ребро, а также погрешность между двумя смежными ребрами. Все эти понятия будут использоваться при формулировке критерия экстремальности произвольного дерева.

Последующие главы посвящены экстремальным деревьям на А-норми-рованных плоскостях, где А ф 2, 3, 4, 6. В первых трех из них основные усилия направлены на выяснение того, когда произвольное дерево на А-нормированной плоскости является экстремальным. А в последней главе применяется полученный критерий экстремальности дерева к проблеме реализации дерева и сходимости экстремальных деревьев при А —> оо.

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

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

2.8. Утверждение 2.3 выделяет из класса граничных вершин степени

2 те вершины, которые можно разрезать с сохранением экстремальности, а утверждение 2.4 показывает, что все граничные вершины степени

3 можно разрезать с сохранением экстремальности. Следующие четыре утверждения относятся к операции разрезания по ребру. Из утверждений 2.5 и 2.6 выясняется, что неточечное ребро всегда можно разрезать с сохранением экстремальности, а точечное разрезаемо с сохранением экстремальности при выполнении некоторых дополнительных условий. Утверждения 2.7 и 2.8 имеют дело не с самим ребром, а с вершиной. Они показывают, что для некоторых внутренних вершин экстремальность всего дерева равносильна экстремальности деревьев, полученных разрезанием по каждому в отдельности ребру, инцидентному этой вершине.

Третий параграф второй главы начинается с определения существенной сети. Эти сети имеют достаточно простую структуру. Они представляют собой объединение пути и ребер, инцидентных некоторым внутренним вершинам этого пути. Поскольку, по определению, в существенных сетях все граничные вершины имеют степень 1 или 2, а внутренние — степень 3, то для них имеется всего один базовый тип расщепления, который получается расщеплением граничных вершин степени 2. Углы между смежными ребрами существенной сети определяются из условия ее локальной минимальности и из условий, описывающих, какие граничные вершины разрезаются с сохранением экстремальности. Далее в этом параграфе приводится алгоритм, который каждому локально минимальному дереву, не содержащему внутренние вершины степени 2, ставит в соответствие набор максимальных существенных его подсетей. Эти сети называются существенными представителями. В дальнейшем описанный алгоритм используется для доказательства теоремы 2.2, утверждающей, что для проверки экстремальности дерева достаточно проверить экстремальность максимальных существенных представителей данного дерева.

Третья глава посвящена деформациям существенных сетей. Для каждой сети рассматривается единственный базовый тип расщепления, который получается расщеплением всех граничных вершин степени 2, и на основании структуры базового типа расщепления выделяются так называемые допустимые деформации и строго допустимые деформации. Отметим, что важным условием того, куда будет двигаться вершина при допустимой деформации, являются значения углов между смежными ребрами в этой вершине. При этом модули векторов скорости движения вершин при строго допустимой деформации взаимосвязаны, т.е., фиксировав один из модулей, мы можем определить все остальные. Таким образом, направления движений вершин определяются только локальными свойствами, а модули векторов скоростей — не локальны. Отметим, что при допустимой деформации сети каждая вершина может двигаться не более чем в четырех направлениях, а при строго допустимой — не более чем в двух. Поскольку длины векторов строго допустимой деформации взаимосвязаны, то каждый базовый тип расщепления существенной сети имеет конечное (возможно нулевое), с точностью до нормирующего множителя, число таких деформаций. Теоремы 3.1, 3.2, 3.3 этой главы показывают, что для проверки экстремальности сети достаточно рассмотреть только строго допустимые деформации с единичной нормой, а также, что существенная сеть экстремальна тогда и только тогда, когда первая вариация для каждой ее существенной подсети неотрицательна при любой строго допустимой деформации с единичной нормой. Так как каждая сеть имеет конечное число подсетей и каждая существенная сеть имеет конечное число строго допустимых деформаций, то для проверки экстремальности дерева достаточно проверить справедливость конечного числа неравенств лишь в конечном наборе значений переменных.

Четвертая глава завершает описание структуры экстремальных сетей на А-нормированных плоскостях.

Первые три параграфа посвящены переходу от сетей к словам. Для удобства изложения существенные сети кодируются словами, при этом нескольким сетям может соответствовать одно и то же слово. Вводится понятие подслова, которое соответствует понятию существенной подсети. Во втором параграфе формула первой вариации сети переписывается в терминах слов. На основании этой формулы в третьем параграфе определяются положительные (справа, слева) слова и полуэкстремальные (справа, слева) слова. Теорема 4.1 утверждает, что сеть экстремальна тогда и только тогда, когда слово, соответствующее ей, полуэкстремально справа и слева.

В следующих трех параграфах исследуется полуэкстремальность слов. Сначала каждому слову при 2А = 1,2 (mod 3) ставится в соответствие некоторый набор так называемых простейших слов. Для этого используется операция редукции, подобная той, которая была определена для деревьев. Оказывается, что полуэкстремальность слова равносильна полуэкстремальности простейших слов, которые строятся по исходному слову, теорема 4.3. Для случая 2А = 0 (mod 3) полуэкстремальность слова связана с существованием строго допустимых деформаций существенных сетей, представленных подсловом исходного слова, теорема 4.8. На основании этого формулируется критерий полуэкстремальности слова. А именно, для каждого слова вводится понятие кручения, которое и ответственно за полуэкстремальность слова для случаев 2А = 1,2 (mod 3). Основные результаты этих параграфов — теорема 4.6 и теорема 4.8. Первая утверждает, что слово о полуэкстремально тогда и только тогда, когда кручение каждого подслова слова а не больше нуля при 2А = 1 (mod 3) и не меньше нуля при 2А = 2(mod3). Вторая теорема относится к 2А = 0 (mod 3) и показывает, что слово а полуэкстремально тогда и только тогда, когда для каждой существенной сети, представленной подсловом слова а, не существует строго допустимой деформации. Используя теоремы 4.1, 4.6 и 4.8, в седьмом параграфе мы приводим критерий экстремальности существенной сети в терминах соответствующего ей слова, теорема 4.9.

Главный результат четвертой главы заключен в следующих двух параграфах. Сначала вводится понятие ориентированной погрешности между двумя смежными ребрами, которая характеризует ориентированный угол между ними. Следующий шаг — это определение ориентированной погрешности сети, которая является аналогом числа вращения сети в евклидовом случае. Далее устанавливается связь между ориентированной погрешностью сети и кручением слова для случаев 2А = 1,2 (mod 3), а также между ориентированной погрешностью сети и существованием строго допустимой деформации сети для случая 2А = 0 (mod 3). Переходя от слов к существенным сетям и пользуясь теоремой 4.9, доказывается теорема 4.15 — критерий экстремальности существенной сети: существенная сеть экстремальна тогда и только тогда, когда ее ориентированная погрешность не больше 3. Используя теорему 4.15 и результаты предыдущих двух глав, мы доказываем основную теорему — геометрический критерий экстремальности произвольного дерева в терминах ориентированной погрешности. Основная теорема утверждает, что произвольное дерево экстремально тогда и только тогда, когда его ориентированная погрешность не больше 3.

В заключительном параграфе этой главы мы применяем критерий экстремальности к деревьям, все вершины которых суть граничные вершины степени 1 или 2. Каждому дереву ставится в соответствие некоторая последовательность целых чисел. Теорема 4.17 показывает, что если последовательность содержит подпоследовательность некоторого специального вида, то дерево не является экстремальным. Из этой теоремы видно, что пути в экстремальных деревьях не могут сильно "закручиваться" в одну сторону с минимально возможным углом.

В пятой главе работы рассматриваются свойства экстремальных сетей и вопросы, касающиеся топологической и планарной А-минимальных (экстремальных) реализаций деревьев, т.е. реализаций этих деревьев в виде локально минимальных (экстремальных) деревьев на А-нормирован-ных плоскостях, а также поведения экстремальных сетей на А-нормиро-ванных плоскостях при А —^ оо.

Первый параграф содержит теоремы, касающиеся поведения ориентированной погрешности при редукциях и антиредукциях дерева. Теоремы 5.1, 5.2, 5.3 дают оценку на ориентированную погрешность дерева, полученного из данного дерева с помощью некоторой операции, и в некоторых случаях позволяют сказать, когда новое дерево экстремально, см. следствие 5.1.

Основной результат второго параграфа — это критерий А-экстре-мальной реализации дерева, теорема 5.5. Эта теорема утверждает, что дерево А-экстремально реализуется тогда и только тогда, когда оно является деревом Штейнера.

Третий, он же заключительный параграф главы, содержит теоремы о поведении экстремальных сетей на А-нормированных плоскостях при

Л —У оо. Теорема 5.7 утверждает, что для любого вложенного экстремального дерева Г на стандартной евклидовой плоскости существует последовательность вложенных планарно эквивалентных Г экстремальных деревьев на А-нормированных плоскостях, сходящаяся к Г при А —> оо. В то же время, это утверждение не имеет места, если дополнительно потребовать, чтобы границы всех приближающих Г сетей совпадали. Теорема 5.8 показывает, что если дерево Г является бинарным, то утверждение теоремы 5.7 верно и с дополнительным требованием совпадений границ.

Автор выражает глубокую и искреннюю благодарность своим научным руководителям д.ф.-м.н. проф. А. А. Тужилину и д.ф.-м.н. проф. А. О. Иванову за постановку задач, постоянное внимание и помощь в работе. Также автор благодарен Н. П. Долбилину, Н. С. Гусеву, Г. А. Кар-пунину, И. М. Никонову, C.B. Матвееву, И.Х. Сабитову, А. Т. Фоменко за полезные обсуждения результатов настоящей диссертации. Автор благодарен всем сотрудникам кафедры дифференциальной геометрии и приложений за творческий климат и поддержку.

Оглавление

1. Предварительные сведения 14

1.1. Общее определение сети .14

1.2. Операции над сетями.18

1.2.1. Разрезание сетей по вершинам и ребрам.18

1.2.2. Редукция вложенного дерева.19

1.2.3. Антиредукция вложенного дерева.20

1.3. Определения экстремальной и локально минимальной сети 21

1.4. Критерий локальной минимальности сети на А-нормированной плоскости .26

2. Существенные сети 32 4! 2.1. Линеаризация сети .32

2.2. Разрезания сети, сохраняющие экстремальность.34

2.2.1. Разрезания по граничным вершинам.34

2.2.2. Разрезания по ребрам.47

2.2.3. Вершины, инцидентные неточечному 1-граничному ребру.49

2.2.4. Вершины, инцидентные точечным ребрам.50

2.3. Существенные представители локально минимального дерева 51

3. Допустимые деформации 61 3.1. Сведение любой деформации к допустимой.61

4. Критерий экстремальности дерева на А-нормированной плоскости 71

4.1. Представление сети словом.71

4.2. Формула первой вариации существенной сети.77

4.3. Определения полуэкстремальных справа и слева слов . 84

4.4. Избавление от букв 63, 64, 65 и для к = 1, 2.84

4.5. Критерий полуэкстремальности слова для х = 1,2.88

4.5.1. Редукция внутри слова.89

4.5.2. Редукция в начале и в конце слова для к = 1 . 100

4.5.3. Редукция в начале и в конце слова для хг = 2 . 102

4.5.4. Простейшие слова и полуэкстремальность слов . . . 105

4.6. Критерий полуэкстремальности слова для х = 0.107

4.7. Критерий экстремальности существенной сети.109

4.8. Геометрический критерий экстремальности бинарной сети 110

4.8.1. Избавление от неточечных ребер.110

4.8.2. Определение ориентированной погрешности.112

4.8.3. Геометрический критерий экстремальности бинарной существенной сети.113

4.8.4. Геометрический критерий экстремальности бинарного дерева.116

4.9. Геометрический критерий экстремальности произвольного дерева.116

4.10. Некоторые следствия из основной теоремы .118

5. Свойства А-экстремальных сетей и их асимптотика при

А оо 120

5.1. Поведение погрешности при редукциях и антиредукциях . 120

5.2. Топологическая и планарная А-минимальные (экстремальные) реализации сети.124

5.3. Стандартная евклидова плоскость как предел А-нормиро-ванных плоскостей при А —оо.127

5.3.1. Сходимость сетей.127

5.3.2. Строгая сходимость сетей.131

Список литература 134

Список работ автора по теме диссертации 138

1. М. Alfaro, М. Conger, К. Hodges, A. Levy, R. Kochar, L. Kuklinski, Z. Mahmood and K. von Haam. The structure of singularities in Ф-minimizing networks in M2 // Pacific J. Math. 149. 1991. Pp. 201-210.

2. D. Cieslic. The vertex-degrees of Steiner minimal trees in Minkowski planes // Topics in Combinatorics and Graph Theory (R. Bodendiek and R. Henn, eds.). Physica-Verlag. Heidelberg. 1990. Pp. 201-206.

3. E.J. Cockayne. On the Steiner Problem // Canad. Math. Bull. 10. 1967. Pp. 431-450.

4. D. Z. Du, F. К. Hwang and J. F. Weng. Steiner minimal trees for Regular Polygons // Disk, and Comp. Geometry. Vol. 2. 1987. Pp. 65-84.

5. P. Fermat. Abhandlungen über Maxima und Minima //В книге: Oswalds, Klassiker der Exakten Wissenschaften. 1934. N 238.

6. R. L. Francis. A note on the optimum location of new machines in existing plant layouts // J. Indust. Engrg. Vol. 14. 1963. Pp. 57-59.

7. M. R. Garey and D.S. Johnson. The Rectilinear Steiner Problem is NP-Complete // SIAM J. Appl. Math. Vol. 32. 1977. Pp. 826-834.

8. M. Hanan. On Steiner's Problem with Rectilinear Distance // SIAM J. Appl. Math. Vol. 14. 1966. Pp. 255-265.

9. F. K. Hwang. On Steiner minimal trees with rectilinear distance // SIAM J. of Appl. Math. Vol. 30. 1976. Pp. 104-114.

10. А. О. Иванов. Геометрия плоских локально минимальных бинарных деревьев // Матем. сборник. 1995. Т. 186. N 9. С. 45-76.

11. А. О. Иванов. Геометрические свойства локально минимальных сетей // Дисс. доктора физ.-мат. наук, М.: МГУ. 1998.

12. А. О. Ivanov, A. A. Tuzhilin. Minimal Networks. Steiner Problem and Its Generalizations: CRC Press. 1994.

13. А. О. Иванов, А. А. Тужилин. Классификация минимальных скелетов с правильной границей // Успехи мат. наук. 1996. Т. 51. N 4. С. 157158.

14. А. О. Иванов, А. А. Тужилин. Разветвлённые геодезические. Геометрическая теория локально минимальных сетей. — The Edwin Mellen Press. Lewiston-Queenston-Lampeter 1999.

15. А. O. Ivanov, А. A. Tuzhilin. Branching Solutions to One-Dimensional Variational Problems. — World Scientific Publishing Co. Pte. Ltd. Singapore 912805. 2001.

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

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

18. Д. П. Ильютко. Локально минимальные сети в iV-нормированных пространствах // Матем. заметки. 2003. Т. 74. Вып. 5. С. 656-668.

19. Д. П. Ильютко. ЛГ-нормированные плоскости //В книге: А. О. Иванов, А. А. Тужилин. Теория экстремальных сетей. Москва-Ижевск: Институт компьютерных исследований. 2003. С. 319-341.

20. Д. П. Ильютко. Экстремальные сети на плоскостях Минковского // Материалы VIII Международного семинара "Дискретная математика и ее приложения". Тезисы. Москва 2004. Издательство мех-мат МГУ. С. 392-395.

21. Д. П. Ильютко. Локально минимальные и экстремальные сети на п-нормированных плоскостях // Труды Воронежской зимней математической школы 2004. Воронеж: ВорГУ. 2004. С. 82-88.

22. А. А. Тужилин. Полная классификация локально минимальных бинарных деревьев с правильной границей, двойственные триангуляции которых являются скелетами // Фундаментальная и прикладная математика. 1996. Т. 2. N 2. С. 511-562.

23. А. А. Тужилин. Классификация локально минимальных плоских сетей с выпуклыми границами // Дисс. доктора физ.-мат. наук, М.: МГУ. 1997.Список работ автора по теме диссертации

24. Д. П. Ильютко. Локально минимальные сети в iV-нормированных пространствах // Матем. заметки. 2003. Т. 74. Вып. 5. С. 656-668.

25. Д. П. Ильютко. iV-нормированные плоскости // В книге: А. О. Иванов, А. А. Тужилин. Теория экстремальных сетей, Москва-Ижевск: Институт компьютерных исследований. 2003. С. 319-341.

26. Д. П. Ильютко. Экстремальные сети на плоскостях Минковского // Материалы VIII Международного семинара "Дискретная математика и ее приложения". Тезисы. Москва 2004. Издательство мех-мат МГУ. С. 392-395.

27. Д. П. Ильютко. Локально минимальные и экстремальные сети на n-нормированных плоскостях // Труды Воронежской зимней математической школы 2004. Воронеж: ВорГУ. 2004. С. 82-88.

28. Д. П. Ильютко. Геометрия экстремальных сетей на А-нормирован-ных плоскостях // Вестник МГУ, сер. 1. Матем. Мех. 2005. N 4. С. 52-54