О деревьях

Представления деревьев

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

Представление с помощью матрицы смежности

Это представление является общим для всех видов графов; оно задает граф с точностью до изоморфизма, но вместе с тем данное представление неэкономично, так как ненулевыми являются для $$n$$ -вершинного дерева только $$2\times n-2$$ из $$n^{2}$$ элементов матрицы.

Задание графа матрицей смежности, размера $$n\times n$$, где $$n$$ — число вершин графа. $$A(i,j)=1$$, если вершины $$i$$ и $$j$$ смежные, в противном случае $$A(i,j)=0$$. $$A$$ — симметрическая матрица для неориентированного графа и несимметрическая для ориентированного.

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

Пример.

(рис 11.1) $$\begin{pmatrix}{0} {0} {0} {1} {0} {0} {0} {0} {0} \\ {0} {0} {0} {1} {0} {0} {0} {0} {0} \\ {0} {0} {0} {1} {0} {0} {0} {0} {0} \\ {1} {1} {1} {0} {1} {0} {0} {0} {0} \\ {0} {0} {0} {1} {0} {1} {1} {0} {0} \\ {0} {0} {0} {0} {1} {0} {0} {0} {0} \\ {0} {0} {0} {0} {1} {0} {0} {1} {1} \\ {0} {0} {0} {0} {0} {0} {1} {0} {0} \\ {0} {0} {0} {0} {0} {0} {1} {0} {0} \end{pmatrix}$$

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

В этом представлении каждой вершине дерева сопоставляется список смежных вершин вида $$v_{i_{1}},v_{i_{2}}\dts v_{i_{n}}$$.

Для дерева из предыдущего примера списки смежности имеют вид$$\begin{aligned} \begin{aligned} \,\,v_{4} : v_{1},v_{2},v_{3},v_{5};\\ v_{5} :v_{4},v_{6},v_{7}; \\ v_{7} :v_{5},v_{8},v_{9};\\ \end{aligned}\\ \left. \begin{aligned} v_{1} :v_{4}; \\ v_{2} :v_{4}; \\ v_{3} :v_{4}; \\ v_{6} :v_{5}; \\ v_{8} :v_{7}; \\ v_{9} :v_{7}; \end{aligned} \right\} \t{— необязательно} \end{aligned}$$

При машинной организации списки смежности могут быть связаны между собой разными способами, например, копируя структуру дерева.

Представление с помощью списка ребер и кода Прюфера

Дерево при этом способе задается перечислением пар $$(v_{i},v_{j})$$ или троек $$(v_{i},v_{j},u_{k})$$, если дополнительно нужна нумерация ребер. Характер связей в списке определяется исходя из условий задачи.

Для дерева, изображенного на (рис.11.1), имеем:

$$(v_{1},v_{4}),(v_{2},v_{4}),(v_{3},v_{4}),(v_{4},v_{5}), (v_{5},v_{6}),(v_{5},v_{7}),(v_{7},v_{8}),(v_{7},v_{9})$$.

Алгоритм построения кода Прюфера

Пусть $$T$$ — дерево с множеством вершин $$\{v_{1},v_{2} \dts v_{n}\}$$. Будем считать, что номер вершины $$v_{i}$$ равен $$i$$. Сопоставим дереву $$T$$ последовательность $$\{a_{1},a_{2} \dts a_{n-2}\}$$ по следующему правилу, представленному в виде функции: Функция кода Прюфера ( $$T$$: дерево) $$=$$

Пусть $$n$$ обозначает число вершин в $$T$$, а $$A$$ — целочисленный вектор длины $$n-2$$ ;

$$B=[1:n]$$ ;

Для $$i$$ от $$1$$ до $$n-1$$ цикл

$$b=\min \{ k\in B: k \text{ --- номер висячей вершины}\}$$ ;

$$a[i]$$ — номер вершины, с которой смежна вершина с номером $$b$$ ;

$$B=B-\{b\}$$ ;

удалить из $$T$$ вершины с номером $$b$$ ;

возврат $$A$$.

Пример. Для дерева $$T$$. код Прюфера имеет вид $$P_{2} (T)= [2,5,5,5,6,6,10,9,10,11,13,15,15,10,13,13,13]$$.

В случае корневого ордерева процедура получения кода Прюфера аналогична. Необходимо только на последнем месте указывать корневую вершину и при распаковке кода исключать номер этой вершины из множества $$B$$.

Алгоритм раскодирования

Распаковка кода Прюфера осуществляется следующей функцией:

