Теория Морса минимальных сетей (1105006), страница 28
Текст из файла (страница 28)
Поэтому имеется толькодва варианта локальной структуры сети Γ в подвижной вершине . Обаварианта изображены на рис. 3.14.У невырожденной сети Γ, согласно предложению 3.9, имеется два особых ребра, направленных в концевые вершины некоторой стороны квадрата нормы ; а также можно выделить одно неособое ребро, направленное в противоположную сторону квадрата нормы .
Остальные дванеособых ребра должны быть парными ребрами. Следовательно, имеется два варианта локальной структуры сети Γ в подвижной вершине ,которые изображены на рис. 3.15.Перечислим теперь возможные комбинаторные расщепления сети Γранга 1. Поскольку для любого геометрического дерева с пятью граничными вершинами каждое внутреннее ребро задает разбиение множестваграничных вершин на двухэлементное и трехэлементное подмножества,то можно в их кодировках сцеплениями оставлять только двухэлементные подмножества. Таким образом, имеется десять возможных расщеплений сети Γ: {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5},{4, 5}.Приложения152Рис. 3.15:a)b)c)d)Мощные расщепления ранга 1 Мощные расщепления ранга 2{1, 2}, {3, 4}({1, 2}, {3, 4}){1, 2}, {3, 4}, {1, 4}, {2, 3}({1, 2}, {3, 4}), ({1, 4}, {2, 3}){4, 5}, {2, 3}, {3, 4}, {1, 5}({4, 5}, {2, 3}), ({3, 4}, {1, 5}){1, 3}, {2, 3}, {4, 5}({1, 3}, {4, 5}), ({2, 3}, {4, 5})Таблица 3.1:Для каждого из типов (a,b,c,d) локальной структуры сети Γ мощныерасщепления легко находятся с помощью общего критерия 3.1 минимальности параметрической сети.
В таблице 3.1 изображены все мощные расщепления ранга один и два для каждого из типов локальной структурысети Γ. Из этой таблицы следует доказываемое предложение. Для случая 5 граничных точек нам потребуется изучить мощные расщепления 2 (Γ) ранга 2 регулярной минимальной параметрической сети Γ[], где — геометрическое дерево с 5 граничными вершинами и 2подвижными. Прежде, чем сформулировать предложение о количестветаких расщеплений, докажем две вспомогательные леммы.Лемма 3.33 Пусть два вектора 1 и 2 направлены в одну сторонуквадрата манхэттенской нормы , причем направление хотя бы одного из этих векторов неособое.
Тогда конорма суммы любых соответствующих этим векторам субградиентов 1 и 2 строго больше 1, т.е.* (1 + 2 ) > 1.Приложения153Доказательство. Предположим, что вектор 1 имеет неособое направление. Тогда у соответствующего субградиента (однозначно определенного) 1 = (1 , 1 ) модули координат равны 1. Пусть, без ограниченияобщности, 1 = 1 = 1. Поскольку вектора 1 и 2 направлены в одну сторону квадрата нормы, то хотя бы одна из координат, скажем2 , любого субградиента 2 = (2 , 2 ) положительна. Следовательно,* (1 + 2 ) = max(|1 + 2 |, |1 + 2 |) = max(1 + 2 , |1 + 2 |) > 1. Лемма 3.34 Пусть дан конечный набор ковекторов { }=1 с условия∑︀ми: для всех ковекторов * ( ) ≤ 1 и = 0.
Тогда в этом наборе=1найдется пара векторов и , таких что * ( + ) ≤ 1.Доказательство. При = 2 утверждение леммы очевидно. Без ограничения общности, предположим, что все ̸= 0. Напомним, что дляманхэттенской нормы конорма ковектора = ( , ) выражается следующим образом: * ( ) = max(| |, | |).Допустим, что в данном наборе есть ковектор , у которого одна из∑︀координат равна 0, например = 0. Тогда, поскольку = 0, найдется=1ковектор = ( , ), у которого координата имеет противоположныйзнак координате . Следовательно, * ( + ) = max(| |, | + |) ≤max(| |, | |, | |) ≤ 1.Рассмотрим теперь случай, когда у всех ковекторов координата имеет обратный знак координате .
Тогда, по тем же соображени∑︀ям что и выше ( = 0), для ковектора = ( , ) найдется ко=1вектор = ( , ), такой что знаки соответствующих координат противоположны. Следовательно, * ( + ) = max(| + |, | + |) ≤max(| |, | |, | |, | |) ≤ 1.Осталось рассмотреть последний случай, когда у всех ковекторовиз данного набора обе координаты ненулевые и в данном наборе существует ковектор , у которого обе координаты имеют одинаковыезнаки. Предположим, для определенности, что у ковектора обе координаты положительны. Тогда, как и выше, существует ковектор =( , ), у которого координата отрицательна.
Если при этом координата также отрицательна, то * ( + ) = max(| + |, | + |) ≤max(| |, | |, | |, | |) ≤ 1. Если же > 0, то, по тем же соображениямПриложения154что и выше, существует ковектор = ( , ), у которого координата отрицательна. Если < 0, то * ( + ) ≤ 1; если > 0, то* ( + ) ≤ 1. Предложение 3.12 Пусть — геометрическое дерево с 5 граничными вершинами и 2 подвижными, а Γ[] — регулярная минимальная параметрическая сеть, затягивающая границу общего положения. Тогдадля сети Γ количество ее мощных расщеплений ранга два 2 (Γ) равнолибо 1 , либо 2.Доказательство.
Обозначим через граничные вершины дерева , ачерез и — подвижные вершины графа степени 2 и 3 соответственно.Пусть смежна с вершинами 4 и 5 , а смежна с вершинами 1 , 2 и3 . Через , = 1, 2, 3, обозначим ребро { , }; через — ребро {, }.Поскольку сеть Γ является минимальной параметрической сетью, то,согласно критерию 3.1, существует решение {0, } характеристическойсистемы сети Γ, каждая компонента которого принадлежит соответствующему субградиентному множеству (, ). Фактически на направленных ребрах (, ) заданы значения 0, их субградиентов, так что выполняются уравнения из критерия 3.1.
Напомним, что, по определениюсубградиентов, * (0, ) ≤ 1. Также, из критерия 3.1, у нас имеется уравнение 01 , + 02 , + 03 , + 0, = 0. Теперь мы находимся в условияхлеммы 3.34. Следовательно, имеются два значения субградиентов, например 01 , и 02 , , таких что * (01 , + 02 , ) ≤ 1.Рассмотрим расщепление Γ′ сети Γ, устроенное следующим образом.Параметризующий граф ′ получается из графа расщеплением в последнем вершины . Добавилось новое внутреннее ребро ′ , которое разделило ребра 1 , 2 , 3 , на пары 1 , 2 и 3 , . Покажем, что сеть Γ′также является минимальной параметрической сетью.
Найдем решение{0, } характеристической системы сети Γ′ , каждая компонента которого принадлежит соответствующему субградиентному множеству (, ).Для этого субградиенты {0, } старых ребер оставим прежними, а субградиент внутреннего ребра ′ положим с точностью до знака равным01 , + 02 , . Поскольку ребро ′ — вырожденное и * (01 , + 02 , ) ≤ 1,то ковектор 01 , + 02 , принадлежит субградиентному множеству ребра′ . Тогда, как легко проверить с помощью критерия 3.1, сеть Γ′ являетсяминимальной параметрической сетью, или, другими словами, расщепление Γ′ не является геометрическим. Таким образом, из 3 возможныхПриложения155расщеплений сети Γ найдется одно, которое не является геометрическимрасщеплением, т.е.
2 (Γ) ≤ 2.Покажем теперь, что по крайней мере одно геометрическое расщепление сети Γ в множестве 2 (Γ) существует. Для этого изучим возможныетипы локальной структуры сети Γ в подвижной вершине , в которойстыкуется 4 ребра 1 , 2 , 3 и . Рассмотрим сначала случай, когда ниодно из ребер 1 , 2 , 3 не вырождено. В этом случае, в силу типичности границы, количество особых ребер не превосходит трех.
Вариантылокальной структуры с не более чем двумя особыми ребрами уже были рассмотрены при доказательстве предложения 3.10 и в каждом изэтих вариантов было не менее одного расщепления. Рассмотрим теперьвариант, в котором имеется три особых ребра. Из-за типичности границы, ребро должно быть особым и все три особых ребра должны иметьразные направления. Следовательно, для одного неособого ребра, скажем 1 , найдется особое ребро, скажем 2 , такое что 1 и 2 направленыв одну сторону квадрата нормы .
В силу леммы 3.33, конорма суммылюбых двух субградиентов, соответствующих этим ребрам, строго больше 1. Поэтому комбинаторное расщепление Γ′ сети Γ, отделяющее ребра1 и 2 в подвижной вершине , может уменьшить длину сети Γ. Такимобразом, Γ′ ∈ 2 (Γ).Пусть теперь одно ребро, для определенности 1 , вырождено. Тогдаособое направление может иметь только внутреннее ребро . Если∙ — неособое ребро, то– либо сумма субградиентов ребер 2 и 3 строго больше 1. Вэтом случае эти ребра направлены в одну сторону квадратанормы или в смежные. Тогда геометрическим расщеплениемΓ′ ∈ 2 (Γ) сети Γ будет расщепление, отделяющее ребра 2 и3 от ребер 1 и .– либо сумма субградиентов ребер 2 и 3 равна 0. В этом случаеребра 2 и 3 направлены в противоположные стороны квадрата нормы, и одно из этих ребер, скажем 2 , с ребром направлены либо в одну сторону квадрата нормы, либо в смежные.Тогда для соответствующих субградиентов и 2 выполненонеравенство * ( + 2 ) > 1, и геометрическим расщеплениемΓ′ ∈ 2 (Γ) сети Γ будет расщепление, отделяющее ребра и2 от ребер и 2 .Приложения156∙ — особое ребро, то– либо сумма субградиентов ребер 2 и 3 строго больше 1.
Вэтом случае эти ребра направлены в одну сторону квадратанормы или в смежные. Тогда геометрическим расщеплениемΓ′ ∈ 2 (Γ) сети Γ будет расщепление, отделяющее ребра 2 и3 от ребер 1 и .– либо сумма субградиентов ребер 2 и 3 равна 0. В этом случаеребра 2 и 3 направлены в противоположные стороны квадрата нормы, и одно из этих ребер, скажем 2 , с ребром направлены в одну сторону квадрата нормы.
Тогда, по лемме 3.33 длясоответствующих субградиентов и 2 выполнено неравенство* ( + 2 ) > 1, и геометрическим расщеплением Γ′ ∈ 2 (Γ) сети Γ будет расщепление, отделяющее ребра и 2 от ребер и2 .5.6Комбинаторная морсовость функции ℓ для случаев 3, 4, 5 граничных точекДля применения основной формулы из теоремы 2.2 нам необходимо проверить, что функция ℓ на пространстве является комбинаторной функцией Морса.Поскольку функция ℓ на каждом страте ⟨⟩ выпукла и “на бесконечности равна бесконечности”, то она достигает своей точной нижней гранина каждом страте пространства . Следовательно, условие 1) из определения комбинаторной функции Морса выполняется для произвольногоколичества граничных точек.Однако, условие 2) этого определения выполняется только для случаев 3, 4 и 5 граничных точек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
