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