Деревья имеют многочисленные применения в анализе иерархических систем.

Так, например, можно представить граф на рис. 2.8 как структуру города (А₀ – город в целом, A₁, А₂, A₃ – функциональные зоны, А₁₂ , А₁₃ , и т.д. – планировочные элементы).

Применение деревьев облегчает разработку и анализ системы, избавляет от необходимости держать в памяти много данных. В последние десятилетия компьютерная наука столкнулась с тем фактом, что деревья обеспечивают удобные структуры для хранения и исправления определённых типов данных – так называемых иерархических баз.

 

Циклический порядок графа.

Интересен вопрос о взаимодействии циклов и деревьев: каково наименьшее число рёбер, которые надо удалить из данного связного графа, чтобы на нём не осталось ни одного цикла?

Рис. 2.9

Можно доказать, что для того, чтобы в связном графе Г с N вершинами и M рёбрами не осталось ни одного цикла, из него надо удалить по меньшей мере   рёбер.  

Определение. Определённое таким образом число  называется циклическим порядком графа или цикломатическим числом графа Г. Оно равно увеличенной на 1 разности между числом рёбер и числом вершин графа.

Чтобы превратить граф на данном рисунке в дерево, надо из него удалить   ребра. Например, рёбра AC, AD, DE.

Рассмотрим произвольное дерево с N заданными и пронумерованными в произвольном порядке вершинами. Пусть, например, N=11. (Рис.2.10)

Рис. 2.10

Рис. 2.11

Но ведь те же 11 вершин можно соединить попарно 10 рёбрами и по другому, чтобы получилось какое-то новое дерево (см. рис.2.11). У этого нового дерева совпадает с предыдущим только 3 ребра. Спрашивается: сколько существует таких разных деревьев?

Английскому математику А.Кэлли (1875 г.) опыт, приобретённый в процессе непосредственного подсчёта числа деревьев, помог найти правильный ответ на этот вопрос. Деревьев с N пронумерованными вершинами существует N^N–2.  

 

Лекция 3. Неориентированные и ориентированные деревья

 

Теоретические основы

Определение. Полустепенью захода вершины называют число заходящих в нее дуг, а полустепенью исхода вершины — число исходящих из нее дуг. Степень вершины — это сумма полустепеней захода и исхода.

Определение. Неориентированным деревом называют связный, ациклический неориентированный граф.

 

Определение. Ориентированным деревом называют бесконтурный ориентированный граф, у которого полустепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0.

 

Опираясь на данное определение, можно доказать, что в ориентированном дереве любая вершина достижима из корня.

 

Определение. Вершину v ориентированного дерева называют потомком (подлинным потомком) вершины u , если существует путь из u в v(путь ненулевой длины из u в v ). В этом же случае вершину u называют предком (подлинным предком) вершины v , а если длина пути из u в v равна 1, то вершину vназывают сыном вершины u , которая при этом вполне естественно именуется отцом вершины v .

Вершину, не имеющую потомков, называют листом.

 

Рис. 3.1

 

 

На рис. вершины  A12, A13 есть сыновья вершины A1, которая, в свою очередь, является сыном вершины  A0— корня дерева. Вершины  A12, A13 являются подлинными потомками вершин A1 и A0, которые соответственно будут

их подлинными предками. Вершины A11,A12,A13,A21, A221,

 A222,A31, A32, A33 — листья дерева.

    Взаимно недостижимые вершины ориентированного дерева

 (например, такие, как A1 и A221) не являются ни предком, ни потомком

 одна другой.

 Каждая вершина будет сама для себя предком и потомком, но не подлинным.

Определение. Произвольный ациклический граф называют неориентированным лесом.  

Определение. Если каждая  компонента ориентированного графа является ориентированным деревом, то такой граф называют ориентированным лесом.

 

На рис. 3.2 дан пример неориентированного леса, а на рис. 3.3 — пример ориентированного леса.

 

Определение. Подграф неориентированного (ориентированного) дерева, являющийся неориентированным (ориентированным) деревом, называют поддеревом исходного дерева.

 

                    

Рис. 3.2                                               Рис. 3.3

Определение. Ориентированное дерево, у которого каждая вершина, отличная от корня, есть лист, называют кустом.