Функция распаковки ( $$A$$: код) $$=$$

Пусть $$T$$ состоит из вершин $$\{v_{1},v_{2} \dts v_{n}\}$$, таких, что номер вершины $$v_{i}$$ равен $$i$$, где $$n$$ — длина кода $$A$$ плюс 2;

$$B=[1: n]$$ ;

Для $$i$$ от $$1$$ до $$n+1$$ цикл;

$$b=\min \{ k\in B.k\ne A[j]$$ для любого $$j\ge i\}$$ ;

В $$T$$ добавить ребро, соединяющее вершины с номерами $$b$$ и $$A[i]$$ ;

$$B=B-\{b\}$$ ;

возврат $$T$$.

Уровневые коды корневых деревьев

Пусть $$(T,z)$$ обозначает корневое дерево с лежащим в его основе свободным деревом $$T$$ и корнем $$z$$. Уровень вершины $$v$$ в $$(T,z)$$ — это расстояние от $$z$$ до $$v$$ плюс единица. Уровневый код (обозначение $$L(T,z)=[l_{1},l_{2} \dts l_{n}]$$ ) — это последовательность целых чисел, полученная выписыванием уровней вершин дерева $$(T,z)$$ в постфиксном порядке.

Уровневый код называется каноническим (обозначается $$L^{*}(T,z)$$ ), если он является наибольшим в лексикографическом упорядочении среди всех уровневых кодов, описывающих дерево.

Пример. Для дерева $$T$$, изображенного на (рис.11. 1), имеем $$L(T,z)=[3,3,2,4,4,3,2,2,1]$$ — обычный уровневый код, а канонический уровневый код $$L^{*}(T,z)) =[4,4,3,3,2,3,3,2,2,1]$$.

(рис 11.3)

Перечисление и подсчет деревьев

Теорема (Кэли) Число $$t_n$$ помеченных деревьев с $$n$$ вершинами равно $${t_n = n^{n-2}}$$.

Теорема (Скойнса) Число $$2$$ -раскрашенных деревьев с $$m$$ вершинами одного цвета и $$n$$ вершинами другого равно $$S_n = n^{m -1} m^{n -1}$$.

Теорема (Рида) Число помеченных гомеоморфно несводимых деревьев равно $$h_{n} =(n-2)!\suml_{k=2}^{n}(-1)^{n-k} \begin{pmatrix} {n} \\ {k} \end{pmatrix} \frac{k^{k-2}}{(k-2)!}$$.

Непомеченные деревья

Пусть $$T(x)=\suml_{n=1}^{\infty }T_{n} x^{n}$$ — производящая функция для корневых деревьев.

Таким образом, $$T_{n}$$ представляет собой число корневых деревьев с $$n$$ вершинами.

Теорема (Пойа) Перечисляющий ряд корневых деревьев удовлетворяет соотношению $$T(x)=x\cdot \exp \left\{\suml_{k=1}^{\infty }T(x^{k} )/k \right\}\!$$.

Из этой теоремы следует, что $$T(x)$$ однозначно определяется функциональным уравнением (*). Из данного уравнения выводится формула для $$T(x)$$. Данную зависимость получил Кэли: $$T(x)=x\cdot \prod\limits_{p=1}^{\infty }(1-x^{p} )^{-T} p$$.

Следующая рекурсивная функция для вычисления $$T(n)$$ принадлежит Оттеру.

Пусть$$t(x)=\suml_{n=1}^{\infty }t_{n} x^{n}$$ производящая функция для деревьев, так что $$t_{n}$$ есть число деревьев с $$n$$ вершинами.

Теорема (Оттера) Ряд $$t_n^{}$$, перечисляющий деревья, выражается через ряд $$T(x)$$ для корневых деревьев с помощью формулы $$t(x)=T(x){-}\frac{1}{2} \left(T^{2}(x){-}T(x^{2})\right)$$.

Ориентированные деревья

Пусть $$r(x)$$ и $$R(x)$$ — перечисляющие ряды для ориентированных и для корневых ориентированных деревьев, соответственно.\medskip

Теорема (Харари-Принса) Перечисляющие ряды $$r(x)$$ и $$R(x)$$ для ориентированных и для корневых ориентированных деревьев удовлетворяют соотношениям $$T(x)=x\cdot \left(\exp \left\{\suml_{k=1}^{\infty }R(x^{k} )/k \right\}\right)^{2}$$ и $$r(x)= R(x) - R^2(x)$$.

Каркасы в неориентированном графе

