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

Cтраница 2

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

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

V /), где обязательно 3 k п, то сумма k строк матрицы А, соответствующих k ребрам этого цикла, будет строкой нулей; поэтому если G не является свободным деревом, то детерминант матрицы Л равен нулю. [19]

Как мы видели в предыдущем пункте, абстрактную блок-схему можно считать графом, если не принимать во внимание направление стрелок на его ребрах; было показано, что используемые в теории графов понятия, как-то цикл, свободное дерево и др., уместны также и при изучении блок-схем. [20]

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

Таким способом из каждого свободного дерева ввиду того, что его точки индивидуально различны, можно получить п различных посаженных деревьев. Обозначим через Ап число топологически различных посаженных деревьев с п индивидуально различными узлами. [22]

J Ориентированное дерево. [23]

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

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

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

Дерево с корнем ( единственным, rooted) - это дерево, в котором один узел назначен корнем ( root) дерева. В области компьютеров термин дерево обычно применяется к деревьям с корнем, а термин свободное дерево ( free tree) - к более общим структурам, описанным в предыдущем абзаце. В дереве с корнем любой узел является корнем поддерева, состоящего из него и расположенных под ним узлов. [27]

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

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

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