Рассмотрим теперь некоторые числовые параметры, которыми характеризуется ориентированное дерево.

Определение. Высота ориентированного дерева — это наибольшая длина пути из корня в лист; глубина d(v) вершины ориентированного дерева v — это длина пути из корня в эту вершину; высота h(v) вершины ориентированного дерева v — это наибольшая длина пути из данной вершины в лист и, наконец, уровень вершины  ориентированного дерева — это разность между высотой ориентированного дерева и глубиной данной вершины.

Уровень корня равен высоте ориентированного дерева, но уровни различных листьев, так же как и их глубины, могут быть различными; высота любого листа равна нулю.

Определение. Ориентированное дерево называют бинарным, если полустепень исхода любой его вершины не больше 2.

 Определение. Бинарное ориентированное дерево называют полным, если из любой его вершины, не являющейся листом, исходят ровно две дуги, а уровни всех листьев совпадают.

 

Бинарные деревья

Примеры различных бинарных ориентированных деревьев приведены на          рис.  3.4. На рисунке представлены неполные и полное ориентированное дерево.

Рис. 3.4

В полном бинарном ориентированном дереве высоты h ровно  2h листьев. Действительно, ориентированное дерево высоты 0  имеет  2⁰= 1 лист. Полное бинарное ориентированное дерево  высоты 1 имеет  2¹= 2 листа.

 

Пусть полное бинарное ориентированное дерево имеет  высоту k и соответственно 2^k листьев. Рассмотрим полное  бинарное ориентированное дерево высоты k+1

Поскольку в полном бинарном ориентированном дереве уровни всех листьев совпадают, легко видеть, что ориентированное дерево высоты k+1 можно получить из полного бинарного ориентированного дерева высоты k, если из каждого листа последнего провести по две дуги. Тогда количество листьев в ориентированном дереве высоты k+1будет в 2 раза больше, чем в ориентированном дереве высоты k.

Отсюда следует, что в произвольном бинарном дереве высоты h не более 2h

листьев. Таким образом, мы получаем следующий простой, но важный результат.

 

Теорема 3.1. Бинарное ориентированное дерево с n листьями имеет высоту, не меньшую log₂n.

Эта теорема имеет одно весьма интересное приложение. Предположим, что необходимо расположить строго по возрастанию элементы конечного линейно упорядоченного множества {a₁,…,a_n}.

Эту задачу называют задачей сортировки, а любой алгоритм, ее решающий, — алгоритмом сортировки. С математической точки зрения алгоритм сортировки должен найти такую перестановку {a_i1,…,a_in} элементов множества, которая была бы согласована с заданным на нем отношением ⩽ линейного порядка, т.е. для любых

k,  n из справедливости неравенства ik < in должно следовать a_ik ⩽ a_in.

Первоначально сортируемые элементы могут быть расположены в произвольном порядке, т.е. исходной может быть любая перестановка элементов сортируемого множества, и мы не имеем никакой априорной информации об этой перестановке. Единственный способ получить такую информацию — проводить попарные сравнения элементов ai (относительно рассматриваемого линейного порядка) в какой-либо последовательности. Заметим, что при этом совершенно не обязательно проводить все возможные сравнения, т.е. сравнивать a_i  с  a_j для всех  i ≠ j.

Все сравнения, которые в принципе могут быть проведены в процессе работы некоторого алгоритма, изображаются наглядно в виде ориентированного дерева, называемого деревом решений. На рис. 3.5 приведено дерево решений для трехэлементного множества {х₁, х₂, х₃}.

 

 

Рис. 3.5

 

Множество листьев находится во взаимно однозначном соответствии с множеством всех перестановок исходного множества.

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

Следовательно, сортируя входную последовательность, алгоритм обязательно пройдет какой-то путь от корня дерева решений к одному из листьев, и, таким образом, число операций сравнения (число шагов алгоритма сортировки) будет величиной, пропорциональной высоте дерева решений, не меньшей чем log₂(n!) в силу изложенной выше теоремы. Дерево решений имеет высоту порядка n log₂n.

Таким образом, в общем случае задачу сортировки с помощью попарных сравнений нельзя решить быстрее, чем за указанное число шагов. Безусловно, конкретный путь в дереве решений из корня к одному из листов зависит от исходной перестановки. Например, в дереве решений, приведенном на рис. 3.5, есть два "коротких" пути длины 2, однако остальные пути имеют длину 3.

 

 

