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

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

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

Если С произвольное дерево. т.е. связный граф без циклов, то плоским линейным деревом типа С или топологии С мы будем называть такое вложение графа С в плоскость, что образ каждого ребра из С представляет собой прямолинеиный отрезок. На языке теории графов. плоское линейное дерево Г типа С это эквивалентный С плоский граф, все ребра которого прямолинейные отрезки. Иногда Г называют плоской линейной укладкой дерева С. Казалось бы, вопрос о плоских линейных укладках произвольных графов (а не только деревьев) давно и хорошо изучен: имеются критерии существования вложения в плоскость произвольного графа, например, теорема Понтрягина — Куратовского, и, более того, известна теорема Вагнера: если граф допускает некоторое вложение в плоскость, то он допускает и линейную плоскую укладку, см., например, ~25).

Наконец, наидсны алгоритмы, проверяющие существует ли у данного графа плоская укладка, и строящие соответствующий плоский граф, если ответ положителен. Однако совсем иначе обстоит дело, если мы потребуем, чтобы искомая плоская линейная укладка графа С обладала какими-либо дополнительными геометрическими свойствами, например удовлетворяла условиям какой-нибудь теоремы о локальной стру.ктуре минимальной сети из главы 3. Сформулируем общую задачу, которая возникает при таком подходе.

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

Пусть С произвольный граф, степени вершин которого не превосходят трех. Пусть фиксировано граничное отображение д: 1х — э ЛХ, и предположим, что 1х содержит все вершины из С степени 1 и '2. Задача о поиске плоской линейной сети Г типа С, затягивающей множество ЛХ Глава 4. Плоские локально минимальные деревья.

238 по граничному отображению,д, и такои что угол между любыми двумя соседними ребрами сети Г больше или равен 120', - это, в точности, задача поиска локально минимальной сети данного типа С с данной границей )1: Р— > ЛХ. В случае, если С дерево, то для каждого граничного отображения д ответ можно получить, как мы уже видели в предыдущем разделе., с помощью алгоритма Хванга-Мелзака 135, 64). Техника, которая будет развита в данном разделе, позволит нам доказать ряд результатов о геометрии плоских линейных деревьев, которые, в частности, дают возможность получать ограничения на возможные топологии деревьев С, допускающих линейные укладки с ограничениями на углы, см.

ниже. В качестве следствий, как мы уже говорили, мы получим эффективные ограничения на возможные топологии плоских линейных деревьев, являквщихсл локально минимальными в смысле длины или взвешенной длины. 1(роме того, на наш взгляд, доказанная нами общая теорема о плоских линейных деревьях имеет и самостоятельный интерес. 4.4.1 'Число вращения плоского линейного дерева Определим понятие числа вращения произвольного линейного дерева Г. Пусть а и 6 произвольные ребра из Г. Рассмотрим единственный ориентированный путь у(а, 6) в Г, начиналощийся на а и заканчивающийся на 6. Путь ~(а, 6), очевидно, представляет собой ориентированную ломаную на плоскости, Числом вращения между ребрами а и Ь линейногв дерева Г назовем кручение ломаной у(а, Ь): 1н(а,Ь) = 1п у(а, Ь). Отметим, что так определенное число вращения ориентированной пары ребер обладает следующими свойствами: ° 1~ч(а, 6) = — 1н(6, .а) (косая симметрия); ° 1ж (а, Ь) + 1ли(6, с) = 1и (а, с) длл любых ребер и, 6 и с из Г, лежащих на одном пу.ти в Г 1аддитивность вдоль путей); ° 1ъ(а, а) = О.

Определение. вйислвм вращения линейного дереве Г называется максимум чисел вращения по всем уеюрядоченным парам 1а, 6) ребер из Г: 1ьвГ = шах 1ж(а, Ь). (ал1 Замечание. Выше, при изучении геометрии локально минимальных бинарных деревьев, см.выше, а также 142, 43, 38], (а также при изучении минимальных взвешенных бинарных деревьев, см. )39), а также 4.4. Линейные деревья.

