Деревья

Теория

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

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

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

Рис. 5.13. Ориентированный граф, не являющийся
ориентированным деревом

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

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

На рис. 5.14 вершины v4 и v5 есть сыновья вершины v2, которая, в свою очередь, является сыном вершины v0 — корня дерева. Вершины v4 и v5 являются подлинными потомками вершин v0 и v2, которые соответственно будут их подлинными предками. Вершины v1, v4, v5, v6, v9, v8 — листья дерева. Взаимно недостижимые вершины ориентированного дерева (например, такие, как v2 и v9) не являются ни предком, ни потомком одна другой. Каждая вершина будет сама для себя предком и потомком, но не подлинным.

Рис. 5.14. Деревья

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

На рис. 5.15, а даны примеры неориентированного леса, а на рис. 5.15, б — примеры орентированного леса.

Рис. 5.15. Неориентированный (а) и ориентированный (б) лес

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

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

На рис. 5.14 подграф, порожденный множеством вершин {v3, v6, v7, v8, v9, }, является поддеревом изображенного на рисунке ориентированного дерева.

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

На рис. 5.13 граф, изображенный слева, является кустом. Рассмотрим теперь некоторые числовые параметры, которыми характеризуется ориентированное дерево.

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

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

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

Примеры различных бинарных ориентированных деревьев приведены на рис. 5.16: ориентированные деревья на рис. 5.16,а и б неполные, а ориентированное дерево на рис. 5.16,в полное.

Рис. 5.16. Бинарные ориентированные деревья

Используя индукцию по высоте ориентированного дерева, можно показать, что в полном бинарном ориентированном дереве высоты h ровно 2h листьев. Действительно, ориентированное дерево высоты 0 имеет 20 = 1 лист. Полное бинарное ориентированное дерево высоты 1 имеет 21 = 2 листа.

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

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

Теорема 5.2 (теорема о высоте бинарного ориентированного дерева с заданным числом листьев). Бинарное ориентированное дерево с n листьями имеет высоту, не меньшую log2 n. #

Эта теорема имеет одно весьма интересное приложение. Предположим, что необходимо расположить строго по возрастанию элементы конечного линейно упорядоченного множества {a1, ...,an}. Эту задачу называют задачей сортировки, а любой алгоритм, ее решающий, — алгоритмом сортировки. С математической точки зрения алгоритм сортировки должен найти такую перестановку {ai1,...,ain} элементов множества, которая была бы согласована с заданным на нем отношением ≤ линейного порядка, т.е. для любых k, l из справедливости неравенства ik < il должно следовать aik ≤ ail.

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

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

Рис. 5.17. Дерево решений для
трехэлементного множества

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

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

Используя для оценки факториала при больших n формулу Стирлинга

получаем, что дерево решений имеет высоту порядка nlog2n.

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

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

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

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

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

Рассмотрим произвольный неориентированный граф G0 = = (V, Е). Если он ациклический, то утверждение очевидно. В противном случае в нем есть хотя бы один цикл. Выберем один из циклов графа и обозначим его С1. Удалим из цикла С1 какое-нибудь ребро. Обозначим его е1. Так как цикл — это простая цепь, то удаление ребра е1 приводит к подграфу G1 = (V, Е\{е1}) графа G0, в котором будет по крайней мере одним циклом меньше, чем в графе G0 В то же время любые две вершины, соединенные цепью в исходном графе, будут соединены цепью и в подграфе G1. Если граф G1 ациклический, то он и будет искомым максимальным остовным лесом исходного графа, так как возвращение удаленного ребра е1 приведет к появлению цикла. Если же граф G1 имеет циклы, то поступим с ним точно так же, как с графом G0, a именно, выбрав какой-нибудь его цикл С2, удалим из него одно ребро — обозначим его е2 В силу конечности множеств ребер исходного графа через конечное число n ≥ 1 шагов, на каждом из которых удаляется ровно одно ребро некоторого цикла графа G, получим некоторый его ациклический подграф Gn = (V, Т), где Т = Е \ {е1 ..., еn}, причем подграф Gn-1 = = (V, Е\{е1, ...,en-1}) содержит цикл, проходящий по ребру еn. Покажем, что добавление к множеству ребер Т хотя бы одного ребра из ранее удаленных, т.е. любого ребра из множества {e1,..., еn}, приведет к появлению цикла.

Действительно, на каждом шаге описанной выше процедуры происходит удаление нового цикла графа G0, т.е. все циклы С1 С2, ..., Сn попарно различны. Для каждого i = 1,n рассмотрим два случая: 1) цикл Ci содержит только одно из удаленных ребер, а именно ребро еi; 2) цикл Ci содержит не менее двух удаленных ребер, т.е. вместе с ребром еi он содержит по крайней мере еще одно ребро ej ∈ {e1,..., en}.

Очевидно, что в первом случае добавление ребра еi к множеству ребер Т приведет к появлению цикла, а именно цикла Сi. Рассмотрим второй случаи. Для простоты будем считать, что есть только одно ребро еj, отличное от ребра еi, которое содержится в цикле Сi (случай нескольких таких ребер анализируется аналогично). Так как ребро ej содержится в некотором цикле Cj, отличном от Сi, то, добавляя ребро еi к множеству ребер Т, все равно получим цикл (рис. 5.18). Действительно, если ребро еi не содержится в цикле Cj, то, как видно на рис. 5.18, концы ребра еi соединены цепью, не содержащей этого ребра. Тогда, согласно теореме 5.1, существует простая цепь (не содержащая ребра еi), соединяющая его концы. Добавляя к ней ребро еi, получим цикл. Если же ребро еi содержится в цикле Cj, то удаление этого ребра приведет к исчезновению вместе с циклом Сi и цикла Cj, что невозможно, так как Сi и Cj — циклы, удаляемые на разных шагах описанной выше процедуры (на самом деле можно показать, что в рассматриваемой ситуации ребро ej, а вместе с ним и цикл Cj, удаляется позже ребра еi). Таким образом, всегда найдется цепь, соединяющая концы ребра ei (и не содержащая этого ребра). Следовательно, существует и цикл, содержащий ребро еi (но не содержащий ребра ej).

Рис. 5.18. Цикл

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

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

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