Остовной лес (дерево)

Определение. Остовным лесом (деревом) неориентированного (ориентированного) графа называют любой его остовный подграф, являющийся лесом (деревом).

Теорема 3.2. У всякого неориентированного графа существует максимальный остовный лес.

Поскольку неориентированный лес — это произвольный ациклический граф, то достаточно показать, что всякий неориентированный граф содержит максимальный остовный ациклический подграф.

Рассмотрим произвольный неориентированный граф G0 = (V,E).

Если он ациклический, то утверждение очевидно. В противном случае в нем есть хотя бы один цикл. Выберем один из циклов графа и обозначим его C1. Удалим из цикла C1 какое-нибудь ребро. Обозначим его e1. Так как цикл — это простая цепь, то удаление ребра в\ приводит к подграфу G1 = (V,E∖{e1}) графа G0, в котором будет по крайней мере одним циклом меньше, чем в графе G0.

 В то же время любые две вершины, соединенные цепью в исходном графе, будут соединены цепью и в подграфе G1. Если граф G1 ациклический, то он и будет искомым максимальным остовным лесом исходного графа, так как возвращение удаленного ребра e1приведет к появлению цикла. Если же граф  G1 имеет циклы, то поступим с ним точно так же, как с графом G0 , a именно, выбрав какой-нибудь его цикл C2, удалим из него одно ребро — обозначим его e2.

 В силу конечности множеств ребер исходного графа через конечное число

n⩾1шагов, на каждом из которых удаляется ровно одно ребро некоторого цикла графа G, получим некоторый его ациклический подграф Gn = (V,T), где T = E∖{e1,…,en}, причем подграф Gn−1=(V,E∖{e1,…,en}) содержит цикл, проходящий по ребру en.

Покажем, что добавление к множеству ребер T хотя бы одного ребра из ранее удаленных, т.е. любого ребра из множества {e1,…,en}, приведет к появлению цикла.

Действительно, на каждом шаге описанной выше процедуры происходит удаление нового цикла графа G0, т.е. все циклы C₁, C₂,…, C_n попарно различны. Для каждого

 i = 1,…, nрассмотрим два случая:

1) цикл Ci содержит только одно из удаленных ребер, а именно ребро e_i;

2) цикл Ci содержит не менее двух удаленных ребер, т.е. вместе с ребром e_i он содержит по крайней мере еще одно ребро  e_j ∈ {e₁,…,e_n}.

Очевидно, что в первом случае добавление ребра ei к множеству ребер T приведет к появлению цикла, а именно цикла Ci.

 

Рис. 3.6

Рассмотрим второй случай. Для простоты будем считать, что есть только одно ребро e_j, отличное от ребра e_i, которое содержится в цикле Ci (случай нескольких таких ребер анализируется аналогично). Так как ребро ej содержится в некотором цикле Cj, отличном от Ci, то, добавляя ребро e_i к множеству ребер T, все равно получим цикл (рис. 3.6). Действительно, если ребро e_i не содержится в цикле Cj, то, как видно на рис. 3.6, концы ребра ei соединены цепью, не содержащей этого ребра. Тогда, согласно теореме 3.2, существует простая цепь (не содержащая ребра e_i), соединяющая его концы. Добавляя к ней ребро e_i, получим цикл. Если же ребро e_i

содержится в цикле Cj, то удаление этого ребра приведет к исчезновению вместе с циклом Ci и цикла Cj , что невозможно, так как Ci и Cj — циклы, удаляемые на разных шагах описанной выше процедуры (на самом деле можно показать, что в рассматриваемой ситуации ребро e_j, а вместе с ним и цикл Cj, удаляется позже ребра e_i). Таким образом, всегда найдется цепь, соединяющая концы ребра e_i (и не содержащая этого ребра). Следовательно, существует и цикл, содержащий ребро e_i

(но не содержащий ребра e_j).

 

Итак, добавляя к подграфу Gn = (V,T) произвольное ребро из множества {e1,…,en}, получим цикл. Следовательно, этот подграф и будет искомым максимальным остовным лесом графа G.

Утверждение теоремы сохраняет силу и для ориентированных графов.

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