Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 5
Текст из файла (страница 5)
Далее, напомним, что каждое дерево явллстся двудольным графом. Последнее означает, что множество его вершин ьложно ракбнть на два подмножества, называемые долями, так, чтобы каждос ребро,всрсва соединяло вершины, принадлежащие разным долям. Пусть 1~ = !сь !З Ъз такое разбиение множества !' вершия локально минимального бинарноь о;!ерева Г. 'Утверждение 7 Пусть на плоскости фиксирована гексагональнал свете.на лоординит !з!'!!'. Пусть !',локально минимальное бинирное дереьо, затлгивсзюьцее,пнозкеспто з!Х, и предло яозюим, и~по килсдоь ребро дерева Г парсылсльно одной из координапьных осей.
Тогда, длл пуоизьольноео разбиения !з = !'1 Ы !'з,мнозкества в,.рьиин дерева Г на доли, имое;и: )и(Р) + 1ДР) + и~(Р)~ — ~ ~'!и(Р) + и(Р) + ю(Р)] = (!. неи1о и Реияс1И ьдгвсрхядения б и 7 показывают, что гсксагональныс координаты граничных точек множества М, затянутого фиксированным минимальныга бинарным деревом, связаны между собой линейным уравнением. Это уравненис называется харакпьсристическим. Отмсти з, что если рассмотреть дерево другой топологии, то характеристическое уравнение окажется, вообще говоря, другим, так как изменится разбиение множества вершин дерева на доли.
С помощью характеристического уравнения удается найти направления ребер минигяальноь о бинарного дерева данной топологии, затяьивающего данное множество точек (если такое дерево существует), или, что все равно, нанти гексагональную систему координат, оси которой параллельны ребрам этого минимального,дерева. 'Утвсржденио 8 Всяп систсиа гексогонольных координат !Р!о!Ло повернута относшпсльно исходной висте.ны ПЪ И' на угол ьо против часоьой ~ трслки, пьо для произао.юной то ~ки Р имеем: Лбсошотно минимальные сети 16 гс)е я. = я1п1зо) лс~/3, а 1 = соя(зр).
Воспользовавшись утверждением 8, можно записать характеристическое уравнение, которое, очсви,лно, будет линейным уравнением па й и 1. Поскольку повороты на углы:р, р+ 2 глз3 и зр+ 4к13 дают, очевидно, одинаковыс, с точностью до обозначения осей, системы координат, а таклсс поскольку имеет место соотношение 1 + 31 ' = 1, поясно, найти угол р (сс.ззз такой существует), удовлетворяющий характеристическому уравнению. Итак, имеет место следукяцее предложение.
Предложонио 3 (Кларк, Хвангз Вонг) Исходя из гексагсзззальньссл координаза точек ззнож ест го ХУХ, с гзо.зсощьзо характеристического ураонсния лкяено найти напряг.зтшл ребер нееьунзждепного млпшлально,ю дерееа Г, затлгиеаюилего ЛХ. 2.3 Абсолютно минимальные деревья, затягивающие множества специального вида Излогда, сели наложить достато шо жесткие ограничения на устройство граничного множества М, удается полностью решить задачу о поиске абсолютно минима.зьного дерева. В настоящем пункте мы расскажем о некоторых задачах такого типа. Зигзаги Рассмотрим на плоскости ломаную 1, звенья которой 'поворачивают в разные стороны" Последнее означает, что если фиксировать некоторую ориентацию ломаной 1„и каждой парс последовательных векторов-звеньев ломаной Х поставить в соотвстствис знак ориентированного узла от псрвого зззена ко второму, то получится знакоперемеппая последовательность.,!оманыс, обладающие таким свойством, называются зигзагали.
Пусть теперь М конечное множество точек плоскосзи. Множество ЛХ называется зигзагов, если существует ломаная-зигзаг 1., мнозксство вершин которой совпадает с ЛХ. В этом случае говорят, что 1, парилетразует зигзае М . Пусть ЛХ = )ЛХз)„~ нсюзторый зигзаг, параметризованный ориснь тировапной ломаной-зигзагом 1.. Предположим, что точки из М зазлумсрованы последовательно в соопзетствии с ориептапиеи 1,.
Зигзаг М называется рсгулярныл, сели существует такая его парамстризация Г, что величина угла ЛХ,Л1ььз ЛХ,лз не зависит от з,. Величина этого угла называется в этом случае суг„лсзлс зигзага М в данной параметризации. Зигзаг ЛХ называется еыпукяыи, если множество М лежит па гранино своей выпуклой оболочки. Абсолотно минимальные сети 21 — 1 Рис. 9: Абсолютно минимальная сеть, затягивающая лщзаг Зигзаг ЛсХ называется нор.нальньсм, если выполнены следующие неравенства: )ЛХ,ЛХ,тс ! < )(ЛХ„Л'Х,ез)(, 1 < с < й — 2, )ЛХ,есМ, ьг ! < ~3ЛХ„ЛХ,ьД, 2 < с < Л вЂ” '2. Непосредственно из опрсдслсний вытекает следующее несложное утверждение.
Лстверждение 9 Пусть М некоторый зигзаг. Если зигзаг ЛХ еыпуклый, то отрезок ЛХ1 ЛХь пересекает каждый отрезок ЛсХсМсяс. Ес,,си,зигзаг М нормальный, то угол МсЛХсьсЛХсьз не ментис чем кссЗ. Рассмотрим регулярный выпуклый зигзаг ЛХ, и пусть о угол зигзага ЛХ, а Х, параметризукпцая М ломаная.
Обозначим через 7; невырожденные треугольники, ограниченные ломаной Е и отрсзком М1ЯХь, см. рис 9. Построим в каждом треугольнике 7; абсолютно минимальное дерево Кс затягивающее вершины Х;, и обозна ням через Е дерево, совпадающее с объсДпненис л 1Збс ДеРевьсв Ес. Положим Яс — ! ЛХгс — 1ЛХзс ~; и Ус — ПМзс сХзс-еси. Рогда имеет место следующая теорема, доказанная Ду. Хвангом и Венгом ~16). Предложение 4 1сДус Хвангс Венгом) Если Я регу;сярный еьтуклый нормальный зигзаг с углом а (ссо осссноиссникс к некоторой фиксироьанной парамстризации1с то поспсроенное сышс дерево Я яалястся абсолиспссо ,.аинимальпым дсрсоопс заспясиаасотим М. Его длипсс пасет, ьид: б я,) + (~ у,) — 2(~ я,) (~ у,) сов1кссЗ+ н) при к,сЗ < а < 2я/3, Л.лс+2 У при 2ксс3 < а < я-.
Лбсошотно минимальные сети Иэ пРедложснин 4 вытекает, что пРи лс|3 < о < 2лс|3 абсолютно минимальное дерево, затягивающее регулярный выпуклый зигзаг с углом о, нс совпадает с минимю|ьным остоиным деревом, а при 2-сс3 < о < и уже совпадает. Точки на окружности Друтой класс | раничных множеств, для которого удается найти абсолютно миннма |ьное дерево, это точки, расположенные на окружности достаточно плотно. Оказывается, в этом случае аосолютно минимальное дерево является минимальным остовным деревом Лля своих граничных точек. Пусть ЛХ = (М,) конечное множество точек плоскости, лежащих на окружности едини"шсно радиуса.
Положим р = «73||2, и « = 1 — (1— р)гсср = О, 51399.... Тогда цмеет место слсдук|щая теорема, полученная Ду, Хван| ом и Чао [13э]. Предложение Ь (Ду| Хванг, '4ао) Если длины всех сторон ссссогоуголсс— ника М, кроме, бьппь жоэкст, одной, лсньшс, чси 7с, то абсолютно л|иии,яальиое дерево длл лноэкгства М представ,|яет, собой объединение вс ех сторон этого,.иногоугольни«а, эа искяючение.и са„иой д.|инной.
Усиление этой теоремы полу сепо в рабоче [37] Рубинштейна и '1омаса. Л именно, имеет место следующий результат, Предложение 6 (Рубинштейн, Томас) Пусть М = (Л1|) конечное жноэн:еси|ьо тече«плоскости, леэкашпх на окружносиш радиуса г. Хусли нс более одной стороны многоугольника ЛХ ижгст си|рого большую чс и г длину, то абсолюпгно линилальное дерево для жноаиества ЛХ пведстав |лет собой объединение асег сторон этого .ино оугольника, эа исключен|се„к са.иой д„пи|ной. Выпуклые многоугольники Следующий результат получен '1омасом, Рубинштейном и Колом [4!]. Авторы статьи [41] опнсывюот не«с|сор| сй класс выпуклых мно| оугольциков, для которых абсолютно минимальная сеть совпадает с множеством сторон многоугольника, за исклкэчением самой длинной.
Пусть теперь ЛХ = [ЛХе,..., ЛХ„|) последовательные вершины некоторого строго выпукло| о многоугольника. Для удобства будем вредно,и- гать, что индексы | в ЛХ; являк|тся элементами группы ств. Для любых трех последовательных точек ЛХ, |, Л1, и ЛХс.ьс обозначим через |, и О, радиус п центр окружности, описанной вокруг треугольника Л1, |МсМсъс Пусть г наименыпее из |,. '!осло г называется радиусом иаибольтс:й кривизны. Мы говорим, что точки ЛХ, |, ЛХ,, ЛХсы и Мсъз совжш тимы, если О, и О| ьс лежат с той же стороны относит прямой (Ме ЛХ|.ьс), что и все остальные точки М,.
Лбсощотно мииимьоььпые сети / / / \ / 'ь / Рис. 10: Примеры абсолютно минимальных сетей, затягиваюппьх вершины, лежащие иа квадратной решетке Предложение 7 (Томас, Рубинштейн, Кол) Пусть г радиус наибо,.ьььисй криа~ьзиьь выпуклого льиогоььгольиико ХьХ, и есс иосьсдоааттььиыг чсптсрки точек из Я1 совместимы. Если нс более одной стороны многоугольника 81 длиииее чеж ь. то абсолютио лииильальяая сеть состоит из осел сиьорои жногоуго.ььиики ЛХ, за искльочсниси сальой длинной.
Воршины квадратной решатки 3 Минимальные остовные деревья Как мы уже отмечали, задача поиска абсолютно минимального дерева явля- ется ~~'1жполььой. поэтому большое практическое значение имеет построе- ние приближенных решений. Один из саььых распространенных способов состоит в построении минимального остовиого дерева. В работах [1] [4] австралийской школы пол руководством Рубииштсйиа выполнен пикл работ, описывающих различные свойства абсолютно минимальных святей, затягивающих конечное множество йХ всршии стандартной квадратной решетки. Оти работы развивакьт результаты, полученные в [7] и [8], в первой из которых были исследованы абэсолютно мииимальиыс сети, затягивающис так казываемыс лестиипы, т.с. все вершины с координатами [т, и'1, где 1 < ьп < Л1, и = 1,2, з во второй высказшьа гипотеза о том, как устроены абсо.патио мипимальшье деревья для решетки 2ь х 2ь, т.с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
