Геометрические свойства локально минимальных сетей (1097521), страница 32
Текст из файла (страница 32)
Отметим, что., по опРеДелению, хгу = х,. ДлЯ кажДой поДвижной веР- шины 1;. графа С~ запишем векторное линейное уравнение с,х; =Хп Е 1ту смежна с 1", где суммирование берется по всем (не только подвижным) вершинам 1' графа Са, соседним с 1;. 3.1. Параметрические сети. 145 Определение. Линеиную систему уравнений с, х;т — — 1ут„ Е 1; смежна с Ъ' т = 1,...,Й, где Й количество подвижных вершин графа С~~, назовем характеристической системой локальной сплруктуры вершины Р.
Объединение характеристических систем локальной структуры по всем подвижным вершинам 1' приведенной сети называется характеристической системой локальной структуры сети Ф. Замечание. Характеристическая система локальной структуры каждой вырожденной вершины ут параметрической сети зависит, вообще говоря, от выбора правильной ориентации соответствующей приведенной колшоненты.
Однако, решения систем, соответствующих различным ориентациям. получаются друг из друга подходящей заменой знаков их и-мерных компонент. Поскольку, как мы увидим из нижеследующего предложения, нас интересуют только модули и-мерных компонент решений характеристической системы, мы, допуская тем самым определенную вольность, не бу.дем в дальнейшем различать системы, соответствующие разным правкчьнылт ориентациям, Предложение 3.11 Пусть Ф ттараметричсская сетиь обитого вида. Тогда, если сеть Ф сильно локально минимальна, то все ее ребра геодезические, и, кроме тпого, ее хариктеристическая система локальной структпуры имееттт тиикое ретиение, чтпо значения каждой его и-мерной переменной х, по модулю не превосходит единицы.
Если характеристическая систаема локальной структуры геодезической сети Ф имеет такое решение, что значение каждой его пмерной компоненты хм по модулю строго меньше единицы,. то сеть Ф сильно лок льна минимальна. Доказательство. Мы получилт утверждение предложения как следствие из предложения 3.10. Определим вид субградиентного множества функпии г = Кл (Е) в точке О' = (О,..., 0) Е 2"ь. Для этого лиы представилт фу.нкпию т'.к(Е) в виде линейной комбинации простейших выпуклых функций ~~Е, — Е )( с положительными коэффициентами отт, и воспользуемся предложением 3.9, описывающим структуру субградиентного множества линейной комбинации выпуклых функций.
Лемма 3.2 Субградиентное множество функции г = 'ОЕ, — Е ~~, опре- деленной на гл"", в точке О' вида Е„= О, о = 1,..., й, имеет видт ((Ят,...,Мь)у: )(Х,(! < 1, !)Лтз!) < 1, Дтт = — Х„тУт = 0 при и ~ т, и ~ у). Глава 3. Чокальная структура минимальных сетей. 146 Доказательство. Напомним, что, по определению, вектор Х из Кьь является субградиентом функции 1; Ко" — ь Ю в точке Х Е Ил" если и только если (Х,У вЂ” Х) < 1(У) — 1'(Л) для произвольного вектора У Е Кьь.
В нашем случао, Х = (Хм..., Ать), У = (Ум...,.Уь), и это условие переписывается в виде ~(Л', У„) < ~~У, — 1'' ц для произвольных У„Е й". Пусть Я вЂ” — произвольный субградиент функции ))Е, — Е;)(. Поскольку правая часть неравенства (*) зависит только от 1; и 1,то, очевидно, Х = О при а отличных от 1 и ~. Для таких векторов Х условие (*) принимает вид (Хо У,) + (Х,У) < ~~1; — 1.~~ для произвольных 1'; и 1' Е Кп.
В частности, если, скажем, 1;. = О. то, чтобы наше неравенство выполнялось для любого вектора 1'з необходимо ЙХ ~~ < 1. Аналогично, 'ОЛ;~~ < 1. Далее, если 1; = 1', то правая часть неравенства обращается в ноль. Левая часть при этом имеет вид (Х, + Х., К) и должна быть неположительна для любого 1;з в частности, для У; = Х, -~-Х.. Поэтому Х, = — А .
Итак, каждый субградиент функции ~~Е, — Е ~~ имеет вид, описанный в лемме. Обратно, если вектор Х = (Жм...,Яь) Е Кол имеет указанный вид, то для любого вектора У = (Ум..., Уь) получим: поскольку ))Х,/( < 1 по условию. Поэтому в атолл случае Х является субградиентом функции ()Е, — Е, 'О' в точках вида Е, = Е~ = О. Лемма доказана.
Из леммы 3.2 и предложения 3.9 вытекает следующий результат. Лемма 3.3 Вектор Х = (Хм...,Хе) е Я"ь принадлежит субградиентному множеству функции еь (Е) в точке О', если и только если каждал его и-мерная компонента ~~,, г' = 1,..., к, представимо в виде Ап ''а — ~ гбРм~ 3 где р,: - некоторые векторы иэ 2", такие что йро~а < 1, и ро —— — рхн а суммирование производится по таким и только такам индексам 1, что веРшина $' смежна с веРшиной Г, в компоненте Сл .
3.1. Параметрические сети. 147 Пусть (с;. ) -- как и выше, матрица смежности, соответствующая некоторой правильной ориентации приведенной компоненты С~~ . Положим я; = р,, если с, > О, т.е. если вершина 1', является началом всех ребер, идущих из нее в вершину 1'. Отметим, что каждой неупорядоченной паре 11;, 1~.) соседних вершин графа С~э соответствует свой вектор тб.
В этих обозначениях, лемма 3.3 может быть переформулирована так. Вектор Х = (Хы...,Хь) е К"ь принадлежит субградиентному множеству функции Ки(Е) в точке О', если и только если существует такой набор и-мерных векторов л;., соответствующих неупорядоченным парам 1Ъ"„71) вершин графа С~'. что ()л,.!) < 1, и каждая и-мерная компонента Л;, 1 = 1,..., Й, вектора Х представима в виде Х, = ~ ~сия;,. Отметим, что утверждения 3.1 и 3.2 непосредственно выводятся из предложенил 3.11.
В самом деле, сложив все уравнения характеристической системы локальной структуры произвольной вершины 1' приведенной сети, мы получим в левой части О, так как сп = — с ь а в правой части сумму всех Х„выходящих из вершины 1', что эквивалентно утверждению 3.1, т1тобы получить утверждение 3.2, достаточно ьщожить уравнения, соответствующие вершинам сети, отнесенным к одному и тому же элементу разбиения. В результате все переменные, соответствующие соседним вершинам сети, попавшим в один и тот же элемент разбиения, сократятся, и мы получим следующие два уравне- ния: об хм — — Л'л, Е 1 е А, у е В, г смежна с у сия, Е ге А, у Е В, г смежна с 1 Так как максимум модуля левой части каждого из выражений, при условии ~~лп ~~ < 1, равен или, мы получаем утверждение 3.2.
Последнее условие, очевидно, эквивалентно условию существованию решения (л; ) характеристической системы локальной структуры для вершины 1', такого что дя, ~~ < 1. При этом, если все неравенства выполняются как строгие, т.е, есяи !)зэ1!) < 1, то опорная гиперплоскость, соответствующая субградиенту Х пересекает конус С~ лишь по точке Г). Теперь утверждение предложения непосредственно вытекает из предложения 3.10. Доказательство закончено. Глава 3.
Локальная структура минимальных сетей. 148 Характеристическая система уравнений локальной структуры записы- вается так: < Чхо1 — Чхш Чх01 + Чх12 Чх20 Ч212 Р1 1'о РЛ'1 Р21 ш (и) где хш, х12 и х20 неизвестные векторы из л2, а 1112, 1 = О, 1, 2, единичные векторы А1ЯД~А,Я. Отметим, что сумма векторов 1111, 1 = О, 1, 2, равна нулю по условию; сумма левых частей уравнений системы (*) также, очевидно, равна нулю. Общее решение системы (~) имост вид: (хо1 212,хво) = Рор(Ч+ У (1Чор+ х11Р))(Ч+ У: У) где у — произвольный вектор из 22. Чтобы проверить, имеются ли среди решений системы (*) удовлетворяющие условиям ~~х, ~~ < 1, пе- репишем решение системы в виде; Чхо1 = Р110+ ЧУ, Чхш = — Р212+ ЧУ. Пример.
Вновь рассмотрим сеть Ф из предыдущего примера. А именно, пусть С -. граф, имеющий шесть вершин Р„1,)„1 = О, 1, 2, ребра вида РД1 в количоство р штук для каждого 1, и ребра вида ЯЯ в количестве Ч штук для каждой пары (1.',1), 1 < 11 Сеть Ф: С вЂ” 1 К2 параметризована графом С; граница 13 сети Ф отображает множестве вершин (Р1) на множество вершин правильного треугольника.4оА1А2, наконец, отображение Ф переводит ребра ЯД1 в центр Я этого треугольника, а ребра РД1 в отрезки А,Я. Выясним, при каких р и Ч сеть Ф является сильно локально минимальной.
Для этого, в соответствии с предложением 3.11, достаточно записать характеристическую систему локальной структуры и проверить,. имеются ли среди ее решений такие, что все их 2-мерные компоненты по модулю нс превосходят 1. Приведенная сеть Ф имеет только одну подвижну.ю вершину. точку Я, поэтому. характеристическая система уравнений локальной структуры в этом случае совпадает с характеристической системой локальной структуры для вершины Я. Приведенная компонента С~~ состоит из трех вершин Ц1, Я2 и Яз, и ЗЧ ребср вида ЯЩ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
