Теория Морса минимальных сетей (1105006), страница 27
Текст из файла (страница 27)
Поэтому субградиент для неособогоребра определен однозначно. Напомним, что переменная , в решениихарактеристической системы сети Γ принимает значение из субградиентного множества (, ) ребра . Поэтому для неособого ребра значениепеременной , определено однозначно.Поскольку субградиент ребра, вообще говоря, определен неоднозначно, то это выражение (“субградиент ребра”) некорректно.
Однако, если унас имеется некоторое решение {0, } характеристической системы сетиΓ, то это решение однозначно приписывает каждому ребру один из егосубградиентов, а именно — 0, . В такой ситуации выражение “субградиент ребра” становится корректным.Лемма 3.28 Пусть невырожденная минимальная параметрическаясеть Γ топологии звезда имеет одно особое ребро .
Тогда∙ — четно;Приложения146∙ решение характеристической системы сети Γ единственно;∙ компонента , решения характеристической системы сети Γпринимает одно из крайних значений субградиента для ребра .Доказательство. Пусть для определенности особое ребро направленовертикально вверх. Будем последовательно удалять из совокупности всехнеособых ребер пары ребер с противоположно направленными субградиентами. В конце концов у нас останется один из следующих вариантов:a) Одно особое ребро .b) Одно особое ребро и несколько (не менее одного) неособых ребер,направленных в одну сторону квадрата нормы .c) Одно особое ребро , несколько (не менее одного) неособых ребер,направленных в одну сторону квадрата нормы и несколько (неменее одного) неособых ребер, направленных в сторону квадратанормы, смежную к вышеупомянутой.Обозначим через 0, решение характеристической системы сети Γ.
Согласно критерию 3.1, сумма всех субградиентов 0, ребер равна 0. Поэтому и сумма субградиентов оставшихся ребер равна 0. Следовательнослучая a) быть не может. Случая c) также быть не может. В самом деле, конорма суммы субградиентов оставшихся неособых ребер в данномслучае строго больше 1. Следовательно, сумма субградиентов всех этихнеособых ребер и особого ребра , конорма которого равна 1, не можетбыть равна 0.В случае b) количество оставшихся неособых ребер не превосходитодного, иначе опять (по тем же причинам, что и в случае c)) суммасубградиентов всех оставшихся ребер не может равняться 0. Таким образом, остается одно особое ребро и одно неособое. Следовательно, должно быть четным.
Субградиент неособого ребра всегда единственен.Поэтому субградиент 0, особого ребра также определяется однозначно, как противоположно направленный, и принимает одно из крайнихсвоих значений. Аналогичными рассуждениями доказываются и следующие две леммыПриложения147Лемма 3.29 Пусть невырожденная минимальная параметрическаясеть Γ топологии звезда не имеет особых ребер. Тогда — четно.Лемма 3.30 Пусть невырожденная минимальная параметрическаясеть Γ топологии звезда имеет два особых ребра 1 и 2 .
Тогда ребра1 и 2 направлены в две смежные вершины квадрата нормы , и1. если — четно, то решение характеристической системы длясети Γ единственно; и компоненты этого решения, отвечающиеособым ребрам 1 и 2 , принимают одно из крайних значений субградиента для этих особых ребер.2. если — нечетно, то решение характеристической системы длясети Γ единственно; и компоненты этого решения, отвечающиеособым ребрам 1 и 2 , принимают средние значения субградиентадля этих особых ребер.Лемма 3.31 Пусть в множестве minℓ [] нет сетей с вырожденнымиребрами.
Тогда лучший представитель множества minℓ [] имеет1. 0 особых ребер, если — четно;2. 2 особых ребра, если — нечетно.Доказательство. Пункт 2) утверждения леммы следует из лемм 3.28,3.29 и 3.30.Докажем пункт 1). Пусть Γ — минимальная параметрическая сетьиз minℓ []. Из лемм 3.28 и 3.30 следует, что в решении характеристической системы сети Γ субградиенты особых ребер обязаны приниматьсвои крайние значения. Это означает, что мы можем пошевелить немного подвижную вершину сети Γ, так чтобы все ребра стали неособыми,а их субградиенты (уже определяемые однозначно) остались прежними.При этом новая сеть Γ̃ останется минимальной параметрической сетью,т.е. будет принадлежать множеству minℓ []. Таким образом получитсялучший представитель множества minℓ [] без особых ребер.
Лемма 3.32 Пусть в minℓ [] имеется сеть Γ с вырожденным ребром,тогда1. если — нечетно, то minℓ [] состоит из одной сети Γ;Приложения1482. если — четно, то существует невырожденная сеть Γ̃ ∈ безособых ребер.Доказательство. Напомним, что мы рассматриваем сети, затягивающие границы общего положения.
Поскольку у сети Γ имеется одно вырожденное ребро, то одна из граничных вершин совпадает с подвижной,и, следовательно, в силу п.2) из определения границы общего положения,все остальные невырожденные ребра обязаны быть неособыми.Мысленно удалим у сети Γ все пары невырожденных ребер с противоположно направленными субградиентами. Тогда, проводя рассуждения, аналогичные рассуждениям из доказательства леммы 3.28, получаем, что— при нечетном не останется ни одного невырожденного ребра.Предположим, что кроме Γ существует еще сеть Γ̃ ∈ minℓ []. В силувыпуклости множества minℓ [], любые две точки из minℓ [] можно соединить отрезком, лежащим в minℓ []. Следовательно, в любой достаточно малой окрестности сети Γ должна существовать минимальная параметрическая сеть из без вырожденных ребер.
Но малое шевелениеподвижной вершины, делающее вырожденное ребро невырожденным,не изменит субградиентов изначально невырожденных ребер, поэтомусумма субградиентов всех изначально невырожденных ребер останетсяравной 0. Следовательно, и субградиент нового невырожденного ребрадолжен быть равным 0. Чего не может быть у невырожденных ребер,поскольку любой субградиент невырожденного ребра имеет единичнуюконорму.— при четном останется ровно одно невырожденное ребро .
Следовательно, субградиент вырожденного ребра должен быть противоположно направлен к субградиенту ребра . Сдвинем достаточно мало подвижную вершину в направлении ребра . Тогда у вновь образовавшейся сетиΓ̃ все ребра будут невырожденными, и сумма субградиентов всех ребербудет равной 0. Следовательно, по критерию 3.1, сеть Γ̃ — минимальнаяпараметрическая сеть из minℓ []. Назовем два невырожденных неособых ребра парными ребрами , еслиих субградиенты противоположно направлены. Резюмируя все вышесказанное, сформулируем предложениеПриложения149Предложение 3.9 Пусть minℓ [] — множество минимальных параметрических сетей топологии звезда, затягивающих типичную границу из точек на манхэттенской плоскости. Тогда1.
Если — нечетно, то minℓ [] состоит всего из одной сети Γ.Причем, после удаления парных ребер сеть Γ будет устроена следующим образом:∙ если Γ — невырождена, то из трех оставшихся ребер два особых ребра направлены в концевые вершины какой-либо стороны квадрата нормы , а одно неособое ребро — во внутренность противоположной стороны квадрата нормы .∙ если Γ — вырождена, то остается только одно вырожденноеребро.2. Если — четно, то существует невырожденный лучший представитель Γ ∈ minℓ [] без особых ребер. Причем у любого невырожденного лучшего представителя без особых ребер все ребра разбиваются на парные ребра.5.5Мощные расщепления минимальных параметрических сетей некоторых типовНачнем с изучения мощных расщеплений минимальных параметрических сетей типа звезда в случаях 3, 4 и 5 граничных точек.В случае 3 граничных точек никаких расщеплений нет.В случае 4 граничных точек для сети Γ имеются только расщепления с одним внутренним ребром.
Все геометрические расщепления рангаодин, т.е. с одним внутренним ребром, являются мощными. Оказывается,имеет место предложениеПредложение 3.10 Пусть Γ — невырожденная минимальная параметрическая сеть топологии звезда без особых ребер, затягивающаятипичную границу из 4 точек манхэттенской плоскости. Тогда длясети Γ количество ее мощных расщеплений ранга один 1 (Γ) можетбыть либо 1, либо 2.Приложения150Рис.
3.13:Доказательство. Согласно предложению 3.9, все ребра сети Γ разбиваются на парные ребра. Таким образом, имеется только два типа локальной структуры сети Γ в подвижной вершине. Эти типы показаны нарис. 3.13.Из трех возможных расщеплений ({1, 2}, {3, 4}), ({1, 3}, {2, 4}) и({1, 4}, {2, 3}) (здесь приведены их кодировки сцеплениями, см. параграф 2.2 главы 1) сети Γ геометрическими (мощными) расщеплениямиявляются только∙ для типа a) локальной структуры — ({1, 2}, {3, 4});∙ для типа b) локальной структуры — ({1, 2}, {3, 4}) и ({1, 4}, {2, 3});что легко проверяется с помощью общего критерия 3.1 минимальностипараметрической сети в нормированном пространстве.
В случае 5 граничных точек для сети Γ имеются расщепления рангаодин и ранга два. Все геометрические расщепления ранга один являютсямощными. Оказывается, имеет место предложениеПредложение 3.11 Пусть Γ — минимальная параметрическая сетьтопологии звезда, затягивающая типичную границу из 5 точек манхэттенской плоскости. Тогда для сети Γ количество ее мощных расщеплений ранга один 1 (Γ) не меньше 2 и не больше 4, и оно связанос количеством мощных расщеплений ранга два 2 (Γ) следующим образом:∙ если 1 (Γ) = 2, то 2 (Γ) = 1;Приложения151Рис.
3.14:∙ если 1 (Γ) = 3, то 2 (Γ) = 2;∙ если 1 (Γ) = 4, то 2 (Γ) = 2.Доказательство. Будем различать два случая: вырожденная и невырожденная сеть Γ.У вырожденной сети Γ только одно ребро имеет нулевую длину, скажем ( 5 ). Остальные ребра невырожденные и неособые. Согласно предложению 3.9, эти ребра разбиваются на парные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
