Графы деревья. Лес

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

1) при удалении из связного графа циклического ребра граф остается связным;

2) при удалении ациклического ребра граф становится несвязным.

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

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

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

1) связный граф, который становится несвязным при удалении любого ребра;

2) связный граф, у которого число ребер на единицу меньше числа вершин;

3) граф, любые две вершины которого связаны единственной элементарной цепью;

4) граф без циклов, в котором после добавления ребра, связывающего две любые вершины, появляется цикл.

Выберем в дереве произвольную вершину α0 и назовем ее корнем, или вершиной нулевого яруса. Соседние вершины назовем вершинами первого яруса и т.д., вершины, соседние вершинам (i-1)-го яруса не отнесенные еще ни к одному ярусу, назовем вершинами i-го яруса. Каждая вершина дерева принадлежит ровно одному ярусу. Очевидно, что номер яруса совпадает с расстоянием между его вершинами и корнем дерева. В силу свойства (3) каждая вершина i-го яруса связана ребром ровно с одной вершиной (i-1)-го яруса и не связана ребром ни с какой вершиной i-го яруса.

Такое представление дерева часто является удобным. Оно показывает, в частности, что в конечном дереве всегда существуют концевые вершины (например, вершины последнего яруса, но, возможно, и другие).

Выделение корня в дереве Д определяет на множестве его вершин частичный порядок: α < β, если α ≠ β и элементарная цепь из корня в вершину β содержит α. Корень α0 является частично упорядоченном множестве вершин, а все концевые вершины (исключая корень: он может быть, но может и не быть концевой вершиной) – максимальными. Каждая вершина α однозначно определяет корневое поддерево Дα, натянутое на множество таких вершин β, что α ≤ β. В каждом таком поддереве Дα (в том числе в Дα0 = Д) можно выделить вершины, непосредственно подчиненные корню поддерева, т.е. такие вершины γ1, что α < γ, и не существует промежуточных вершин δi, для которых α < δi < γi. Для каждой такой вершины γi определяем ветвь Дα γ; дерева Дα как корневое поддерево с корнем α, натянутое на множество вершин {α} u {δ : δ ≥ γ}. Все поддерево Дα получается из своих ветвей склеиванием в корне α.

Каждую логическую формулу, т.е. формулу, выражающую булеву функцию, можно представить корневым деревом: корень соответствует внешней булевой операции, вершины 1-го яруса – функциям, подставляемым на место ее аргументов, и т.д. Концевыми вершинами являются независимые переменные и константы.

Пример. Формула (Х V ( ¬ Y + Z)) → (¬ X& (1 ~ Y)) изображаемая деревом.

Теорема. Дерево с n вершинами содержит n-1 ребро.

Доказательство. Проведем индукцией по n. При n=2 утверждение очевидно. Пусть дерево G содержит n вершин. Удалим из него какую-нибудь концевую вершину и инцидентное ей концевое ребро. Получим новое дерево, содержащее n-1 вершину и, по предположению индукции, n-2 ребра. Следовательно, исходное дерево содержит (n+2)-1 = n – 1 ребро.

Турнир по олимпийской системе (с выбыванием проигравшего) изображается корневым дихотомическим деревом: корень соответствует победителю.

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

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

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