Свободное дерево

Cтраница 1

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

Свободное дерево с двумя центроидами имеет четное число вершин, а высота каждого центроида равна п / 2 ( см. упр. [2]

Мы представляем свободное дерево в виде коллекции ребер. Если представлять свободное дерево неупорядоченным, упорядоченным или даже бинарным деревом, придется признать, что в общем случае существует множество различных способов представления каждого свободного дерева. [3]

Докажите, что свободное дерево с п вершинами и двумя центроидами состоит из двух свободных деревьев с nil вершинами, соединенных ребром. II обратно, если два свободных дерева, имеющих т вершин каждое, соединены ребром, мы получаем свободное дерево с 2т вершинами и двумя центроидами. Обобщая этот результат, найдите число различных / - арных деревьев, имеющих п узлов. [4]

Сколько существует различных способов представления свободного дерева, показанного на рис. 5.20, в форме упорядоченного дерева. [5]

В этом разделе под деревом нужно понимать свободное дерево с п точками. Два дерева будут рассматриваться как различные или одинаковые в зависимости от того, различны или одинаковы они топологически. [6]

Вставка точки pis. При вставке затронуты узлы. ( 11, 4, 1, 13, 12, 3, ( 2, 2, ( 0, 1, ( 5, 1, ( 10, 1, 13. [7]

Легко понять, что структура данных описывает некоторое свободное дерево на текущем множестве точек, которое называется деревом оболочки. [8]

Вершина дерева с минимальной высотой называется центроидом этого свободного дерева. [9]

Свободное дерево.| Два различных бинарных дерева, в которых узел А - исходный ( корень, а В - порожденный. [10]

В теории графов таким образом определенное дерево называется свободным деревом. Пример такой структуры показан на рис. 2.3. Очевидно, что этому определению соответствует более широкий класс древовидных структур, нежели нашему первоначальному определению дерева. [11]

Это сильное условие, из которого следует, что в свободном дереве имеется не больше чем два центроида, и если имеются два центроида, то они смежны ( см. упр. [12]

В тексте показано, как, помещая корень в нужную вершину, свободное дерево можно превратить в ориентированное дерево. Следовательно, если имеется ориентированное дерево с корнем R, то его можно сначала превратить в свободное дерево, убрав направления дуг, а затем, установив новые направления, получить ориентированное дерево с корнем в некоторой выбранной вершине. [13]

Опираясь на тот факт, что не больше чем одно поддерево вершины свободного дерева может содержать центроид, докажите, что в свободном дереве имеется не больше двух центроидов и если свободное дерево содержит два центроида, то они смежны. [14]

Покажите, что в случае от п детерминант матрицы Ай равен 0, если G не является свободным деревом, и равен 1, если G - свободное дерево. [15]

Страницы: 1 2 3