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