Геометрические свойства локально минимальных сетей (1097521), страница 69
Текст из файла (страница 69)
В следующем разделе мы покажем, как можно легко вычислить длину линии Симпсона исходя только из информации о структуре погружения, задаюшего взвешенное минимальное невырожденное дерево Штейнера, его весовой функции и координатах граничных точек. Ыы начнем с того, что опишем важную характеристику погружения, а именно, оснащение вращения., индуцированное этим погружением. 5.3.1 Оснащение вращения Пусть С произвольный граф, и Г: С вЂ” > йз некоторая погруженная сеть.
Напомним, что, по определению, ребра сети — вложенные кривые, Тем не менее, минимальные взвешенные сети обладают еще одним важным свойством; у каждой вершины такой сети имеется вложенная локальная сеть (напомним, что мы продполагаем выполненными строгие неравенства треугольника для весов). Каждую сеть, обладающую этим дополнительным свойством, будем называть нормальной.
Пусть теперь Г нормальная невырожденная сеть Штейнера. Отметим, что так как Г невырождена. т.е. ее граница состоит в точности из всех вершин степени 1, то множество всех подвижных вершин сети Г --- это множество всех вершин из Г степени 2 и 3, причем каждая вершина степени 2 фиктивная. Пусть ц . произвольная подвижная вершина из Г степени 3. В силу нормальности сети Г, некоторая локальная сеть Гц с центром в ц является вложенной сетью, состоящеи из трех ребер. Пусть е и е' произвольныс два ребра из Сп.
Положим по определению число вращения Фв (е, е') упорядоченной пары (е, е') равным 1, если при обходе в положительном направлении вершины г, начиная с образа ребра е', мы сначала встретим образ ребра е, а лишь затем образ третьего ребра сети Гп. В противном случае, положим Фи(е, е') = — 1. Вели Е и Е' Глава 5. Сети с фиксированными типом и границей. 314 ребра графа С, содержащие е и е' соответственно, то числом враигения гго1Е, Е') упорядоченной пары 1Е,Е'), индуиированным сетью Г, назовем число гтл(е, е'). Пусть теперь о произвольная фиктивная вершина графа С, а Е и Е' ребра из С, инцидентные о.
Положим по определению 'ьгч(Е, Е') = О. Итак, каждая нормальная сеть Г: С вЂ” г Кз индуцирует на С оснаигение врагаенил, представляющее собой совокупность чисел вращения всех упорядоченных пар смежных ребер из С. Пусть теперь С взвешенный невырожденный граф Штейнера с весовой функцией ы, и Г некоторая нормальная сеть типа С, а о --- произвольная подвижная вершина графа С степени 3, инцидентная ребрам Е;, г = 1,..., 3. Построим треугольник со сторонами, равными весам ш(Ег), и обозначим чорез о; величину того угла этого треугольника, который противолежит стороне длины ы(Е;). Положим тх (ЕОЕ,) = тъ(ЕОЕ.), где (г,у,к1 = (1,2,31.
'1исло бж (Ег, Е ) называется взвешенным числом вращения упорядоченной пары (Е„Е ) ребер взвешенного графа С, индуцированным нормальной сетью Г. Пусть теперь о . - произвольная фиктивная вершина из С, а Е и Е' инцидентные ей ребра из С. Положим ги '1Е,Е') = О. Итак, каждая взвешенная невырожденная нормальная сеть Штейнера Г; С -+ Гсз индуцирует на С взвешенное оснащение вращения, предстаатяюшее собой совокупность взвешенных чисел вращения всех упорядоченных пар смежных ребер из С. Если С является невырожденным деревом Штейнера, то можно продолжить как оснащение вращения, так и взвешенное оснащение вращения на все упорядоченные пары ребер этого дерева по аддитивности вдоль путей.
Последнее означает следующее. Если (Е,Е') --- упорядоченная пара произвольных различных ребер из С, а у = (Ео = Е, Ег,..., Еь = Е'1 единственный путь в С, соединяющий Е с Е', то положим бж(Е,Е') = ~~г 1ъ(Е, г,Е,), и '.ъм(Е,Е') = ~~г Фи~(Ер г,Е,). р=г Если жс Е = Е', то положим ги(Е,Е') = йъ'"(Е.,Е') = О. Число гак(Е, Е') называется числом вращения уггорядоченной пары 1Е, Е') ребер дерева С, или числом враигения от ребра Е к ребру Е', порожденным сетью Г.
Соответственно, число гвг '(Е, Е') называется взвешенным числом враигенил упорядоченной пары (Е,Е') ребер взвеигеннозо 5.3. Сети Штейнера на плоскости. 315 дерева С, или взвешенным числом вращения от ребра Е к ребру Е', порожденным взвешенной сетью Г. Замечание. Отметим, что если Г .-- плоское взвешенное бинарное дерево., то определенное только что число вращения пары ребер из Г совпадает с определенным в предыдущей главе и имеет тот же геометрический смысл, т.е.
если Г локально минимально, то число вращения равно полному утлу поворота вдоль соответствующего пути в Г, деленному на к/3. Далее, в терминах чисел вращения легко выписать координаты концов линии Симпсона. Пусть С произвольное взвешенное невырожденное дерево Штейнера, и Г некоторая его взвешенная минимальная реализация с эффективной границей ВГ. Выберем в С произвольное ребро е, и пусть Е = ~Х, 1') -- соответствующая е линия Симпсона. Пусть, для начала, ребро е --- граничное, п --. единственная граничная вершина, ему инцидентная, и т = Г(о) ее образ при отображении Г. Тогда, как легко видеть, одна из концевых точек линии 5, скажем Х. совпадает с т.
Далее, пусть пь,..., пь остальные граничные вершины из С, а тр — — Г(п„). Пусть ер -- единственное граничное ребро, инцидентное ор. Обозначим через 1„взвешенное число вращения бк (е, ер). Тогда имеет место следующее предложение. Предложение 5.13 Втаорой конец У линии Силтсона Е может быть вычислен по следующей 1рормуле: где через тр обозначены также комплексные координаты точек т„. Доказательство.
Для доказательства этого предложения нам пона- добится следующая лемма. Лемма 5.6 Пусть АВС треугольник на плоскости Кэ со сторонамиа= ~ВС~, Ь= ~АС~, с= ~АВ~ и угламио = А, В=В,3 =С. Предположим, что пара векторов (АВ,АС) образует положительно ориентированный репер. Тогда вершина С может быть вычислена через А и В так: сС=аАе ' +ЬВе' Глава 5. Сети с фиксированными типом и границей. 316 Доказательство. В самом деле, 5( — А)е' С=А+ с поэтому сС = А(с — Ье'в) + 5Ве'". С другой стороны, сумма векторов .4В, ВС и СА равна нулю, что на комплексном языке переписывается так: цл — и) + 5 — цл — сб откуда с — бе'" = ае что и требовалось.
Отметим сначала, что, по определению, линии Симпсона для не- вырожденного дерева Штайнера совпадают с соответствующими линиями Симпсона для бинарного дерева, полученного выбрасыванием фиктивных вершин. Поэтому доказательство предложения достаточно провести в предположении, что С бинарное дерево. Итак, пусть С бинарное дерево. Доказательство проведем по индукции. Если дерево состоит из одного ребра е, образ которого отрезок ~А, В), то линия Симпсона совпадает с этим отрезком.
С другой стороны, если Х = А, то по доказываемой формуле второй конец У линии Симпсона должен иметь вид: У= о~(е)В=В, ю(с) что верно. Далее, предположим, для всех бинарных деревьев, содержащих меньше чем и вершин степени 1 предложение доказано. Пусть теперь бинарное дерево С содержит п > 3 вершин степени 1.
По лемме 4.7, дерево С имеет усы (е', е"), не содержащие ребра е. Пусть 1 .. единственное ребро из С, смежное одновременно с е' и е". Без ограничения общности будем считать, что 1и" (1, е') > О, поэтому, в частности, 1ъ' (у,е") ( О. Обозначим через А и В образы вершин степени 1, инцидснтных соответственно е' и е", при отображении Г. Применим в сети Г шаг прямого хода обобщенного алгоритма Лйелзака, заменив вершины А и В на вершину С, такую что длины сторон а = ~ВС~, д = ~АС~ и с = (АВ) треугольника АВС равны соответственно Лог(е'), Ло~1ев) 5.3.
Сети Штейнера на плоскости. 317 и Лго(7") для некоторого Л > О, а вектора АВ и АС образуют положительно ориентированный репер. Обозначим через а и,б величины углов треугольника АВС в вершинах А и В. Отметим, что в соответствие с геометрическим смыслом взвешенного числа вращения имеем: а = — 1и (1, е").г/3, а,З = 1ъ""(г", е')х/3 Пусть Г': С' ь йз результат работы описанного только что шага алгоритма, и го .— вершина иэ С', соответствующая С. Положим 1 = Фи' (е, () .
Тогда для Г' предложение справедливо по предположению индукции. Иными сгювами, щ(ея)трс г~" ~~+ (()Се (отметим, что линия Симпсона сохраняется при работе обобщенного алгоритма ГИелзака). Однако, последнее слагаемое в этом выражении в силу леммы 5.6 можно переписать в виде 1 ы(Г)Се " 7~ = Лго(()Се 1 го(е) Лы(е) 1 ( Лы(е') А е ' О + Лю(ео) В е' ") е Лю(е) ( )(Р ) АР ьЫ ~де )л/3+ (Ео) ВГ,— ьсм ГГ ИП л/З)Š— Ыл/3 (е) = '(-" — щ(е ) Ае ' гн-г'.,ьц'гз + го(е') Ве ' ь' г" ~'"гз) ы(е) = — '(.'' откуда и вытекает требуемое утверждение. Предложение доказано. Далее, пусть теперь е некоторое неграничное ребро дерева С.
Разрезав С по ребру е, мы разобьем дерево С на два невырожденных дерева Штейнера, скажем С' и С". Обозначим через т'„..., т'ь, вершины степени 1 из С', не принадлежащие е, а через т,",..., т',!„вершины степени 1 из С", также не принадлежащие е. Пусть е„' ребро из С, инцидснтное т'„, а со ребро из С, инцидентное т„". Обозначим через 1„' и 1" чиста вращения 1и"'(е, е'„) и Ги" (е, е'„') соответственно, Следующее предложение немедленно вытекает иэ предложения 5.13. Предложение 5.14 Концы Л и У линии Симпсона Е мазут быть Глава 5. Сети с фиксированными типом и границей.
318 вычисленвь ио сле0ую»аим формулам: ь' » ь»1е')и»' е "»~»з ь»1е) лр=» А" у = ч ь»(ео)тое " ь»(е) ~-' р=-~ 5.3.2 сРункция Максвелла Пусть Г: С вЂ” » К- произвольная взвешенная минимальная сеть, и пусть См..., С невырожденные компоненты графа С, и Гд — — Г~п, соответствующие невырожденные компоненты сети Г. Рассмотрим некоторую невырожденную компоненту Г».
Для каждой граничной вершины ир из Сд обозначим через о„единичный вектор направления единственного входЯщего в веРшинУ Гд .. ир — » Ка РебРа Гд. ер -+ Ке сети Гд. Каждому вектору о„соответствует комплексное чис до е' » . Далее, пусть, как и выше, те — . комплексное число, соответствующее точке Г(ир). Обозначим через р(Г») комплексное число ~ трь»(ер) схр( — » ~рр), где сумма берется по всем граничным вершинам вр графа С,. Определение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
