INTUIT.ru::Интернет-Университет Информационных Технологий

Интернет-Университет Информационных Технологий

http://www.INTUIT.ru

Графы и их применение

11. Лекция: О деревьях
Представления деревьев. Представление с помощью матрицы смежности. Представление с помощью списков смежности. Представление с помощью списка ребер и кода Прюфера. Алгоритм построения кода Прюфера. Алгоритм раскодирования. Уровневые коды корневых деревьев. Перечисление и подсчет деревьев. Непомеченные деревья. Ориентированные деревья. Каркасы в неориентированном графе. Каркасы в ориентированных графах.

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

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

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

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

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

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

Пример.

Рис. 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} & {0} & {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}$

Рис. 11.2.

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

В этом представлении каждой вершине дерева сопоставляется список смежных вершин вида $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_{6}; \\ 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}).$

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

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

Пусть обозначает число вершин в , а — целочисленный вектор длины ;
;
Для от до цикл
$b=\min \{ k\in B: k \text{ --- номер висячей вершины}\}$ ;
— номер вершины, с которой смежна вершина с номером ;
$B=B-\{b\}$ ;
удалить из вершины с номером ;
возврат к .

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

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

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

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

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

Пусть состоит из вершин $\{v_{1},v_{2} \dts v_{n}\}$ , таких, что номер вершины $v_{i}$ равен , где — длина кода плюс 2;
;
Для от до цикл;
$b=\min \{ k\in B.k\ne A[j]$ для любого $j\ge i\}$ ;
В добавить ребро, соединяющее вершины с номерами и ;
$B=B-\{b\}$ ;
возврат .

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

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

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

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

Рис. 11.3.

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

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

Теорема (Скойнса) Число -раскрашенных деревьев с вершинами одного цвета и вершинами другого равно $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}$ представляет собой число корневых деревьев с вершинами.

Теорема (Пойа) Перечисляющий ряд корневых деревьев удовлетворяет соотношению

$T(x)=x\cdot \exp \left\{\suml_{k=1}^{\infty }T(x^{k} )/k \right\}\!.$ (*)

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

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

Пусть

$t(x)=\suml_{n=1}^{\infty }t_{n} x^{n}$

производящая функция для деревьев, так что $t_{n}$ есть число деревьев с

вершинами.

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

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

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

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

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

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

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

Пример. Для графа (рис.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) = \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}$ , равно . Соответствующие каркасы графа показаны на (рис.11. 4).

Рис. 11.3.

Рис. 11.4.

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

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

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

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

Пример. Для графа (см. рис.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|$

Используя их, убеждаемся сразу, исходя из первой строки матрицы —Ї‘tЧM\Ь„_6q,IqтШdДЌ:dкЂ ЎТЛ>K!iGRЙІ'€‘Ј‹О†lН=‚Щ8Ь»uџ Є•µХN.”ЈійоnMzэыKljЊ4ZF‚@ьв[LF’Єiе MќйЬc&®g¦а„°Дўљѕч?4н“к&аRdЮ‘л«oWы®±Љz^5Ћџѕ¤—йelYtЫ.¬vНђі¬F<‹="gMKґ P№Н¤°y гкXљ1Ґфб™І