Геометрические свойства локально минимальных сетей (1097521), страница 43
Текст из файла (страница 43)
Плоские локально минимальные деревья. 198 обратный ход алгоритма Мелзака приведет к построению искомой минимальной реализации, или будут проверены все 2в вариантов и < делан вывод о том, что данное дерево С не имоет минигаальной реализации с граничным отображением 3. Нак мы уже отмечали, к успешному завершению прямого хода алгоритма Мелзака может привести не более одной реааизапии пряъюго хода. Алгоритм Мелзака. не умея отсеивать 'неперспективные" последовательности, тратит много времени на работу. с ними. Однако.
оказывается, можно заранее понять, как устроена та единственная последовательность треугольников АВА', которая может привести к успешному завершению алгоритма Мелзака. Эту задачу решает алгоритм, предложенный Хвангом в [35). 4.2.4 Алгоритм Хванга Изложеннал здесь конструкция предложена Хвангом, см. ~35).
Пусть С 2-дерево с границси,д; ЛХп — ~ ЛХ с Кз, заданнои на множестве ЛХо всех вершин из С степени 1. Начнем с рассмотрения случаев,когда дерево С содержит мало ребер. Если С состоит ровно из одного ребра, то все очевидно, так как треугольники АВА' строить не надо. Если С имеет три ребра, т.е. ЛХп состоит из трех вершин, то имеются следующие возможности; или все точки из ЛХ = ДЛХо) лежат на одной прямой (тогда, очевидно, минимальнои реквизиции не существует), или точки из ЛХ образуют невырожденный треугольник.
В последнем случае один из двух треугольников АВА' из прямого хода аягоритма Мелэака пересекается с внутренностью выпуклой оболочки сопя ЛХ множества ЛХ, а друтой нет. Легко видеть, что тот АВА', который пересекает внутренность сонг ЛХ, никогда не приводит к положительному результату, т.е. к минимальной сети. Поэтому в этом случае однозначно определено "правильное" расположение треугольников АВА'. Пусть теперь С состоит из пяти ребер,т.е. множество ЛХо содержит четыре вершины. Обозначим через (е,е') и (Х,Х') имеющиеся две пары усов. Пусть Е, Е', Е и Е' —,В-образы граничных вершин, инцидентных соответственно е, е', Х и Х'. Очевидно, если какие-либо из этих четырех точек совпадают, то искомую минимальную сеть построить нельзя.
Пусть тепсрь вес эти точки различны. Обозначим через Х, и ХХ прямые, проходящие соответственно через Е, Е', и Е, Е'. Из элементарных планиметрических соображений вытекает, что если дерево С имеет минимальную реализацию с границей Д. то точки Е и Е' должны лежать в одной открытой полуплоскости относительно 4.2. Бинарные деревья. прямой су, а также точки Е и Е' должны лежать в одной открытой полуплоскости относительно прямой !ь Более того, есщи вершина В треугольника ЕВЕ', который строится на вершинах Е и Е'., лежит в той же полуплоскости относительно с'„что и точки Е и г", то это не приводит к минимальной реализации дерева С. Аналогичные рассуждения имеют место и для треугочьника ЕСЕ' на вершинах Е и Е'.
Таким образом, и в этом случае однозначно определено правильное расположение треугольников ЕВЕ' и ЕСг". Предположил1 теперь, что дерево С состоит более чем из 5 ребер, т.е. его граница состоит более чем из четырех вершин. Напомним, что по лемме 4.7, в дереве С имеется, по крайней мере, двое непересекающихся усов. Нам будут полезны следующие опредсяения. Пусть (е,е') и (!,зо) пара непересекающихся усов в дереве С.
Обозначим через в, и ву общие вершины соответственно для первых и длл вторых усов. Х!ы скажем, что эти двое усов смежны, если существует вершина в, смежная одновременно с в„и ву. Далее, пусть (е, е') усы, и в, вершина, общая для ребер из этих усов. Пусть ! ребро, соединяющее некоторую вершину степени 1 с некоторой вершиной ву. Мы скажем, что усы (е,е') и ребро 7" смежны, если вершины в, и ву соединены ребром. Имеет место следующее утверждение.
Лемма 4.9 Пусгпь С произвольное 2-дерево, содержащее более 5 ребер. Тогда в С или существует пара смежныт, усов, или имеются усы, смежные ребру, иниидентному вершине степени 1, Доказательство. Отрежем от дерева С все усы. Так как С имеет более четырех граничных вершин, то полученное 2-дерево С' будет., очевидно, содержать более одного ребра. По лемме 4.7, 2-дерево С' обладает некоторыми усами, скажем (е, е'). Однако эти усы не могут быть усами дерева С, иначе они должны были быть отрезанными. Поэтому к усам (е, е') крепятся или одни усы дерева С, или двое усов из С.
В первом случае мы получаем усы, смежные с граничным ребром, а во втором случае пару смежных усов. Доказатеаьство закончено. Итак, рассмотрим два случая. Пусть сначаяа в дереве С существует пара съвсжных усов (е,е') и (7", !'). Обозначим через Е', Е', Е и Е' В-образы граничных вершин из С, инцидентных е, е', ! и !' соответственно. Пусть |ь и су прямые, проходящие соответственно через Е,Е'иЕ,Е', Лемма 4.10 Если существует минимальная реализаиия дерева С, то или тонки Е и Е' лежат в одной открытой полуплоскости относительно прямой с7, или тонки Р и г" лежат в одной открытой полуплоскости относительно прлмой с,.
Глава 4. Плоские локально минимальные деревья. 200 я б е 5 и . е 5 [е Е' и ,!' Рис. 4.8; Алгоритм Хванга. Доказательство. Действитеяьно, утверждение леммы равносильно тому, что отрезки [Е,Е'1 и [Е,К'[ не псресекаются. Последнее очевидно из элементарных планиметричсских соображений, см, рис, 4.8. Следующая лемма также элементарна. Перейдем теперь ко второму случаю, а именно, когда в дерево С имеются некоторые усы [е,е'), смежные с некоторым ребром у, инцидентным вершине степени 1. Обозначим через Е, Е' и Е соответственно д-образы граничных вершин, инцидентных ребрам е, е' и з'.
Обозначим через К, прямую, проходящую через Е и Е'. Легко видеть, что имеет моста следующий результат. Лемма 4.12 Если существует минимальнал реализация дерева С, то точка Е не лежит на прямой 1,. Более того, при правильном выборе треугольника АВА', построенного на точках Е и Е', вершина В и тачки Е должны лежать в разных открытых полуплоскостях относительно прямой с, Итак, правильный выбор треугольников АВА' на ьтом шаге прямого хода алгоритма Мслзака в случае, когда текущее дерево С,, состоит более чем из 5 ребер, заключаетсл в следующем. Если имеются усы [е, е'), смежные с граничным ребром З", то сначала проверяем, различны ли В-образы граничных вершин, инцидентных е, е' и у (если нет, то эта реализация прямого хода плохая) и нс Лемма 4.11 Пусть хлопки Е и Е' лежагп в одной открытой полуплоскоспи относительно прямой су.
Тогда если вершина В треугольника АВА', построенного на точках Е и Е', лежит, в той же полуплоскости, что и точки Е и Е', то зта реализация прямого хода алгоритма Мелзака не приводит к построению минимальной сети. 4.2. Бинарные деревья. 201 лежит ли )3-образ Е граничной вершины, инцидентной (, на прямой Р„, проведенной через д-образы граничных вершин, инцидентных усам (е, с'). Если лежит., то эта роализация прямого хода плохая. Иначе располагаем вершину В так, чтобы она была отделена прямой с, от Е. Если не существует усов, смежных с граничным ребром, то обязана существовать пара смежных усов, скажем (е,е') и (Д, Г').
Если Е, Е'., Е, Е' -- образы граничных вершин ребер е, е', з", у"' соответственно, то проверяем, различны ли точки Е, Е', Е и Р" (если нет, то эта реализация прямого хода плохая) и не пересекаются ли отрезки (Е, Е'1 и (г, Р'). Если пересекаются, то эта реализация прямого хода плохая. Иначе выбираем ту пару точек из (Е, Е') и (Е, г"), которая лежит в одной открытой полуплоскости относительно прямой, проведенной через другую из пар этих точек.
Пусть, например, точки Е и Е' лежат с одной стороны относительно прямой су, проведенной через Е и Е'. Построим треугольник АВА' на вершинах Е и Е' так, чтобы его вершина В была отделена прямой Ку от точек Е и Е'. 4.2.5 Следствия из алгоритмов Мелзака и Хванга Итак, мы выяснили, что, исходя из геометрии множества ЛХ =,3(ЛХо) и топологии дерева С можно однозначно определить правильный выбор треугольника АВА' на каждом шаге прямого хода алгоритма Мелзака.
В дальнсишем, говоря об алгоритме Мелзака, мы всегда будем предполагать, что все треугольники АВА' выбираютсл именно так. Конечно, мы не гарантированы, что в результате обратного хода будет построена минимальная реализация дерева С, так как ее, вообще говоря, может и не существовать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
