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

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

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

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

Отметим, что при таком определении усы могут состоять из одного граничного ребра. Предложение 5.12 Каждое дерево С, количество веригин которого больше единицы, имеет усы. Если это дерево содержит неграничное ребро, то имеется двое непересекающихся усов. Глава 5. Сети с фиксированными типом и границей. 310 Доказательство. Отрежем от дерева С все граничные ребра. Если у полученного дерева нет ребер, то все граничные ребра иэ С образуют усы.

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

Полученный к-прообраз будем называть усами графа С, а единственное неграничное непикличсское ребро, инцидснтное усам (если таковое имеется) ребром крепления этих усов. Из предложения 5.12 мгновенно полу. чается следующий результат. Следствие 5.8 Пусть Г: С вЂ” > Км взвешенная локально минимальная сеть, совпадаю1цая со своей невырожденной компонентой. Тогда граф С имеет некоторые усы.

Если граф' С содержит внутреннее нениклическое ребро, то он имеет двое непересекающихся усов. Усы, содержащие циклическое ребро, будем называть ииклическ ми усами, а все остальные усы деревянными. 5.2.4 Доказательство теоремы 8 Первое утверждение теоремы вытекает из предложения 5.9. Перейдем к доказательству второго утверждения. Очевидно, что его достаточно доказать в предположении, что сеть Г совпадает со своей невырожденной компонентой.

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

Имеется две возможности: или вершина Г; п — ь йо нс является слабо фиктивной в Г, или является. Если вершина Г: о — > К нс являстсл слабо фиктивной, то по край- М ней мере двое иэ отрезков Г: е, ь К~ не колинеарны. В силу неизменности направления каждого ребра в процессе деформации Гы вершина Г; о -+ Бм и, значит, все отрезки Г; е, — ь ге~ в этом случае неподвижны. По определению, усы (еы...,еь) состоят из ребер второго 5.2. Взвешенные минимзльныс сети в Гьэ. уровня, и, как мы только что показали, для них теорема имеет место. Далее, отрежем от С усы (еы...,еь) и полученный невырожденный граф обозначим через С'.

Обозначим через Г' ограниченно деформации Г на С'. Так как вершина Г: и — ~ К~ неподвижна при деформации Г„то деформация Г', сетей топологии С' также неподвижна на границе. По предположению индукции, теорема имеет место для сетей Г',, Легко видеть, что ребра из С' относятся, по отношению к С',. к тем же уровням, что и по отношению к С. Таким образом, в этом случае теорема доказана.

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

В силу выбора точки ш все Г' -- погруженные сети, .параллельные Г~~о . Определим границу графа С', положив дС' = (дС ОС') 0 (и). Граф С' с границей дС' совпадает со своей невырожденной компонентой. Далее, положим р' = дГ'. По предположению индукции, для взвешенной минимальной сети Г' утверждение теоремы имеет место, Осталось заметить, что для всех ребер из С', кроме ребра е, разбиение на уровни по отношению к С' совпадает с разбиением на уровни по отношению к С.

Поэтому для всех этих ребер утверждение теоремы имеет место, что и завершает доказательство. Пусть теперь в С нет деревянных усов. По следствию 5.8, граф С содержит некоторые циклические усы С'. Пусть е -" ребро крепления усов С', и а Е е некоторая внутренняя точка ребра е. Ясно, что ребро е нс циклическое. Разрежем граф С по точке а. Так как е не циклическое ребро, граф С распадется на две компоненты. Обозначим через С ту нз этих двух компонент, которая содержит усы С', а через е' ребро из С, принадлежащее е. Оставшуюся компоненту.

обозначим через С. Рассмотрим ограничение Г' деформации Г~ на С . По предложению 5.11, отрезки Г',(е') лежат на одной прямои. Поэтому для ребра Глава 5. Сети с фиксированными типом и границей. е, которое, очевидно, относится к первому уровню., теорема доказана. Кроме того, мы получаем., что для 1, близких к О, можно сделать такую РспаРаметРизацию РебоР Гь .. е -+ 1аз сотен Гь котоРаЯ, во-пеРвых.

непрерывно зависит от 1, и, во-вторых, после нее то пса Г~ (а) неподвижна. Теперь применим предположение индукции к обоим компонентам С и С . Очевидно, ребра из С и С, отличные от ребер разреза, принадлежат к тем же уровням, что и в графе С. Последнее замечание доказывает, что утверждение теоремы имеет место для сетей Г„близких к Гв = Г.

Применяя описанную процедуру для каждой сети Гь, 1 Е ~О, 1], выбранной в качестве сети Г, мы получим покрытие отрезка малыми интервалами, на каждом из которых утверждение теоремы выполнено. В силу компактности отрезка, из этого покрытия можно выбрать конечное. что и завершает доказательство теоремы. Теорема 8 позволяет описать, чем взвешенные минимальные сети с одинаковыми топологиями и границами отличаются друт от друга. Следствие 5.9 Пустль Г и, Г' две взвеиеенных минимальных сети в Км одного и того же типа С и с одной и той же границей. Тогда имеют место следующие свойства; ° сеть Г параллельна сети Г'; ° взвешенные длины сетей Г и Г' равны; ° если е .

произвольное ребро из С, лежащее на втором уровне, то его образы при отображениях Г и Г' совпадают; ° если е -- произвольное ребро из С, лежащее на первом уровне, то его образы при отображениях Г и Г' лежат на одной прямой; ° если е произвольное ребро из С, лежащее на нулевом уровне, то его образы при отображениях Г и Г' параллельны между собой. 5.3 Взвешенные минимальные сети Штей- нера на плоскости Рассмотрим теперь важный частный случай плоские сети, степени вершин которых не превосходят трех. Такие сети и их параметризуюшие графы называются плоскими сетями Штейнера и графами Штейнера соответственно. Они возникают при исследовании локально минимаяьных сетей в смысле функпионала обычной (не взвешенной) 5.3.

Сети Штейнера на плоскости. 313 длины; каждая локально минимальная сеть есть сеть Штейнера. Для взвешенных минимальных сетей на плоскости удается вычислить размерность многогранника ~С, ~р) ы исходя из топологии параметризующего графа С с границей дС. Оказывается, размерность равна цикломатическому числу подвижного подграфа. Для простоты изложения мы будем предполагать, что для каждой внутренней вершины ц сети неравенство треугольника для весов инцидентных г ребер выполняется строго. Отсюда, в частности, вытекает. что минимальная сеть не может иметь слабо фиктивных вершин. В предыдущей главе мы описали обобщенный алгоритм Мелзака для построения взвешенных минимальных реализаций взвешенных плоских деревьев Штейнера и получили некоторые следствия из него. Там же было определено понятие линии Симпсона для таких деревьев.

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

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