Деревья в программировании
Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Таким образом, компонентами связности леса являются деревья.
Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и программировании. Дерево (ориентированное) и иерархия - это равнообъемные понятия.
Ориентированным деревом (или ор деревом, или корневым деревом) называется орграф со следующими свойствами.
1. Существует единственный узел г, полу-степень захода которого равна 0, d+(r) =0. Он называется корнем дерева.
2. Полу-степень захода всех остальных узлов равна 1,
{r}d+(v)=1
3. Каждый узел достижим из корня
Множества Т1,...,Тk в эквивалентном определении ор дерева являются поддеревьями. Если относительный порядок поддеревьев Т1,...,Тk фиксирован, то ор дерево называется упорядоченным.
Бинарное (или двоичное) дерево - это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев - левого и правого. Бинарное дерево не является упорядоченным ор деревом.
Следующая теорема перечисляет некоторые основные свойства деревьев.
Теорема. Пусть граф G(V, Е) имеет n вершин. Тогда следующие утверждения эквиваленты.
1) G является деревом;
2)G не содержит циклов и имеет n -1 ребер;
3) G связен и имеет n -1 ребер;
4)G связен, но удаление любого ребра нарушает связность;
5) любые две вершины графа G соединены ровно одним путем;
6)G не имеет циклов, но добавление любого ребра порождает ровно один цикл.
При n = 1 утверждение очевидно, поэтому считаем
1) => 2). По определению G не имеет циклов. Рассмотрим некоторое ребро l = ( , ) и удалим его. Получим граф G'. В графе G' нет пути из в т.к. если бы такой путь был, то в графе G был бы цикл. Значит G' не связен и не имеет циклов. Значит, он состоит из двух компонент, являющихся деревьями с числом вершин и соответственно ( + = n). По индуктивному предположению G' имеет -1 + -1 ребер. Следовательно, граф G имеет n -1 ребер.
2)=> 3). Если бы G был несвязен, то каждая его компонента представляла бы собой связный граф без циклов. Из предыдущего имеем, что число ребер в каждой компоненте меньше на одно число j ее вершин. Значит, общее число ребер меньше числа вершин по крайней мере на два, что противоречит тому, что G имеет n -1 ребер.
3)=> 4). Удаление любого ребра приводит к графу с n вершинами и n-2 ребрами, который не может быть связным.
4)=> 5). В силу связности G, каждая пара вершин соединена путем. Если бы данная пара была соединена более, чем одним путем, то они образовывали бы цикл. Но тогда удаление любого ребра в цикле не нарушает связности графа.
5)=> 6). Если бы G содержал цикл, то любые две вершины на цикле соединялись бы, по крайней мере, двумя путями. Добавим теперь к графу G ребро l = ( , ). Тогда образуется цикл, т.к. вершины и уже соединены путем. Ясно, что цикл единственный.
6) => 1). Если бы G был несвязен, то добавление ребер, соединяющих вершины из разных компонент, не приводит к образованию цикла.
Следствие. Дерево с более чем одной вершиной имеет, по крайней мере, две вершины степени 1.
Действительно, пусть v1,…,vn - множество вершин, тогда имеем
В силу связности , отсюда и следует утверждение.
2. Для графа G(V, Е) определим два полезные понятия.
Вершинный подграф G(V', E') - это граф на множестве вершин ребрами такими, что оба конца ребра принадлежат V.
Реберный подграф G(V, E') - это граф, определяемый подмножеством ребер множеством вершин , состоящим из концевых вершин ребер из Е'. Остовым (покрывающим) деревом графа G(V, Е) называется его реберный подграф с множеством вершин V, являющийся деревом.
Факт 2. Граф G(V, Е) имеет остовое дерево тогда и только тогда, когда он связен.
Предложим процедуру построения остового дерева. Ясно, что если граф G не связен, то он не может иметь остового дерева.
Пусть граф связен. Если в графе нет ребра, удаление которого сохраняет связность графа, то G - дерево.
Если такое ребро есть, удалим его и. продолжим процедуру. Когда процедура не может быть продолжена, полученный граф является деревом.
Рассмотрим теперь известную проблему нахождения минимального остового дерева. Пусть G(V, Е) неориентированный граф и пусть каждому ребру е из Е поставлено в соответствие положительное число l (е), называемое его весом. Требуется найти связный реберный подграф G'(V', E'), такой, что V' = V, причем сумма минимальна.
Ясно, что граф G(V, Е') должен быть деревом. Действительно, если G(V', Е') содержит цикл, то тогда любое ребро цикла можно удалить из графа и тем самым уменьшить суммарный вес ребер графа G(V', Е').
Рассмотрим следующее представление свободного дерева, известное как код Прюфера. Допустим, что вершины дерева T(V,E) занумерованы числами из интервала 1...р. Построим последовательность A: array[1 ...р-1] of 1...р в соответствии с алгоритмом pac1.
Алгоритм 1. Построение кода Прюфера свободного дерева.
Вход: Дерево T(V,E) в любом представлении, вершины дерева занумерованы числами 1...р произвольным образом.
Выход: массив A: array[1 ...р-1] of 1 ...р - код Прюфера
дерева Т.
For I from 1 to р-1 do
v:=min {k V\ d(k)=1}{выбираем вершину v - висячую вершину с наименьшим номером}
A[i]:=Г(v) {заносим в код номер единственной вершины, смежной с v}
V:=V-v {удаляем вершину v из дерева}
End for.
По построенному коду можно восстановить исходное дерево с помощью алгоритма 2.
Алгоритм 2. Распаковки кода Прюфера свободного дерева.
Вход: массив A.array [1...р-1] of 1...р - код Прюфера дерева Т.
Выход: Дерево T(V,E) заданное множество ребер Е, вершины дерева занумерованы числами 1 ...р.
Е:= 0{в начале множество рёбер пусто}
В:=1 ...р {множество неиспользованных номеров вершин}
For i from 1 to p-1 do
v:=min {k Е В/ j>i k=A[j]} {выбираем вершину v -неиспользованную вершину с наименьшим номером, который не встречается в остатке кода Прюфера}
E:=E+(v, A[i]) {добавляем ребро (v,A[i])}
B:=B-v {удаляем вершину v из списка неиспользованных}
End for.
Построение кода Прюфера.
Для дерева, представленного на рисунке, код Прюфера
7,9,1,7,2,2,7,1,2,5,12
