Геометрия локально минимальных и экстремальных сетей в пространствах с нормами (1102759), страница 2
Текст из файла (страница 2)
которые требуется соединить сетью дорог, .то в этом случае минимальная сеть это самая дешевая транспортная система, обеспечиваюшая коммуникации между данными конечными пунктами. Здесь естественно предполагается. что стоимость коммуникации пропорцио- нальна их длине.
Другие приложения проблемы Штейнера это разводка микросхем и построение эволюционных деревьев. Основная проблема при разводке микросхем это минимизапия длины проводников на печатных платах. Эти проводн1лки имеют вид ломанных линий. составленных из горизонтальных и вертикальных отрезков. Таким образом, разводка микросхем имеет непосредственное отношение к проблеме Штейнера на манхсттенской плоскости. Эволюционные деревья часто моделируются кратчайшими сетями в филогенетических пространствах.
т.е. в пространствах слов с соответствуюшси метрикои. Теорией экстремальных сетей много занимались А. О. Иванов и А. А. Тужилин ~12, 14, 15, 17~. В своих работах ~15. 17~ онп показали. как по каждой сети можно построить систему неравенств, выполнение которых при какдом значенилл переменных равносильно экстремальности исходной сети. Функции.
входящие в эту систему, устроены д(н;таточно сложно. в них даже могут встречаться условные операторы, поэтому. в общем случае, проверка справедливости этих неравенств может оказаться чрезвьг(айно трудоемкой. Один из результатов настоящей диссертации состоит в том, что для условия экстремальности дерева на Л-нормированной плоскости достаточно показать справедливость неравенств системы для деревьев простого вида и лишь для конечного набора значений переменных. А.О. Иванов и А.А.
Тужилин ~15, 17~ получили, используя систему обсужденных выше неравенств, геометрический критерий экстрем гльности локально минимальной сети на 2-нормллрованной плоскости. Настоящая диссертация дает геомстрическип ответ на вопрос, когда дер(во являет(..я экстремсзльным на Л-нормллров')нно11 пло( кости для вс(х Л, за исключением Л = 2. 3. 4, 6.
Для получения этого ответа были выбраны методы теории экстремальных сетей, разработанные А. О. Ивановым и А. А. Тужилиным [12, 14, 15, 17~. Была построена характеристика дерева, орненптрооанн(ля, 1)о;реп(ность, которая является аналогом плела враще- НИЯ ДЕ1ЭСВа На ЕВКЛПДОВОИ ПЛОСКОСТИ. ОксаЗЫВссЕТСЯ, ЧТО Эта. ПОГРЕШНОСТЬ полностью отвечает за экстремальность дерева на Л-нормированной плос- КОСТП. Сса.'сла ОРИЕНТЩ)овс)ННЗЯ ПОГРЕШНОСТЬ ДЕ1)ЕВа СслиТсКЕТСЯ ДОСтс1ТОс1НО просто: (начала определяет(я ориентированная погрешность между двумя смен(ными ребрамп как кососимметричная функция от их направлений: затем для всех путеи, входящих в дерево и удовлетворяющих некоторым дополнительным условиям, определяется ориентированная погрешность как сумма ориент(лрованных погрешностей во внутренних вер- шинах; наконец.
вычисляется максимум ориентированных погрешностей о всевозможных ориентированных путей, удовлетворяющих некоторым до- полнительным условиям. Поскольку дерево содержит конечное число путей, для любого дерева мы хложем за конечное число шагов вычислить ориентированную погрешность и проверить его экстремальность. Отметим, что ориентированная погрешность пути определяется только самим путем. т.е.
ребра, не входящие в путь. но смежные с ним, нс влияют на результат. Для некоторых деревьев критерий экстремальности в терминах погрешности позволяет достаточно быстро отвечать на вопрос об их экстремальности. Так„ в диссертации критерий применяется к деревьям. которые представляют собой путь. Критерий, получаемый в этом случае, достаточно прост и нагляден. см. теорему 4.17.
Также в диссертации исследуется вопрос о реализации дерева в виде локально минимального или экстремального дерева на Л-нормированной плоскости и псэведение экстремального дерева на Л-нормированных плоскостях при Л вЂ” + ж. Как и следовало ожидать, при достаточно больших Л структура экстремального дерева на Л-нормированной плоскости близка к структуре экстремального дерева на евклидовой плоскост1л, т.е.
степени вершин те же и углы между смежными ребрами приблизительно одни и те же. Диссертация состоит из пяти глав. Первая глава посвящена описанию основных используемых в работе понятий и результатов, связанных с теорией сетей. Эта глава основывается на [12. 14, 15, 17, 18. 29, 32]. В первом параграфе вводятся определения сети, границы сети, подсети, деформации септ, типа расьцеплсния сети, которые будут использоваться в дальнейшс м. Во втором параграфе описываются операции над сетями, такие как разрезание сети по вершине и ребру, редукция и антиредукция сети. Первые трьл операции применяются для упрощения проверки экстремальности произвольной сети. С помощью этих операцллй мы переходим к сетям более простого вида, экстремальность которых равносильна экстремальности исходной сети.
Последняя операция используется для построения экстремальных сетей общего вллда из экстремальных сетей простого вида. В параграфе 1.3 мы вводим понятие экспуэемальной и слабо экстремальной сети, кролпнайьией и локально минимальной сети. Теорема 1.1 показывает, что в любом нормированном пространстве классы локально минимальных и локально экстремальных сетей совпадают. Итогом этого параграфа являкэтся теоремы 1.3 и 1.4. В теореме 1.3 приведена формула первой вариации для сетей, а теорема 1А показывает, какие типы расщепления сети достаточно рассмотреть для проверки экстремальности.
Зти типы расщепления называются базовыми. Основным результатом четвертого параграфа является теорема 1.5. Эта теорема представляет собой геометрический критерий локальной минимальности произвольной сети на Л-нормпрованной плоскости. Также в этом параграфе вводятся важныс понятия для ребер сети. Это точечное и неточечное ребро, а также ноарсшноеть между двумя смежными ребрами.
Все эти понятия будут использоваться при форму- лировкс критерия экстремальности произвольного дерева. Последующие главы посвящены экстремальным деревьям на Л-нормированных плоскостях, где Л ~ 2, 3, 4, 6. В первых трех из них основные усилия направлены на выяснение того, когда произвольное дерево на Л- нормированной плоскости является экстремальным. А в последней главе применяется получснньш критерий экстремальности дерева к проблеме реализации дерева и сходпмости экстремальных деревьев при Л вЂ” + =с. Вторая глава содержит три параграфа. В первом параграфе пока- зывается, как свести проверку экстремальности произвольного дерева к проверке экстремальности дерева, не содержащего внутренние вершины степени 2.
Такие деревья называются линеоризоеанными. Основной результат этого параграфа, утвсрждснллс 2.2, заключается в том, что сеть экстрсмальна тогда и только тогда, когда все сс нити являются монотон- ными кривыми, а линсаризованная сеть зкстрсмальна. Во втором параграфе изучается, какие операции сохраняют экстре- мальность. т.е. выясняется, когда экстремальность сети равносильна экстремальности сетей, полученных в результате применения этих операций. Ключсвыхл результатом этого параграфа являются утвср кдснпя 2.3 2.8. Утверждение 2.3 выделяет из класса граничных вершин степени 2 те вершины, которые можно разрезать с сохранением экстремальности. а утверждение 2А показывает, что все граничные вершины степени 3 можно разрезать с сохранением экстремальности.
Следующлле четыре утверждения относятся к операщл1л разрезания по ребру. Из утверждений 2.5 и 2.6 выясняется, что нсточсчнос ребро всегда можно разрезать с сохранением экстремальности, а точечное разрсзасмо с сохранением экстремальности прп выполнении некоторых дополнительных условии. Утверждения 2.7 и 2.8 имеют дело нс с самим ребром, а с вершиной. Они показывают, что для некоторых внутренних вершин экстремальность всего дерева равносильна экстремальности деревьев. полученных разрезанием по каждому в отдельности ребру, инцидентному этой вершине. Третий параграф второй главы начинается с определения существенной сети. Эти сети имеют достаточно простую структуру. Они представляют собой объединение пути и ребер.
инцидснтных некоторым вну- 7 тренним вершинам этого пути. Поскольку, по опрсдслсник)., в существенных сетях все граничные вершины имеют степень 1 или 2„а внутрсннис степень 3, то для них имеется всего один базовый тпп расщепления, который получается расщеплением граничных вершин степени 2. )'глы между смежными ребрами существенной сети определяются из условия ес локзльнои минимальности и из услоВИИ., ОписыВаюших., какие граничные Вершины разосзаются с сохе)анснЕлсм экстрсмальност11.
Далее В этом параграфе приводится алгоритм, которыи ка)кдому локально минимальному дереву. не содержащему внутрсннллс вершины степени 2, ставит в соответствие набор максимальных существенных его подсетей. Зти сети называются сулцестеенныии предстиеип)еанлли. В дальнейшем описанный алгоритм используется для доказательства теоремы 2.2. утвсржда- ющей, что для проверки экстремальности дерева достаточно проверить экстремальность максимальных существенных представителей данного дерева. Третья глава посвящена деформациям существенных сетей. Для каждой сети рассматривается единственный базовый тип расщепления, который получается расщеплением всех граничных вершин степени 2, и на основании структуры базового типа расщепления выделяются так называемые допустлАлте деформации и строго допуегпимые д)ефорлеиции. Отметим, что важным условием того, куда будет двигаться вершина при допустимой де11)О1)мацлллл, являя)тся зна~ленлля углов между смежнымел ребрами в этой вершине.
При этом модули векторов скорости движения вершин при строго допустимой деформации взаимосвязаны, т.с.. фиксировав один из модулеи, мы можем определить все сн тальные. Таким обра- зом, направления движении вершин определяк)тся только локальными своиствами, а модули векторов скоростей не локальны. Отметим, что прп допустллмой деформацлпл сети каждая вершллна может двигаться не более чем в четырех направлениях, а прлл строго допустимой не более чем в двух. Поскольку длины векторов строго допустимой деформации взаимосвязаны, то каждый базовый тип расщепления существенной сети имеет коне'Еное (ВОзможно пулевое).
с "го'1нос гьк) до н01)мщ)ук)шсго множителя, .число таких деформаций. Теоремы 3.1) .3.2, 3.3 этой главы показыван)т. что для проверки экстремальности сети достаточно рассмотреть только строго допустимые деформации с единичной нормой, а также, что существенная сеть экстремальна тогда и только тогда, когда первая вариация для каждой ее существенной подсети неотрицательна при лн)бой строго допустимой деформации с единичной нормой. Так как каждая сеть имеет конечное число подсетей и каждая существенная сеть имеет конечное число строго допустимых деформаций, то для проверки экстре- мальности дерева достаточно проверить справедливость конечного числа неравенств лишь в конечном наборе значений переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
