logo
РГР_ПО_ДИСКРЕТКЕ

1.8. Деревья

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

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

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

Некоторые из определений приведены в следующей теореме (они же являются свойствами деревьев):

Теорема: Для графа G с N вершинами и R рёбрами следующие утверждения эквивалентны:

  1. G-дерево;

  2. G-связный граф, R=N-1;

  3. G-ациклический граф, R=N-1;

  4. любые две несовпадающие вершины графа G соединяет единственная простая цепь;

  5. G-ациклический граф, такой, что, если какую-либо пару его несмежных вершин соединить ребром, то граф будет содержать ровно один цикл.

Примеры деревьев приведены на рис. 1.31.

Рис 1.31

Рис 1.32

Рис. 1.33

Дерево, имеющее N вершин, всегда содержит R=N-1 ребро, то есть минимальное количество рёбер для того, чтобы граф был связным. Если из дерева удалить хотя бы одно ребро, то граф становится несвязным, он распадается на компоненты, которые могут быть также деревьями или отдельными вершинами. При добавлении в дерево ребра образуется цикл.

Несвязный граф, компонентами которого являются деревья, называется лесом. На рис. 1.32 показано образование цикла (а) и разложение дерева на компоненты (б).

Среди различных деревьев особо выделяют последовательное дерево, представляющее простую цепь ( рис. 1.33а), и звёздное дерево, в котором одна из вершин – центр, смежная со всеми остальными вершинами (рис. 1.33б).

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

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

Число рёбер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно (G)=R-N+K, где K –число компонент связности G.

Число (G)=R-N+K называется цикломатическим числом графа G. (G) определяет меру связности графа.

Для леса =0, для связного дерева (H)=0, так как R=N-1, K=1 (=N-1-N+1). Граф имеет единственный цикл тогда и только тогда, когда (G)=1. Любой граф, в котором число рёбер не меньше, чем число вершин, содержит цикл. Естественно возникает вопрос: как много остовов в графе? Для полного графа число остовов равно NN-2. (N-число вершин ).

Теорема Кирхгофа (1847г.) Число остовов в связном графе G порядка N2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа B(G) = I*IT.

Рис. 1.34

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

Рис. 1.35

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

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

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