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

. . , ( , ). Предположим теперь, что деревья 1 и 2неизоморфны. Рассмотрим дерево 1 . Согласно лемме об усах 1.2 у 1имеются усы, состоящие из точки крепления и граничных ребер, инцидентных граничным вершинам с номерами 1 ,. . . , . Вершине инцидентно также одно внутреннее ребро дерева 1 . Ребру соответствуетнекоторое разбиение ( , ) множества {1, .

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

Эта ветка не содержит внутренних ребер, поскольку,если бы она содержала какое-нибудь внутреннее ребро ′2 с соответствующим разбиением (′ , ′ ), то тогда одно из множеств ′ или ′ строгосодержалось бы в множестве .Таким образом, дерево 2 имеет усы такого же вида как и у дерева˜1 и ˜ 2 , полученные1 . Поэтому, если 1 и 2 неизоморфны, то деревья Сети в метрических пространствах38из деревьев 1 и 2 редукцией по ребрам 1 и 2 соответственно, так˜ 1 и действуем по схеме,же неизоморфны. Далее находим усы в дереве приведенной выше.

Проделав редукций, мы из дерева 1 и дерева 2получим одно и то же дерево 0 ∈ (0) , что противоречит неизоморфности начальных деревьев 1 и 2 . Резюмируя все вышесказанное, можно сделать следующий вывод.Утверждение 1.1 Кодировка сцеплениями устанавливает взаимнооднозначное соответствие между наборами сцепленных разбиений множества {1, .

. . , } и геометрическими деревьями из множества .Замечание. Кодировка сцеплениями позволяет сравнивать два внутренних ребра 1 и 2 , принадлежащих геометрическим деревьям 1 и 2соответственно. Будем говорить, что два внутренних ребра 1 ∈ (1 )и 2 ∈ (2 ) одинаковы (равны, эквивалентны и т.п.), если определяемые ими элементы (1 , 1 ) и (2 , 2 ) из кодировок сцеплениями деревьев1 и 2 равны. Аналогичным образом, внутренние ребра сетей можносравнивать посредством сравнения соответствующих ребер их параметризующих геометрических деревьев.2.3Частичный порядок на множестве Определим отношение ≤ частичного порядка на множестве следующим образом.

По определению ′ ≤ , если и только если дерево ′получено из дерева с помощью последовательных операций расщепления подвижных вершин. Дерево ′ назовем потомком дерева ; в своюочередь, дерево будем называть родителем (предком) для дерева ′ .Лемма 1.4 Для двух геометрических деревьев 1 и 2 из отношение1 ≤ 2 имеет место тогда и только тогда, когда для их кодировоксцеплениями выполняется включение(1)(1)(1)(1)(2)(2)(2)(2){(1 , 1 ), . . . , (1 , 1 )} ⊃ {(1 , 1 ), . . . , (2 , 2 )}.Доказательство.

В одну сторону утверждение леммы является непосредственным следствием определения кодировки сцеплениями. В другую сторону — следует из лемм 1.1 и 1.3. Сети в метрических пространствах39Предложение 1.1 Для любого набора деревьев 1 , . . . , ∈ в множестве имеется точная верхняя грань.Эту точную верхнюю грань мы будем называть общим родителем (предком) для деревьев 1 ,.

. . , .Доказательство. Рассмотрим кодировки сцеплениями для деревьев1 ,. . . , :(1)(1)(1)(1)1 — {(1 , 1 ), . . . , (1 , 1 )};...()()()() — {(1 , 1 ), . . . , ( , )}.Рассмотрим теперь дерево , у которого кодировка сцеплениями образована пересечением кодировок сцеплениями деревьев . В силу леммы 1.4, дерево не меньше, чем любое дерево . Предположим, чтосуществует еще какое-то дерево ′ , которое не меньше всех . Тогдаего кодировка сцеплениями обязана содержаться в пересечении кодировок сцеплениями деревьев , а значит дерево ′ не меньше дерева .Таким образом, дерево является точной верхней гранью набора деревьев 1 ,.

. . , . 2.4Перечисление геометрических деревьевФормулировка задачиПеречислить с точностью до изоморфизма все геометрические деревьяс граничными вершинами и подвижными вершинами.Обозначим через (, ) — совокупность геометрических деревьев с граничными вершинами и подвижными вершинами, а через (, )— количество деревьев в этой совокупности.Заметим, что количество подвижных вершин (число ) в геометрическом дереве с граничными вершинами может меняться от 1 до − 2.При = − 2 все подвижные вершины имеют степень 3.

Напомним,что геометрические деревья, все подвижные вершины которых имеютстепень 3, являются бинарными деревьями.Сети в метрических пространствах40Сведение исходной задачи к перечислению помеченных деревьевТакже напомним, что все граничные вершины геометрических деревьев из класса (, ) помечены различными числами из множества{1, . . . , }, а подвижные вершины геометрических деревьев не помечены.Рассмотрим теперь вспомогательный класс деревьев без вершин степени 2, с вершинами степени 1, помеченными различными числами измножества {1, . .

. , }, и с остальными вершинами, помеченными различными числами из множества { + 1, . . . , + }. Вершины степени 1этих деревьев мы также будем называть граничными, а остальные вершины — подвижными. Обозначим совокупность таких вспомогательных˜ ), а через (,˜ ) — количество деревьев в этой содеревьев через (,вокупности.Лемма 1.5 Имеет место равенство(, ) =1 ˜(, ).!˜ ) на классы экДоказательство.

