Cтраница 4
Структура вложенных друг в друга однородных объектов, изоморфная корневому дереву. [46]
Наиболее естественным внутренним представлением формулы для решения этой задачи является корневое дерево. Предположим, что исходную формулу удалось представить в виде корневого дерева с корнем F. [47]
Это следует из двух фактов: ( 1) первый член последовательности, соответствующей корневому дереву, больше всех остальных членов; 2) последовательности, соответствующие факторам Т, располагаются в S в порядке возрастания их рангов. [48]
Если в полученном определении ориентацию всех ребер поменять на противоположную, то получим также определение корневого дерева. [49]
Доказать, что число висячих вершин не превосходит п / 2, где п - число вершин корневого дерева. [50]
Это соответствие для п 4 проиллюстрировано на рис. 3.1.2. Более подробно: пусть дана некоторая совокупность из п корневых деревьев; новое корневое дерево строится путем добавления одной новой вершины и установления смежности этой вершины с каждым из корней п первоначальных корневых деревьев. Ясно, что все деревья, у которых корни имеют степень п, могут быть построены указанным способом. [51]
Это соответствие для п - 4 проиллюстрировано на рис. 3.1.2. Более подробно: пусть дана некоторая совокупность из п корневых деревьев; новое корневое дерево строится путем добавления одной новой вершины и установления смежности этой вершины с каждым из корней п первоначальных корневых деревьев. Ясно, что все деревья, у которых корни имеют степень п, могут быть построены указанным способом. Чтобы найти число таких деревьев, рассмотрим степенную группу ESn с множеством объектов Yx, где Е - единичная группа, X 1, , п и Y - множество всех корневых деревьев. Тогда каждая функция из Yx соответствует некоторому упорядоченному набору, состоящему из п корневых деревьев. [52]
Процесс рождения или стационарный ветвящийся процесс, ( называемый также процессом размножения) можно представить деревом, растущим из некоторого корня ( корневым деревом), и рассмотреть ряд задач для этого прадерева. Рождение частиц происходит взаимно независимо, и все частицы имеют одно и то же распределение вероятностей для числа рождаемых частиц. [53]
В дереве любой узел с входной степенью 0 называется корнем, и если K - / Q fT, то Т называется К - корневым деревом. [54]
Заметим, что вес каждой орбиты, который является весом и любой функции, содержащейся в этой орбите, ровно на единицу меныдз общего числа вершин в корневом дереве, сопоставленном орбите. Умножение ряда Z ( Sn, Т ( х)) на х подправляет веса так, что коэффициент при xf в x - Z ( Sn, Т ( х)) равен числу этих деревьев с р вершинами. [55]
Заметим, что вес каждой орбиты, который является весом и любой функции, содержащейся в этой орбите, ровно на единицу меньше общего числа вершин в корневом дереве, сопоставленном орбите. Умножение ряда Z ( Sn, Т ( х)) на х подправляет веса так, что коэффициент при & в x - Z ( Sn, Т ( х)) равен числу этих деревьев с р вершинами. [56]
Следовательно, при нечетном числе точек никакое дерево не окажется бицентроидальным, а при четном числе точек, скажем 2т, каждое из двух деревьев, составляющих заданное дерево, может рассматриваться как корневое дерево из т точек. [57]
Числа таких деревьев с различными точками немедленно находятся на основании следующих замечаний: ( 1) п - 1 линий ( в деревьях с п точками) могут быть ориентированы 2й 1 способами; ( 2) все эти ориентации дерева или корневого дерева с различными точками различны. [58]