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

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

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

Будем говорить, что линейное дерево Г' получено укрупнением дерева Г. Дерево Г' совпадает с Г, как подмножество плоскости, поэтому, в частности, си Г = си Г'. 1(роме того, по определению, совпадают и границы этих деревьев. Таким образом., следу ющее соглашение не ограничивает общности: Всюду ниже будем рассматривагпь лишь линейные деревья, не содержащие фиктивных вершин. Далее, оказывается, произвольное линеинос дерево Г сколь угодно малой деформацией, неподвижной на границе дерева Г. можно превратить в линейное дерево без неустоичивых внутренних вершин, переведя все неустойчивые внутренние вершины в устойчивые. Предложение 4.17 Пусть Г произвольное линейное дерево.

Тогда, для любого е > 0 существует линейное дерево Г„без неустойчивых внутпренних вершин, такое что, ~ уиà — сиГ„~ ( е, а множества ддГ и ддГс совпадают. Доказательство. Мы построим деформацию дерева Г, изменяющую положение только его неустойчивых внутренних вершин. Пусть 1г произвольная внутренняя неустойчивая вершина из Г. Тогда, по определению. существует ровно два инцидентных ей реора из Г, угол между которыми равен н. Эти ребра назовем опорными ребрами вершины И. Замкнутую полуплоскостьь ограниченную прямой, проходящей через опорные ребра вершины 1'. и содержащую все ребра из Г, инцидентные 1", назовем опорной полуплоскостью вершины И, Так как, напомним, мы предполагаем, что Г не содержит фиктивных вершин, опорная полуплоскость однозначно определена для произвольной внутренней неустойчивой вершины. Рассмотрим подграф Т' дерева Г, порожденный множеством всех неустойчивых внутренних вершин нз Г, т.е.

подграф, множество вершин которого совпадает с множеством всех неустойчивых внутренних вершин дерева Г, а множество ребер состоит из тех и только тех ребер из Г, которые соединяют неустойчивые внутренние вершины. Так как мы строим деформацию, неподвижную на всех вершинах, кроме неустойчивых внутренних, то достаточно научиться строить эту деформацию для каждой связной компоненты графа Т'. Иными словами, без ограничения общности будем предполагать, что Т' связен, т.е.

является деревом. Предположим сначала, что граф Т' состоит из одной вершины И, Это означает, что все вершины из Г, смежные с 1', нс являются неустойчивыми внутренними вершинами. Построим деформацию дерева Глава 4. Плоские локально минимальные деревья. 242 Г, неподвижную на всех вершинах из Г, отличных от Р, и смещающую вершину Г внутрь ее опорной полуплоскости.

Ясно, что при любых достаточно малых смещениях эта деформация превращает всршину 1' в устойчивую внутреннюю вершину дерева Г и не меняет типы всех остальных вершин из Г. Пусть теперь граф Т' содержит по крайней мере две вершины. Добавим к графу Т' все опорные ребра входящих в Т' вершин, Полученное дерево обозначим через Т.

Отмстим, что линеиное дерево Т может, вообще говорл, содержать фиктивные вершины, причем любая его вершина степени 2 является фиктивной. Обозначим через Т укрупнение дерева Т. В силу сказанного выше, граф Т не имеет вершин степени 2, а все ого воршины степени 1 не принадлежат Т'. Для доказательства предложения достаточно, очевидно, построить малую деформации> дерева Г, неподвижную на границе дяГ, переводящую несколько неустойчивых вну.тренних вершин в устойчивые внутренние вершины, и не меняющую тип остальных вершин дерева Г. Дсйствительно, если такая деформация построена, то доказатсльство завершается индукцией по числу внутренних неустойчивых вершин.

Пусть 1х некоторая вершина дерева Т' степени 1.,Ясно, что по определению дерева Т, .существует или одно, или два ребра из Т, инцидентных Р и не входящих в Т', Если таких ребра два, то 1' является вершиной графа Т и имеет в нем степень 3. Ероме того, среди вершин из Г, смежных с 1', ровно одна вершина являстся неустойчивой внутренней вершиной, причем эта вершина принадлежит Т'. Построим деформацию дерева Г, смещающую вершину Ъ' внутрь единственного инцидентного 1г неопорного ребра из Т и оставляющую неподвижными все остальные вершины из Г. Ясно, что при любых достаточно малых смещениях эта деформация превращает вершину 1' в устойчивую внутреннюю вершину дерева Г и не меняет типы всех остальных вершин из Г. Таким образом, если хотя бы одна из вершин дерева Т' степени 1 инцидентна двум не входящим в Т' ребрам дерева Т, то искомая деФормация дерева Г построена. Рассмотрим теперь оставшуюся возлюжностьс пусть для каждой вершины 1' из Т' степени 1 существует ровно одно ребро из Т, инцидентное Г и не входящее в Т'.

В этом случае, очевидно, каждая такая вершина 1" является фиктивной вершиной графа Т, и поэтому лежит внутри некоторого ребра ек графа Т. Отметим, что ребро е~ составлено из опорных робер тех вершин дерсва Г, которые лежат внутри е~ . Обозначим через Ак и А', вершины ребра еп в Т, при этом предположим, что Аг и 1'.

смежны в Т. Вершина.4к, очевидно, имеет в дереве Т степень 1. Для вершины А', это, вообще говоря, неверно. Мы начнем с того, что выберем среди вершин Ъ' подходящую для наших 4.4. Линейныс деревья. 243 целей вершину, которую будем обозначать через е'. Кроме того, мы определим отрезок Е, который будет содержать ребро еи.

После этой подготовительнои работы, мы построим искомую деформацию дерева Г. Пусть сначала степень вершины А~~с равна единице. Тогда, в силу связности дерева Т, это дерево состоит из одного ребра еч . Положим 1'=К,иЕ=еч. Пусть теперь дерево Т состоит больше чем из одного ребра. Нам понадобится счедующая лемма.

Лемма 4.16 Пусть Ф дерево, сосншяо>ее более чем из одного ребра и не имеющее вершин степени два. Тогда в Ф или существуепь вершина,. смежная с не менее ием тремя вершинами степени 1, или существует вершина степени 3, смежн я с двумя вершинами с~иепени 1. Доказательство. Отрежем от Ф все ребра, инцидентные вершинам степени 1.

По предположению, полученный в результате граф Ф' не пуст и яачяется деревом, Если Ф' состоит из одной вершины, то Ф звезда, количество ребер которой больше двух, поэтому единственная вершина из Ф степени больше 1 удовлетворяет условию леммы. Если же Ф содержит ребра, то условиям .чеммы у.довлетворяет лкчбая вершина из Ф, которой соответствует вершина степени 1 в Ф'. Лемма доказана. В силу ваших предположений. дерево Т удовлетворяет условиям леммы 4.16. Если в Т имеется вершина А', смежная с тремя или более вершинами степени 1, то среди этих вершин степени 1 имеется, очевидно.

по крайней мере одна вершина А, такая что ребро АХ не является опорным для вершины А'. В этом случае мы положим Е = АХ, и в качестве К выберем соответствующую вершину из Т', смежную с А в Т. В противном случае, в Т имеется вершина Х степени 3, смежная двум вершинам степени 1. Здесь имеется две возможности: или одно или оба соответствующих граничных ребра являются опорными для А', Если такое ребро одно, то обозначим через А граничную вершину инцидентную другому граничному ребру. Тогда снова ребро АХ не является опорным для Х, и как и выше, мы положим Е = АХ и 1' вершина из Т', смежная с А.

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

244 Перейдем теперь к построению деформации. Ясно, что построенный нами отрезок Е составлен из опорных ребер тех вершин дерева Г, которые лежат внутри Е. При этом все эти вершины являются фиктивными вершинами дерева Т, кроме, быть л>ожет, одной вершины степени 3 (если отрезок Е состоит из двух ребер дерева Т, являющими опорными). Обозначим через 1' = 1 >,..., И, последовательные вершины дерева Т, лежащие внутри отрезка Е, и пусть 1'>,...,1'„максимальный начальный отрезок этой последовательности, такой что опорные полуплоскости вершин 1;. для 1 < 1 < р совпадают.

Обозначим через В вершину дерева Т, смежную с 1;, отличную от 1' Построим ломаную Ь = (А = Ие, И'>,, .., Ию Ир.>.> = В), такую что 1. ломаная Л лежит в обшей опорной полуплоскости вершин 1',;, 1 < 1<р; '2. ломаная Ь, вместе с отрезком АВ, ограничивает строго выпукяый многоугольник; 3. расстояние между точками 1; и И'; не превосходит щ 4.

