Теория Морса минимальных сетей, страница 7

Обозначим получившийся графчерез ′ . Будем говорить, что граф ′ получен из графа расщеплениемвершины .Аналогичные операции можно определить и для сетей.Определение. Пусть Γ : () → — некоторая сеть с вырожденным˜ граф, полученребром = Γ|(,) , т.е. Γ() = Γ(). Обозначим через ный из редукций по ребру (, ); а через — вершину, заменившую˜ → следующим обвершины и . Определим теперь сеть Γ̃ : ()разом: положим отображение Γ̃ на неизменившихся вершинах равнымΓ, а на вершине равным Γ() (= Γ()), т.е. Γ̃| ()∖{,} = Γ| ()∖{,}и Γ̃() = Γ() = Γ().

Будем говорить, что сеть Γ̃ получена из сети Γредукцией по вырожденному ребру .Определение. Пусть Γ : () → — некоторая сеть, и = Γ| —некоторая ее вершина. Обозначим через ′ граф, полученный из расщеплением вершины ; а через и — вершины, заменившие вершинуСети в метрических пространствах33. Определим теперь сеть Γ′ : (′ ) → следующим образом: положимотображение Γ′ на неизменившихся вершинах равным Γ, а на вершинах и равным Γ(), т.е. Γ′ | ()∖ = Γ| ()∖ и Γ′ () = Γ′ () = Γ(). Будемговорить, что сеть Γ′ получена из сети Γ расщеплением вершины .Очевидно, что операции редукции по вырожденному ребру и расщепление вершины не изменяют длины сети, т.е.

ℓ(Γ) = ℓ(Γ̃) = ℓ(Γ′ ).1.5Компоненты вырождения. Приведенные сетиОпределение. Рассмотрим сеть Γ[]. Связные компоненты множествавсех вырожденных ребер графа назовем компонентами вырожденияпараметризующего графа сети Γ. Из формальных соображений, каждуювершину графа , все инцидентные ребра которой невырождены, такжебудем считать компонентой вырождения. Каждая компонента вырождения, очевидно, является подграфом в , все вершины которого отображаются в одну и ту же точку.

Ясно, что две различные компонентывырождения графа не пересекаются.Снова рассмотрим сеть Γ. Проредуцируем ее по всем вырожденнымребрам. Полученную сеть Γ̃ будем называть приведенной параметрической сетью для сети Γ. Приведенная сеть уже не содержит вырожденныхребер.Пусть Γ — параметрическая сеть с некоторой границей Γ : → ,и Γ̃ — соответствующая приведенная сеть. Вершину приведенной сетиназовем подвижной, если ее прообраз при редукции содержит хотя быодну подвижную вершину сети Γ; вершину приведенной сети назовем чисто подвижной, если ее прообраз при редукции не содержит граничныхвершин сети Γ. Остальные вершины сети Γ̃ будут считаться граничными.22.1Геометрические деревьяОпределение множества геометрических деревьев Определение.

Геометрическим деревом будем называть дерево безвершин степени 2, у которого все вершины степени 1 считаются граничными, а остальные подвижными. Также будем считать, что все вершиныСети в метрических пространствах34степени 1 у геометрического дерева, пусть их штук, помечены (занумерованы) различными числами от 1 до .Обозначим через множество всех геометрических деревьев с граничными вершинами, а через () — множество деревьев из , имеющихранг .

Как правило, параметр у множества ясен из контекста и мыего будем опускать. Поскольку количество вершин степени 1 у деревьевиз равно , то количество подвижных вершин лежит в пределах от 1до −2, следовательно количество их внутренних ребер (т.е. ранг) лежитв пределах от 0 до − 3. Таким образом, имеет место разбиение = (0) ⊔ · · · ⊔ (−3) .Скажем несколько слов об операциях расщепления и редукции длякласса геометрических деревьев . Очевидно, что операция редукции повнутреннему ребру дерева ∈ не выводит за пределы класса .

Болееточно, если дерево имело ранг , то после редукции по его внутреннему˜ будет равен − 1. Заметим, чторебру ранг у полученного дерева операция редукции по граничному ребру выводят за пределы класса ,поскольку на единицу уменьшается количество вершин степени один.Поэтому, если не оговорено противное, то все редукции геометрическихдеревьев и сетей, параметризованных геометрическими деревьями, будутпроводиться только по внутренним ребрам.Очевидно также, что если в вершине некоторого графа делатьрасщепление () = 1 ⊔ 2 , в котором одно из множеств (1 , 2 ) пустое или одноэлементное, то это приведет к появлению дополнительнойвершины степени 1. Следовательно, подобные расщепления вершин геометрического дерева ∈ выводят из класса .

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

. . , } на пары подмножеств (1 , 1 ) и(2 , 2 ), {1, . . . , } = 1 ⊔ 1 = 2 ⊔ 2 , называются сцеплением, еслиСети в метрических пространствах35каждое из подмножеств разбиений состоит по крайней мере из двух элементов и одно из подмножеств первого разбиения целиком содержит одноиз подмножеств второго разбиения.Далее нам понадобится понятие ветки дерева (не обязательно геометрического). Выкинем из множества ребер дерева какое-нибудь произвольное ребро . Тогда распадется на два поддерева 1 и 2 , которыемы и будем называть ветками дерева , инцидентными ребру .

