Геометрические свойства локально минимальных сетей (1097521), страница 42

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 42)

Рассмотрим второй случай, и пусть г1 и гз лучи ограничивающие один из характеристических клиньев точки Р и пересекающие и. Рассмотрим ребро сети инцидентное Р и параллельное гы и пусть, для определенности, это ребро еь Тогда, в силу выпуклости о, ребро еь не пересекает о (будучи ориентированным от точки Р, ребро е1 противонаправлено лучу г1 ), и, рассуждвя как и выше, можно заключить, что отличная от Р инцидентная еь вершина из Г также лежит внутри Н(Е;), Если это граничная вершина, то все доказано.

Если это точка Штейнсра, то один из ее характеристических кяиньев порожден лучами, противонаправленными лучам г1 и гз. Поэтому этот клин не Глава 4. Плоские локально минимальные деревья. 194 пересекает о в силу выпуклости последнего, и мы находимся вновь в условиях рассмотренного выше первого случая. Предложение доказано.

Следствие 4.5 Пусть à —,минимальное '2-дерево, затлгиванпцее множество Л4, и пусть А некоторый путь в Г. Предположим, что Е находится в общем положении по отношению к границам всех уровней выпуклости множества Лб. Пусть Н некоторая шапочка пунш В, и А' . некоторая верхушка шапочки Н, Тогда Н(А') О Е = 3. Доказательство. По определению, верхушка Н(ьэ) шапочки Н не может содержать точек из ЛХ.

Поэтому утверждение следствия вытекает из предложения 4.6. Следствие 4.6 Пусть Г минимальное '2-дерево, затягивающее множество ЛХ, и пусть Г некоторый путь в Г. Предлоложилц что В находигпся в общем положении по отпнотению к граничим всех дровней выпуклости множества Л4, Тогда, если Е образует две шапа ~ки Н и А", такие что Н(В') с Н(Г'), то зти шапочки имеют разные индексы. В частноспьа, если Ам...,Е,„шапочки, образованные путем То 1пакие что Н(Ь1) С ..

С Н(Ьы), и Ь1 является 1-шапочкой, то т < 1. Доказательство. Чтобы доказать первое утверждение следствия, мы предположим противное, а именно, пусть индексы Ь' и Ео равны между собой. Пусть А' некоторая верхушка А'. Тогда, в силу предложения 4.4, существует такая верхушка Ао, что Нф) С Н(Ао), и, в частности, Х' С Н(Ао). Последнее противоречит следствию 4.5. Второе у.тверждение следствия немедленно вытекает из первого. Действительно, индекс шапочки Е1 не больше чем 1, индексы шапочек Е, убывают, поэтому индекс последней шапочки . 1ы, не больше чем 1пс1 Ь1 — (т — 1), и, в итоге, 1пдТ. < пн(В1 — (т, — 1) < 1 — т+ 1. Осталось заметить, что индекс любой шапочки строго больше 1, по- этому 1 < 1 — т + 1.

Доказательство закончено. 4.2. Бинарные деревья. 195 4.2.3 Алгоритм Мелзака В данном разделе мы обсудим хорошо известный алгоритм Мелзака [64], позволяющий строить плоские локально минимальные 2-дсревья данной топологии с данной границей. Более формально, пусть С произвольное топологическое бинарное дерево, ЛХц некоторое подмножество вершин из С, содержащее все его вершины степени 1, и пусть Д: ЛХц — у Л1з . — произвольное граничное отображение,,д(ЛХп) = ЛХ. Алгоритм Мелзака позволяет ответить на следующий вопрос; существует ли погруженная локально минимальная сеть Г: С вЂ” ~ Лаз с границей о, или, как говорят, существуе~ ли у С минимален я реализация с границей ХХ.

Замечание. На самом деле алгоритм Мелзака работает и для произвольных деревьев 1Птейнера, не обязательно невырожденных, Для этого достаточно разбить произвольное дерево Штейнера в объединение бинарных деревьев невыролсденныя но,мпонент, и, если для каждой невырожденной компоненты существует бинарное минимальное дерево с соответствующей границей, то проверить под какими углами стыкуются невырожденные компоненты в вершинах степени два. Напомним алгоритм Мелзака. Прежде всего, можно предполагать без ограничения общности, что ЛХп совпадает со множеством всех вершин степени 1 бинарного дерева С. Действительно,как известно ~35, 551, если 2-дерево С имеет минимальную реализацию с границей Д, то эта реализация единственна.

Поэтому, если какис-то вершины степени 3 попали во множсство ЛХо, то следует сначала рассмотреть ограничение Д1 граничного отображения ф на множество всех вершин степени 1 бинарного дерева С, проверить, существует ли минимальная реализация Г1 дерева С с границей Х)ы и если да, то проверить, совпадает ли ограничение отображения Г1 на ЛХп с заданным отображением Д. Итак, мы предполагаем, что ЛХо совпадает с множеством всех вершин из С степени 1.

Если С имеет ровно одно ребро, то, очевидно, минимальная реализация существует тогда и только тогда, когда образы граничных вершин этого дерева различны (напомним, что мы ищем погруженную минимальную сеть). Пусть теперь С состоит более чем из одного ребра. Определение. Два смежных ребра произвольного 2-дсрсва С обра- зуют усы, если каждое из них инцидентно вершине степени 1. Глава 4. Плоские локально минимальные деревья.

196 Лемма 4.7 Если 2-дерево С состоит из трех ребер, то каждая пара его ребер образует усы. Если же С имеет более трех ребер, то оно содержит, ао крайней мере, двое непересенаюшиз,ся усов. Доказательство. Первое утверждение леммы 4.7 очевидно. Доказательство второго утверждения проведем по индукции. Отметим сначала, что количество ребер в произвольном 2-дереве нечстно.

Предположим, что для всех 2-деревьев с числом ребер, меньшим 2п + 1 и большим 3, утверждение имеет место. Расслштрим произвольное дерево С, состоящее из 2п + 1 ребер. Пусть е .- произвольное ребро из С, не инцидентное вершинам степени 1. Разрезав С по ребру е, мы получим два 2-дерева, С' и С", каждое из которых состоиг более чем из одного ребра. По предположению индукции и по первому утверждению настоящей леммы, каждое из С' и Со имеет усы, не содержащие ребра е.

Доказательство закончено. Итак, по лемме 4.7, дерево С имеет некоторые усы (е., е'). Пусть о и и' - . вершины степени 1, инцидентные ребрам е и е' соответственно, а в вершина степени 3, инцидентная одновременно ребрам е и е'. Обозначим через ео третье ребро, инцидснтнос вершине в,а через и отличнуиь от в вершину,инцидентную ребру е". Если образы А = Д(и) и А' = р(и') вершин с и и' при отображении )з совпадают, то минимальной реализации не существует. В противном случае. построим правильный треугольник АА'В одним из двух возможных способов. Перестроим дерево С в дерево С', отрезав от С усы. Определи граничное отображение У на множестве Мп всех вершин из С' степени 1, положив его равным ф везде. кроме в, и определив ))'(в) равным В. Следующая лемма вытекает из элементарных планиметрических построений. Лемма 4.8 Если 2-дерево С имеет минимальную реализацию Г с границей д, то для одного из двух правильных треугольников АА'В дерево С' имеет, минимальную реализацию Г' с границей Д'.

Миним льные сета Г и Г' совпадаю1п на С' 1 е". При зевом, луч с вер1ииной В в направлении точки Г'(ео) = Г(и) содержится внутри угла АВА' и содержит таочку Г(в), которая, в свою очередь, лежит на окружности У, описанной вокруг треугольника АВА'. В частности, точка Г'(ш) =- Г(и~) лежит вне круга, ограниченного онруьюностью У. Обратно, если сушествует миним льная реализация Г' дерева С' с границей Д', и выполняются следуюшие условия: ° луч с вершиной В в направлении точки Г'(ю) содержится внутри угла .4ВА', и 4.2. Бинарные деревья. 197 ° точка Г'(ю) лежит вне круга, ограниченного окружностью У, которая описана вокруг правильного треугольника, АВ.4', то существует .минимальная реализация Г дерева С с границей д, коспорая получается из Г' так. Обозначи,м через С точку пересечения интервала (Г'(в), Г'(ю)) с окружностью Вс.

На всех ребрах иэ С, отличных от е, е' и е", оспобрслжение Г определим равным онсображению Г'. На ребрах е, е' и ео определим его так, чтобы эти ребра переходили соответственно в опсрезки ~С,А), ~С,А') и )С,Гссю)) соответственно. Нри этом, конечно же, Г(в) = С. я=. я Рис. 4.7: Иллюстрация идеи алгоритма ГИелзака. Итсрируя описанный только что процесс перестройки дерева С и граничного отображения Д в дерево С' и граничное отображение,У до тех пор, пока в результирующем дереве останется ровно одно ребро, мы реализуем прямой ход алгоритма Мелэака. Иаждвя итерация называется шагом прямого хода алгоритма Мелзака.

Ясно, что если прямой ход состоит из и шагов, то существует 2" реализаций прямого хода, в зависимости от выбора правильного треугольника АВ.4' на каждолс шаге. Для завершения алгоритма Мелзака, необходимо выполнить так называемый обрапснььй ход. На первом шаге обратного хода мы проверяем, не совпали ли образы граничных вершин результирующего дерева, состоящего из одного ребра. Если нет, то строим минимальную реализацию этого дерева, отображая единственное его ребро в отрезок, соединяющий образы граничных вершин при результирующем граничном отображении. После этого, начинаем последовательно строить минимальныс реализации деревьев, полученных на прямом ходе.

Соответствующие построения мьс уже описали в яемме 4.8. Если на одном из шагов обратного хода нарушаются условия леммы 4.8, то переходим к испытанию следующей из 2" реаяизаций прямого хода. Таким образом, или при проверке очередной реализации прямого хода Глава 4.

Характеристики

Список файлов диссертации