Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 16
Текст из файла (страница 16)
при малом изменении граничного отобрахссния р, условия леммы 1.2 по-прежпему ззыполнязотся. '1тобы сформулировать соответствующий результат, введем следующее определение. Пусть ГУ произвольный граф Штсйнсра с границей дС. Введсьз на множестве всех з раничных отображений зр: дС вЂ” з Э ' метрику р следующим образом.
Если р и Зо' два таких отображения, то положим р))о, р ) = зззах,р(и)лр )и) ~. чедн Предложение 1.ос Ирсдззоложил, чизо бинарное дерево С с границей дС = д,,С ииесаи .аитхиальную реалзюацию Г для некоторого граничного отоброжения р. уогда существует такое е > О, что для .яюбзого гразтчиого отобзрззжезнзя р', рз)дГ, зр') ( =, дерево С также имеет минимальную рь— ализацию с граничным ооиображенис.я зо'.
Иньыт слооалии, .нинииольныс бззззарньзе деревья с зффетиивиыли границошии усизойчивьз при малых вариацият, границы. Более того, для любого г > 0 существуеиз изакое б > О, что дяя осст граничных отпображсний зр' дерева С, зиаких что р)ф, дГ) < 6, существуют,ииззилзалысые ретаизации Г' дерева б' с границами р', и рас.- стояние лезяду образали Г)и) и )ч)х) произвольной верилиньз и Е б' при отобралсениях Г и Г' язеньтс е. Иныли словами, лини.нальная реаяизсзция бинарного дерева С с зффекищвной границыз непрерьтно зависзззп от граничного отображения. Замечаннсз. Предложение )лз пе может быть обобщена на проьщззольные деревья!Птейнера с вершинами степени 2 в силу тсн о, что прп малом шевеленин граничного отображения угол ме кду ребрами невырождснных компонезгг, стыкующихся в некоторои вершине степени 2, может стап, меньше 120' (сели, конечно, до ."зтого он был равен 120').
)хроьзе того, требование Минимвльныс ели!и с д~~~~~~ !оно.,!огней и грвницси 6! эффективности гршпщы также сущоствснпо: малый сдвиг точек эффектввнои части грш)ицы мипнмап,ного дерева может привести к сдвигу ка!кдой вершины степени 3, что недопустимо, если в дереве имеется граничная вершина степени 3, котору!о мы хотим оставить на месте.
Напомним, что результатом прямого хода алгоритма Мелзака является пара точек. В качестве первого шага обратного хола мы строп и отрезок, сосдиня!Оьций получш!Ны!' '!Очки. )!ОГ о!резок наз!Йвается линией Си.янсона. Отметим, что, в силу произвольности выбора усов на каждом шаге прямого хода, мы, вообще говоря, мол!вы построить много разных линий Симпсона.
На свмом деле, существует естественное взаимно однозначнос соответствие мс!кду линиями Симпсона и ребрами оинарпого дерева С. Действительно, в процессе прямого хода мы перестраиваем дерево С, отрезая от него выорапные усы. На последнем шаге прямого хола от дерева С остается ровно одно ребро. которое и надо поставить в соответствие полученной линии Симпсона.
Несложно показать, что каждому ребру дерева С соответствует некоторая линия Симпсона. Полее того, имеет место следующее утверждение. 'Утверждение 1г2 Если бинарное дерево С онест „яинияальну!о реаягзаиию с граничим.н о!аображсни!.и !д, то длина .гюбой линии Силпмона ровна длине соотвс!пству!ои!ей .нинина,!ьной сети. 6 Структура минимальных сетей с данными топологией и границей В настоящем разделе мы приведем для полноты изложения результаты и:! [60~, обобщаклцие предложение 1Л па минимальные се ги с пиклами. Иными словами, мы опишем устройство минимальных сетей одной и той жс топологии и с одной и той же границей.
Для этого введем следующие понятия. Обобшеннал сеть Г: С вЂ” ! к называется линейной. сели все сс ребра отрезки прямых. Отметим, что некоторые ребра обобпюппой линейной сети могут быть вырожденными отрезками. т.е. отображениями в точку. Пусть Е(С) обозначает множество всех оообщепных линейных сетей вида Г: С вЂ” ь !Рз, !де С произвольпыи граф !!!тейнера. Ясно, что элементы пространства Е(С~ могут быть описаны поло!кениями своих вершин.
По'!!то лу, если !!С! количество вершин графа С, то Е(С) представимо в виде евклидова пространства '~' ~ !~. Элементы множества Е(С) назовем оооби!енныжи,н!нейныжи сетя.яи топологии С. Для каждой пары (С,ф, где С граф !Птейпера, а:р: дС вЂ” ь .йз нскоторос граничное отобра!кение, рассмотрим все обобщенные линсйныс сети !': С вЂ” ь '.йз, такие что с!!' = !о. Это множество обозначим через (С! Д Миннмальныс сети с данными топологией и границей бэ2 и будем называть пространство.и обобщеннььг линейных сетей топологии 6 с данной границей р. По определению, [6,;о) С С[С)).
Каждый элемент из [6, Д однозначно задается положением точек Штсйнсра, поэтому если ь количество подвижных вершин графа С', то [С', Д естественным образом наделяется структурой пространства с '. Ясно, что й ' = [6, р) является аффинныьэ подпространством в ээ ~ Д = Е[6). Пусть 6,. подграф в 6, порожденный всеми неграпичными вершинами пз 6, т.е. вершинами, не принадлеэкащими д6. Подграф 6я назовем подвижным подграфом графа [6, с)С).
Обозначим через у[6,.) цикломатическое число графа 6„, т.е. наименьшее количество ребер, которые пало выбросить из графа 6и, чтобы разрушить все циклы, и, значит, превратить граф 6, в лес. Предложение 1.6 Пусть С' проиэвольныи' граф Штсйнсра с границей д6, 1э любое граничное опэображенос, 6, подоиэкный подграф' в 6, и й = 1[6,,) цикломатичесьое число подвижного подграфа 6, . '!'огдсэ иноэкество минимальных сетей топологии 6 с границей р или пусто, или является к-,ие1энььн выпуклым открыты.а телом в некотором к-мерно.я подпространспьье конфитурационного просэпранс~ива [6, ьэ) подвилсных вершин графа С'.
Поэта„ну, сели Г,: 6 — ь "~,'з, ! = О, 1, две погрузки нных .нинимальных сети топологии С с одной и той лес границей р, то все обобщенные линейные сети Гь вида [1 — 1) !с + 1Гэ, ! Е [О, 1],. являются [поеружспнымп) минияольными сетями той эке тоттогии 6 и с той лес границеи' ьэ. В спешности, если !с[С'„) = О, т.е. подвиэкный подграф 6и графа 6 ацикличегй то существует не более одной мини вольной сети ошно 6 с границеи ьэ. Пусть 6 произвольный граф Штайнера с границей дб,п р неко- торос граничное отобраэксние.
Пусть 6 . подвижный подграф для 6. Ребро е из 6 отнесем к нулево.иу уровню, если е принадлежит нскоторо лу циклу подвижного по,п рафа 6и. Ребро е из 6, не лежащее ва пулевом уровне, но смежное с некоторым рсбром нулевого уровня, отнесем к первому уровто, а все ребра из С, не лежащие пи на пулевом, ни на первом уровнях, отнесем ко второму уровню. Предложение 1.7 Пусть !" и Г' две,ниии,иальнви сети одной и той лсе тпопологии 6 и с одной о тои' эке границы). Тогда имеют место следующие свойства: ° сеть Г параллельна сети Г'; ° длины сыпей Г и Гэ равньц произвольное ребро иэ С', леэкащее на вэпорон уэовнс, его образы при отображениях Г и Г' совпадаюпц Постановка основной задачи ° ес ш е произвольное ребро из С", лежап1ее на пгрво,я уровне, то еео образы при отображениях Г и Г' лежат на одной примой; ь сели с произьольное ребро из Х», лежащее на нулевом уровне, то его образы при отображениях !' и Г' (в соответгтвии с первььи пунктом) паХзаллельны мезюду собой.
7 Постановка основной задачи 13 настоящем параграфе мы сфорьлулируем общую задачу диссертапии. С частным случаем этой задачи мы уже сталкивались выше, где требовалось описать все минимальные сети, затягивакпцие данное конечное подмножество М точек плоскости. Однако, как был~э показано в ~21), зта задача и даже задача поиска абсолютно минимального дерева, затягивающего ЛХ, является А Р-полной, так как приходится тестировать слишком большое число топологий парамстризующих г рафов.
Ото приводит к тому, что современные компьютеры в состоянии найти абсолютно минимальное дерево )за реальное время) лишь для множеств ЛХ, состоящих из небольшого числа точек, много меныпего, чем это требуется в приложениях. Поэтому одна из вюкных задач теории минимальных сетей состоит в поиске ограничений на возможные топологии, которые вытекают из геометрии множества М. Тем самым, гттсствонно перейти от конкретного множества М к тем или иным классам множеств ЛХ, и выяснить, какие графы Штейнера имеют минимальные реализации на множествах Л1 из рассматриваемых классов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
