Теория Морса минимальных сетей (1105006), страница 6
Текст из файла (страница 6)
Естественно возникает следующий вопрос: Найдется ли граница (разумеется уже нена двумерном многообразии ), такая что для любого бинарного геометрического дерева существует локально минимальная сеть типа, затягивающая границу ?Данный вопрос известен как задача об универсальной границе, которая была сформулирована А. О. Ивановым и А. А. Тужилиным в работе [7]. Перед тем как дать ответ на этот вопрос сформулируем следующую теоремуТеорема 3.1 Пусть — граница, состоящая из вершин правильного -мерного симплекса евклидового пространства.
Тогда для любогогеометрического дерева соответствующая минимальная параметрическая сеть типа , затягивающая границу , невырождена (т.е.не имеет вырожденных ребер).Поскольку невырожденные минимальные параметрические сети являются регулярными, то, ограничиваясь в предыдущей теореме типамибинарных геометрических деревьев, получаем следствиеВведение27Следствие 3.2 Пусть — граница, состоящая из вершин правильного -мерного симплекса евклидового пространства. Тогда для любого бинарного геометрического дерева существует локально минимальнаясеть типа , затягивающая границу .Заметим, что свойство универсальности границы не пропадает прилюбых его малых деформациях.Напомним, что основным точным методом поиска минимального дерева Штейнера для данной границы ′ на евклидовой плоскости является построение всех локально минимальных сетей, затягивающих ′ , изатем выбор из них наименьшей по длине.
Пример универсальной границы показывает, что при решении таким методом задачи Штейнера дляданной (но произвольной) границы ′ в евклидовом пространстве достаточно большой размерности a priori нельзя откинуть ни один из комбинаторно возможных типов локально минимальных сетей. Таким образом,даже если бы существовал в многомерных евклидовых пространствах линейный алгоритм построения по данной границе ′ и данному бинарномутипу соответствующей локально минимальной сети, задача Штейнерарешалась бы за экспоненциальное время.Стоит отметить, что совокупность вершин правильного -мерногосимплекса в евклидовом пространстве является единственным, известным на данный момент, нетривиальным примером границы с произвольным количеством граничных точек, для которой описаны все локальноминимальные сети.Апробация работыРезультаты диссертации рассказаны и обсуждены на следующих семинарах и конференциях, проводимых на механико-математическом факультете МГУ им.
М. В. Ломоносова:— на семинаре А. О. Иванова и А. А. Тужилина по теории минимальных сетей;— на семинаре В. М. Бухштабера и О. Р. Мусина по вычислительнойгеометрии и топологии;— на семинаре В. И. Арнольда по теории особенностей;— на семинаре И. Х. Сабитова и Э. Р. Розендорна по геометрии вцелом;— на VII международном семинаре “Дискретная математика и ее приложения” (Москва, МГУ, 2001 г.);Введение28— на международной конференции, посвященной 100-летию со днярождения И. Г. Петровского (Москва, МГУ, 2001 г.).ПубликацииОсновное содержание диссертации опубликовано в 7 работах, список которых приведен в конце диссертации на стр. 179.Автор выражает глубокую и искреннюю благодарность своим научным руководителям д.ф.-м.н. А.
А. Тужилину и д.ф.-м.н. А. О. Иванову за постановку задач, постоянное внимание и помощь в работе. Также, автор хотел бы поблагодарить В. М. Бухштабера, В. А. Васильева, О. М. Касим-Заде, О. Р. Мусина, М. В. Пронина, Э. Р. Розендорна,И. Х. Сабитова, С. П. Тарасова, А. Т.
Фоменко за полезные обсуждениярезультатов настоящей диссертации. Автор признателен руководству математического отдела НИИ Автоматики за поддержку и понимание.Глава 1Сети в метрическихпространствахВ настоящей главе определяются базовые понятия и объекты даннойдиссертации.11.1Основные определенияСети, параметризующие графы, длина сетиПусть ( , ) — метрическое пространство.Рассмотрим конечный связный граф . Обозначим через () —множество вершин графа , а через () — множество ребер графа.Определение. Отображение Γ : () → назовем параметрическойсетью(или просто сетью) в пространстве . Сам граф называетсяпараметризующим графом сети Γ. Если для сети Γ требуется явно указать ее параметризующий граф , то мы будем использовать обозначение Γ[].Ограничение отображения Γ на вершину графа , т.е.
Γ| , будемназывать вершиной сети Γ. Ограничение отображения Γ на пару вершин (, ), образующих ребро (, ) графа , т.е. Γ|(,) , будем называть ребром сети Γ. Множество вершин сети Γ обозначим через (Γ), амножество ребер сети Γ — через (Γ).29Сети в метрических пространствах30Замечание. Согласно введенным выше определениям на сети в метрическом пространстве естественно переносится вся терминология теорииграфов: смежность, инцидентность, степень вершины, циклы, понятиедерева и т.д.Определение. Длиной ребра = Γ|(,) сети Γ будем называть величину ℓ() = (Γ(), Γ()). Ребро сети Γ назовем вырожденным ребром,если его длина нулевая.Для каждой сети Γ в метрическом пространстве ( , ) определимдлину сети Γ как сумму длин ее ребер, т.е.∑︁∑︁ℓ(Γ) =ℓ() =(Γ(), Γ()).∈(Γ)1.2(,)∈()Графы с границей, сети с границейВыделим некоторое подмножество множества вершин графа , которое назовем множеством граничных или неподвижных вершин графа , естественно сами вершины из множества назовем граничнымиили неподвижными вершинами.
Множество граничных вершин графа мы будем обозначать через . Дополнение ()∖ будем называтьмножеством внутренних или подвижных вершин графа , а сами вершины из множества ()∖ назовем внутренними или подвижнымивершинами.Пусть нам также задано некоторое конечное подмножество пространства . Будем говорить, что граф затягивает множество ,если задано некоторое сюръективное отображение : → множества граничных вершин графа на . В таком случае отображение называется граничным отображением для графа , а множество называется границей.Ребро графа назовем граничным ребром графа , если хотя быодин из его концов является граничной (неподвижной) вершиной.
Ребро графа назовем внутренним ребром графа , если оба его конца являются внутренними (подвижными) вершинами. Рангом графа назовемколичество его внутренних ребер.Аналогичные определения вводятся и для сетей. Сеть Γ[] назовемсетью с границей, если у ее параметризующего графа выделено некоторое множество граничных вершин . Совокупность вершин сети Γ,Сети в метрических пространствах31соответствующих множеству граничных (неподвижных) вершин назовеммножеством граничных или неподвижных вершин сети Γ, а вершиныиз этого множества назовем граничными или неподвижными вершинамисети Γ. Совокупность вершин сети Γ, соответствующих множеству внутренних (подвижных) вершин назовем множеством внутренних или подвижных вершин сети Γ, а вершины из этого множества назовем внутренними или подвижными вершинами сети Γ.Ребро = Γ|(,) сети Γ назовем граничным ребром сети Γ, если ребро(, ) графа является граничным ребром.
Ребро = Γ|(,) сети Γназовем внутренним ребром сети Γ, если ребро (, ) графа являетсявнутренним ребром. Ранг сети Γ по определению положим равным рангуее параметризующего графа.Обозначим через Γ ограничение отображение Γ на множество графа , т.е. Γ = Γ| . Подмножество пространства , являющеесяобразом при отображении Γ : → называется границей сети Γили граничным множеством сети Γ. Будем также говорить, что сеть Γзатягивает множество ⊂ .Наконец, сеть Γ с границей назовем регулярной, если сеть Γ неимеет вырожденных внутренних ребер. В свою очередь, сеть, котораявообще не имеет вырожденных ребер, называется невырожденной.1.3Тип сети с границей, минимальные параметрические сетиОпределение.
Пусть Γ[] — сеть с границей ⊂ . Типом сети Γназывается пара (, ), где : → граничное отображение дляграфа с множеством граничных вершин .В дальнейшем важную роль будут играть класс сетей фиксированного типа, который мы будем обозначать через [, ]. Заметим, что любаясеть Γ ∈ [, ] полностью определяется положением своих подвижныхвершин. Поэтому можно сказать, что [, ] = | ()∖| .Определение. Точку Γ абсолютного минимума (если она существует)функции длины ℓ на классе [, ] всех сетей фиксированного типа назовем минимальной параметрической сетью типа (, ).Сети в метрических пространствах1.432Операции редукции и расщепленияОпределим операцию редукции графа по ребру.Определение. Пусть — некоторый граф , а (, ) — его ребро.
Удалим ребро (, ) из множества ребер графа , а вершины и — измножества вершин графа . Теперь добавим в множество ()∖{, }новую вершину , а в множестве ребер ()∖(, ) заменим все вхождения вершин и на вершину . Обозначим получившийся граф через˜ Будем говорить, что граф ˜ получен из графа редукцией по ребру.(, ).Для операции редукции графа по ребру имеется обратная операция— расщепление вершины.Определение. Пусть — некоторый граф, а — его вершина. Обозначим через () множество ребер графа , инцидентных вершине .Разобьем множество () на два подмножества () = 1 ⊔ 2 (1 или2 могут быть пустыми). Теперь удалим из множества вершин графа вершину и добавим туда две новых вершины и . Множество ребериз графа изменим следующим образом: заменим вхождения вершины в подмножестве ребер 1 на вершину , а в подмножестве 2 — на вершину , и добавим новое ребро (, ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