239 ниже) мы определяли число вращения для произвольного плоского бинарного дерева. При этом, определенное в разделе 4.2 число вращения бинарного дерева было планарным инвариантом, т.е, было одинаковым для планарно эквивалентных бинарных деревьев. Такое определение, на самом деле, было возможно, поскольку мы знали локальное устройство изучаемых локально минимальных сетей, а именно, знали величины углов, под которыми могут стыковаться их ребра. В рамках же рассматриваемой нами более общей задачи, ограничения на углы люгут быть заданы в виде неравенств.

Ясно, что, исходя из таких ограничений, нельзя адекватно определить число вращения между. парой ребер дерева. (В качестве примера, можно рассмотреть задачу о минимальных взвешенных деревьях, у которых имеются вершины степени больше чем три.) Тем не менее, для каждого конкретного линейного дерева число вращения определлется естественным образом, что и сделано выше, и можно изучать, как изменяется число вращения внутри некоторого класса таких деревьев.

Отметим, что для минимальных, а также взвешенных минимальных бинарных деревьев, определенное нами число вращения совпадает с числом вращения таких деревьев в смысле раздела 4.2 и 4.3 и работ [42, 43, 38, 391. 4.4.2 Геометрическая граница линейного дерева Определим теперь понятие геометрической границы линейного дерева. Пусть à — — линейное дерево, и Р --. произвольная вершина из Г. Каждая прямая Е', проходящая через Р. определяет пару полуплоскостей, которые мы будем называть полуплосносьплми, порожденнььми е.

Определение. Вершину Р линейного дерева Г назовем граничной, если существует проходящая через Р прямая с, такая что одна из открытых полуплоскостей, порожденных е, содержит все ребра из Г, инцидентные Р. Все остальные вершины из Г будем называть внутренними, Множество всех граничных вершин дерева Г назовем геометрической границей дерева Г и обозначим через длГ.

Замечание. Ниже, там где это не вызовет недоразумений, мы, для краткости, будем называть геометрическую границу линейного дерева просто границей, опуская слово "геометрическая". Теперь все готово для того, чтобы сформулировать основную теорельу настоящего раздела. Глава 4. Плоские локально минимальные деревья. 240 Теорема 6 Пусть Г -- произвольное линейное дерево, и М = двГ -- его геометрическая граница, Обознач м через гс(М) количество уровней выпуклости .множества двГ.

Тогда 1кГ < 12(м(ЛХ) — 1) + 6. Более того, зта оценка является точной в следующем смысле, Для каждого целого )с > 1 существует плоское линейное дерево Г, такое что си Г = 12(к — Ц + 6, и гс(двГ) = )с. Доказательство этой теоремы мы разобьем на несколько шагов.

4.4.3 Правильные линейные деревья В качестве первого шага, мы покажелц что достаточно доказать теорему 6 для специального класса так называемых правильных линейных деревьев. Внутренние вершины произвольноголинейного дерева Г могут быть следующих трех типов. Внутренняя вершина Р из Г называется устойчивой, если для любой прялвой 6, проходящей через Р., каждая из открытых полуплоскостей, порожденных 6, содержит ребра из Г, инцидентные Р.

Внутренняя вершина степени два называется фиктивной, а внутренняя вершина степени больше чем два и не являющаяся устойчивой называется неустойчивой, см. рис. 4.13. Рис. 4.13: Типы внутренних вершин. Пусть Г произвольное линейное дерево. Рассмотрим произвольную фиктивную вершину Г из Г (если такая есть) и заменим пару ребер е1 и с|,. из Г, инцидснтных 1', на одно 'длиннооь ребро, явллющееся объединением отрезков ек и е';.

Ясно, что так перестроенная сеть снова является линейным деревом, которое совпадает с Г как подмножество плоскости, однако содержит на одну фиктивную вершину меньше. Будем повторять описанную процедуру до тех пор, пока 4.4. Линейныс деревья. 241 не построим линейное дерево Г', совпадающее с Г как подмножество плоскости, но уже не имеющее фиктивных вершин.

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

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