Ветка1 будет называться дополнительной к ветке 2 , и наоборот.Рассмотрим теперь произвольное геометрическое дерево ранга измножества . Дерево порождает некоторый набор разбиений множества {1, . . . , } на пары (1 , 1 ),. . . , ( , ), любые две из которых образуют сцепление, следующим образом. Любое внутреннее ребро дерева задает разбиение граничных вершин на два множества. И, посколькувсе граничные вершины геометрического дерева помечены различнымичислами от 1 до , это разбиение задает некоторое разбиение множества{1, .

. . , } на пару непустых подмножеств ( , ). Покажем теперь, чтолюбые два разбиения ( , ) и ( , ) образуют сцепление. Рассмотримдве ветки и дерева , инцидентные ребру . Граничным вершинам из ветки соответствует множество , граничным вершинамиз ветки — множество . Предположим, что ветка содержитвнутреннее ребро . Рассмотрим две ветки и дерева , инцидентные ребру . Тогда та из этих веток, которая не содержит ребра , для определенности ветка , обязана целиком содержаться в ветке . Следовательно, ⊂ .

Это и означает, что два разбиения ( , )и ( , ) образуют сцепление.Порожденный таким образом набор разбиений множества {1, . . . , }на пары (1 , 1 ),. . . , ( , ), любые две из которых образуют сцепление,назовем кодировкой сцеплениями геометрического дерева .Лемма 1.1 Каждый набор разбиений множества {1, . . . , } на пары(1 , 1 ),. .

. , ( , ), любые две из которых образуют сцепление, является кодировкой сцеплениями некоторого геометрического дерева ранга с граничными вершинами.Доказательство. Пусть дан набор разбиений множества {1, . . . , } напары (1 , 1 ),. . . , ( , ), любые две из которых образуют сцепление.Построим по этому набору геометрическое дерево ранга с граничными вершинами.Сети в метрических пространствах36Перед построением требуемого дерева сделаем предварительную под˜ с граничнымиготовку. Рассмотрим некоторое геометрическое дерево вершинами и некоторую его подвижную вершину .

Любое расщеплениевершины задается разбиением множества ребер (), инцидентныхвершине , на два множества 1 = {1 , . . . , } и 2 = {1 , . . . , }.Разбиение () = 1 ⊔ 2 определяет разбиение множества {1, . . . , } = ⊔ , где = {. . . }1 ∪ · · · ∪ {. . . } и = {. . .

}1 ∪ · · · ∪ {. . . } . Заметим,что в множествах и не менее двух элементов. Мы будем говорить,что разбиение (, ) согласовано с расщеплением (1 , 2 ). Предположим, что в вершине можно сделать два расщепления, согласованныхсо сцепленными разбиениями (1 , 1 ) и (, ) (пусть для определенности1 ) ), т.е. совокупность всех наборов {. . . } , ∈ () можно разбитьна две подсовокупности{. . . }1 ∪ · · · ∪ {.

. . } = 1{. . . }1 ∪ · · · ∪ {. . . } = 1и{. . . }1 ∪ · · · ∪ {. . . } = {. . . }1 ∪ · · · ∪ {. . . } = После того, как мы сделаем расщепление подвижной вершины надве вершины 1 и 2 , согласованное с парой (1 , 1 ), мы получим, чтос вершиной 1 связаны наборы чисел {. . . }1 , . . . , {. . . } , {. . . }+1 , где{. . . }+1 = {.

. . }1 ∪ · · · ∪ {. . . } ,; а с вершиной 2 — наборы чисел{. . . }1 , . . . , {. . . } , {. . . }+1 , где {. . . }+1 = {. . . }1 ∪ · · · ∪ {. . . } .Заметим, что 1 можно дальше расщепить согласованно с парой(, ), а 2 — нельзя. Причина состоит в том, что одно из множеств(в данном случае ) строго содержится в одном из наборов (в данномслучае в {.

. . }+1 ), связанных с вершиной 2 . Поскольку дальнейшиерасщепления только укрупняют наборы {. . . } , то после произвольногоколичества расщеплений имеется только одна вершина, которую можнорасщепить парой (, ).Теперь требуемое дерево c кодировкой (1 , 1 ),. . .

, ( , ) строится следующим образом. Возьмем дерево 0 ∈ (0) ранга 0, у которогоединственная подвижная вершина . Очевидно, что в этой подвижнойвершине для любого разбиения ( , ) из кодировки дерева можносделать расщепление, согласованное с этим разбиением. При первом расщеплении, согласованным с (1 , 1 ), вершина распадется на две вершины 1 и 2 . Оставшийся набор разбиений (2 , 2 ),.

. . , ( , ), в своюочередь, также распадется на две части: разбиения, для которых существует расщепление вершины 1 , согласованное с данным разбиением,Сети в метрических пространствах37и разбиения, для которых не существует расщепления вершины 2 , согласованного с данным разбиением. Затем делается расщепление соответствующей вершины, согласованное с разбиением (2 , 2 ) и т.д. Послевсех расщеплений получим дерево . При доказательстве следующей леммы 1.3 нам понадобится так называемая лемма об усах .

Определим сначала усы у дерева . Удалимиз дерева все концевые ребра вместе с инцидентными им концевымивершинами; получим дерево ′ . Концевую вершину дерева ′ вместе синцидентными ей концевыми ребрами дерева назовем усами дерева ,а саму вершину назовем точкой крепления усов. Поскольку в любомдереве с количеством вершин не менее 2 имеется не менее двух концевыхвершин, см. [4], то получаем лемму об усах.Лемма 1.2 В любом дереве с количеством подвижных вершин не менее2 имеется не менее двух усов.Лемма 1.3 Два геометрических дерева 1 ∈ и 2 ∈ с одинаковойкодировкой сцеплениями изоморфны (как помеченные графы).Доказательство. Обозначим кодировку сцеплениями деревьев 1 и 2через (1 , 1 ),.