если 1> является вершиной графа Т, то выберем точку И', на единственном неопорном для 1', ребре из Г, инцидентном 1; (такое ребро., очевидно., существует и единственно.,так как степень 1;. в Т равна 3). Построим деформации> линейного дерева Г, постоянную на всех вершинах, за исключением 1>>,...,. 1ю и переводящую каждую вершину 1; в соответствуюшую вершину И'и г = 1,...,р. Ясно, что при достаточно малом я, эта деформапня превращает всршины 1',, 1 = 1,..., р, в устойчивые внутренние вершины дерева Г, и не меняет тип других вершин из Г, отличных от В.

Для вершины В существует три возможности: 1. или р < и. т.е. вершина В = 1р+> является вершиной дерева Т, лежащей внутри отрезка Е, в частности, В --. неустойчивая внутренняя вершина из Г, опорная полу плоскость которой не совпадает с опорной полуплоскостью вершины 1'р, 2. или р = ц н степень вершины В в дереве Т равна 1 (в этом сяучае В не является неустойчивой внутренней вершиной из Г); 3. или р = и и степень вершины В в дереве Т больше 1 (при этом, очевидно, вершина В неустойчивая внутренняя вершина из Г, 4.4.

Линейные деревья. 245 а единственное инцидентное В ребро дерева Г, содержащееся в Е, по построению не яьтяется опорным для В). В первом случае внутренняя неустойчивая вершина В становится внутренней устойчивой вершиной. Во втором и в третьем случаях тип вершины В не меняется. Таким образом, искомая деформация дерева Г построена. Итак, нами построена сколь угодно малая неподвижная на границе деформация линейного дерева Г, превращающая некоторое количество неустойчивых внутренних вершин дерева Г в устойчивые внутренние вершины и не меняющая типы лругих вершин из Г.

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

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