Разобьем множество деревьев (,˜1 и ˜ 2 из (,˜ ) будемвивалентности следующим образом. Два дерева считать эквивалентными, если после стирания пометок на подвижныхвершинах этих деревьев получится одно и то же дерево из (, ).Таким образом, можно сказать, что введенные только что классы эквивалентности — это деревья из (, ).

Теперь докажем, что количествоэлементов в каждом классе равно !. Отсюда уже следует утверждениелеммы.В самом деле, любое дерево из класса, соответствующего дереву ∈ (, ), получается из дерева некоторой пометкой подвижныхвершин дерева элементами из множества { + 1, . . . , + }. Количество таких различных пометок равно !. Осталось показать, что дверазличные пометки дерева приведут к двум неизоморфным деревьям˜1 и ˜ 2 из (,˜ ).˜1 и ˜ 2 изоморфны, то пометки дереваДокажем, что если деревья ˜1 и ˜ 2 . Изоморфизм совпадают. Пусть — изоморфизм между является некоторым автоморфизмом дерева , если мы покажем, чтоон тождественный, то отсюда будет следовать совпадение пометок.

Очевидно, что тождественен на граничных вершинах дерева , посколькуСети в метрических пространствах41пометку граничных вершин мы не меняли. Но автоморфизм любого дерева, тождественный на граничных вершинах, будет тождественным навсем дереве (это можно показать последовательным отрезанием усов, см.лемму об усах 1.2). Таким образом исходная задача вычисления чисел (, ) свелась к˜ ).вычислению чисел (,Представление ПрюфераДалее нам понадобится взаимно однозначное соответствие, полученноеПрюфером в [33], между помеченными деревьями порядка (помеченным деревом порядка называется дерево с вершинами, которые помечены различными числами от 1 до ) и наборами из − 2 элементов1 , 2 , .

. . , −2 , где каждое является целым числом от 1 до , причем в наборе допускаются повторения. Следуя [20], напомним построениеэтого соответствия. В заданном помеченном дереве возьмем висячуювершину (т.е. вершину степени 1), имеющую наименьшую пометку, ивыберем пометку 1 вершины, смежной с . Далее, проделав такой жешаг для дерева − , находим пометку 2 (дерево − получено издерева удалением вершины и ребра, инцидентного вершине ).

Этотпроцесс оборвется, когда останутся только две смежные вершины. Таким образом по каждому помеченному дереву порядка однозначностроится слово длины − 2 в алфавите {1, . . . , }.Опишем теперь обратную процедуру, позволяющую однозначным образом строить по каждому набору (1 , 2 , . . . , −2 ) помеченное дерево.Обозначим через 1 наименьшее целое положительное число, не встречающееся в наборе (1 , 2 , . . . , −2 ), и пусть (2 , .

. . , −2 ) обозначает набор длины − 3, получающийся из набора (1 , 2 , . . . , −2 ) уменьшением всех его координат, больших, чем 1 на 1. Тогда набор (2 , . . . , −2 )состоит из чисел, принадлежащих множеству {1, . . . , − 1}, и мы можем предположить, что существует соответствующее дерево порядка − 1. Изменим распределение пометок у вершин дерева , прибавляя1 к каждой пометке, превосходящей 1 − 1. Затем введем -ю вершинус пометкой 1 и соединим с вершиной, помеченной числом 1 в дереве .Таким образом, получили единственное помеченное дерево, соответствующее данному набору длины − 2.Из описанного выше построения взаимно однозначного соответствиялегко следует леммаСети в метрических пространствах42Лемма 1.6 В слово, отвечающее помеченному дереву , входят лишьпометки невисячих вершин, причем с кратностями, равными степенисоответствующей невисячей вершины минус 1.Перечисление бинарных деревьев˜ — некоторое дерево из совокупности (,˜ ).

Обозначим чеПусть рез , = 1, . . . , , степени его подвижных вершин. Каждому дереву˜ ), согласно представлению Прюфера и лемме 1.6, соответствуетиз (,слово длины + − 2 = (1 − 1) + · · · + ( − 1), в которое пометка + входит ровно − 1 ≥ 2 раз. И обратно, любое такое слово соответствует˜ ). Количество слов описанного вида (а знанекоторому дереву из (,˜ )) выражается с помощьючит и число деревьев в совокупности (,формулы∑︁( + − 2)!˜ ) =(,1 ! · · · · · !1 +···+ =+−2 ≥2Следовательно,(, ) =1!( + − 2)!1 ! · · · · · !∑︁(1.1)1 +···+ =+−2 ≥2При = − 2 все обязаны равняться 2, поэтому сумма в формуле. Таким образом, получаем утвер(1.1) состоит из одного члена (2(−2))!2−2ждениеУтверждение 1.2 Количество бинарных деревьев с помеченнымиграничными вершинами равно(, − 2) =12−2·(2( − 2))!.( − 2)!Числа Стирлинга 2-ого родаЗаметим, что формула (1.1) перечисляет количество способов разбить( + − 2)-множество на подмножеств мощности не менее 2.Сети в метрических пространствах43Определение.