Число каркасов в неориентированном графе определяется с помощью следующей матричной теоремы о деревьях в графе. Пусть $$M(G)$$ обозначает матрицу, получаемую из матрицы $$A(G)$$, где $$A(G)$$ — матрица смежности графа $$G$$, с помощью подстановки в ней на место $$i$$ -го диагонального элемента числа $$\deg v_{i}$$.

Матричная теорема о деревьях для графов. Для всякого связного помеченного графа $$G$$ все алгебраические дополнения матрицы $$M(G)$$ равны друг другу и их общее значение представляет собой число каркасов графа $$G$$ .

Пример. Для графа $$G$$ (рис.11. 3) с матрицей смежности$$A(G) = \left|\!\left| \begin{matrix} 0 1 1 0\\ 1 0 1 0\\ 1 1 0 1\\ 0 0 1 0 \end{matrix} \right|\!\right|$$ матрица $$M(G)$$ имеет вид$$M(G) = \left|\!\left| \begin{matrix} \phantom{-}2 -1 -1 \phantom{-}0\\ -1 \phantom{-}2 -1 \phantom{-}0\\ -1 -1 \phantom{-}3 -1\\ \phantom{-}0 \phantom{-}0 -1 \phantom{-}1 \end{matrix} \right|\!\right|.$$

Алгебраическое дополнение, например, элемента $$a_{1,4}$$, равно $$3$$. Соответствующие каркасы графа $$G$$ показаны на (рис.11. 4).

(рис 11.4) (рис 11.3)

Интересен также следующий результат. Пусть $$G-n$$ -вершинный граф без петель и $$B_0$$ — его матрица инциденции с одной удаленной строкой (т.е. с $$n - 1$$ независимыми строками). Пусть $$B^t_0$$ — транспонированная матрица к $$B_0$$. Тогда определитель $$|B_0^{} B_0^t|$$ равен числу остовных деревьев графа $$G$$.

Каркасы в ориентированных графах

Число каркасов в ориентированном графе определяется с помощью аналогичной матричной теоремы о деревьях в орграфе. Пусть $$G$$ — орграф с матрицей смежности $$A(G)$$. Определим диагональную матрицу $$M_{\rm out}$$, у которой $$(i,i)$$ -й элемент равен полустепени исхода $${\rm deg}^+v_i$$ вершины $$v_i$$. Затем положим $$C_{\rm out}= M_{\rm out} - A(G)$$. Аналогично определяется матрица $$C_{\rm in} = M_{\rm in} - A(G)$$.

Матричная теорема о деревьях для орграфов. Все алгебраические дополнения $$i$$ -й строки матрицы $$C_{\rm out}$$ равны друг другу, и их общее значение есть число каркасов орграфа $$G$$, входящих в вершину $$v_i$$. Двойственным образом общее значение алгебраических дополнений $$i$$ -го столбца матрицы $$C_{\rm in}$$ равно числу каркасов, выходящих из вершины $$v_i$$ .

Пример. Для графа $$G$$ (см. рис.11.5) матрицы $$C_{\rm out}$$ и $$C_{\rm in}$$ имеют вид:$$C_{\rm out} = \left|\!\left| \begin{matrix} 2 -1 \phantom{-}0 \phantom{-}0 -1\\ \phantom{-}0 \phantom{-}2 -1 -1 \phantom{-}0\\ \phantom{-}0 \phantom{-}0 \phantom{-}1 -1 \phantom{-}0\\ \phantom{-}0 -1 -1 \phantom{-}0 -1\\ -1 \phantom{-}0 \phantom{-}0 \phantom{-}0 \phantom{-}1 \end{matrix} \right|\!\right|\qquad C_{\rm in} = \left|\!\left| \begin{matrix} \phantom{-}1 -1 \phantom{-}0 \phantom{-}0 -1\\ \phantom{-}0 \phantom{-}2 -1 -1 \phantom{-}0\\ \phantom{-}0 \phantom{-}0 \phantom{-}1 -1 \phantom{-}0\\ \phantom{-}0 -1 \phantom{-}0 \phantom{-}2 -1\\ -1 \phantom{-}0 \phantom{-}0 \phantom{-}0 \phantom{-}2 \end{matrix} \right|\!\right|$$

Используя их, убеждаемся сразу, исходя из первой строки матрицы $$C_{\rm out}$$ и из первого столбца матрицы $$C_{\rm in}$$, что орграф $$G$$ имеет в точности четыре каркаса, выходящих из вершины $$1$$, и два каркаса, входящих в эту вершину.

(рис 11.5)