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