Компоненты связанности графа. Понятие дерева и остовного дерева.

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

Деревом называется связный граф без циклов.

Подграф G 1 = (V 1, E 1) графа G = (V, E), называется остовным деревом в

графе G = (V, E), если G 1 = (V 1, E 1) — дерево и V 1 = V.

Ориентированное (направленное) дерево — ацикличный орграф (%84"ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.)"[2]

Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:

• существует один корень дерева T

• остальные узлы (за исключением корня) распределены среди непересекающихся множеств T ₁,..., T_m, и каждое из множеств является деревом; деревья T ₁,..., T_m называются поддеревьями данного корня T

Число различных деревьев, которые можно построить на n нумерованных вершинах, равно

n^{n − 2} (Теорема %80"КэлиHYPERLINK "http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)"[3]).

Производящая функция

для числа T_n неизоморфных корневых деревьев с n вершинами удовлетворяет функциональному уравнению

.

Производящая функция

для числа t_n неизоморфных деревьев с n вершинами можно представить с помощью перечисляющего ряда для корневых деревьев:

При верна следующая асимптотика

t_n ∼ C α ⁿ / n ^{5 / 2}

где C и α определённые константы, C = 0,534948..., α = 2,95576....

Дерево можно кодировать наборами из нулей и единиц. Рассмотрим, например, укладку дерева на плоскости. Начиная с какой либо вершины, будем двигаться по ребрам дерева, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах дерева. Проходя по некоторому ребру, записываем 0 при движении по ребру в первый раз и 1 при движении по ребру второй раз (в обратном направлении). Если m — число рёбер дерева, то через 2 m шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из 0 и 1 (код дерева) длины 2 m позволяет однозначно восстанавливать не только само дерево D, но и его укладку на плоскости. Произвольному дереву соответствуют несколько таких кодов. В частности, из этого способа кодирования вытекает следующая грубая оценка на число деревьев с n вершинами:

Дата добавления: 2015-09-06