Деревья

Связный неориентированный граф называется деревом, если он не имеет циклов.

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

Теорема 3.5. В дереве любые две вершины связаны единственным простым путем.

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

Наглядное представление для произвольного дерева T = <V, E> можно получить при помощи следующей конструкции.

Выберем произвольную вершину a₀ и будем рассматривать ее как корень дерева или вершину нулевого уровня.

U₀ = {a₀}.

От a₀ проведем все ребра к вершинам, находящимся на расстоянии 1 от вершины a₀. Вершины, смежные с a₀ составят множество вершин первого уровня:

.

От этих вершин первого уровня проведем все ребра к смежным с ними вершинам, находящимся на расстоянии 2 от a₀ , за исключением ребер, инцидентных вершинам первого уровня. Получим множество вершин второго уровня

.

Из вершины a_i⁽ⁿ⁾ находящейся на расстоянии n от a₀ , выходит одно ребро к единственной предшествующей вершине , а также некоторое семейство ребер к вершинам , находящимся на расстоянии n +1.

.

Ни для какой из этих вершин a⁽ⁿ⁾ не может быть ребер, соединяющих ее с вершинами с тем же или меньшим расстоянием, кроме { a^(n-1), a⁽ⁿ⁾}. Таким образом, дерево может быть представлено в следующей форме:

Будем называть вершину a дерева концевой, если (a) = 1.

Будем называть ребро концевым, если хотя бы одна инцидентная ему вершина является концевой.

Утверждение 3.6. Любое нетривиальное конечное дерево имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.

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

Утверждение 3.7. Каждое дерево с n вершинами имеет n-1 ребро.

Доказательство. Доказательство легко проводится индукцией по числу вершин. Для n =1 утверждение, очевидно, справедливо. Пусть n>1. Тогда в дереве существует концевая вершина v. Удаляя из дерева v и ребро (u, v), инцидентное v, получим дерево с n-1 вершиной, которое в силу индуктивного предположения имеет n-2 ребра. Следовательно, первоначальное дерево имеет n-2+1=n-1 ребро.

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

Пример. Пусть количество вершин n равно 4. Тогда на этом множестве вершин могут быть построены следующие различные деревья.

Первый класс таких деревьев составляют деревья следующего вида:

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

Второй класс деревьев имеет вид:

Центральная вершина может быть выбрана 4 способами, что дает 4 различных дерева в этом классе.

Других деревьев с 4 вершинами, отличных от указанных в первом и втором классах, нет. Таким образом, существует 16 деревьев, имеющих 4 фиксированные вершины. 

Обратимся теперь к общему результату.

Теорема 3.8. Число различных деревьев, которые можно построить на заданном множестве V, содержащем n вершин, равно

t_n = n^n-2.

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

V = {1,2, ... ,n} (3.1)

Для любого дерева T, определенного на V, введем некоторый символ, характеризующий его однозначно. В T существуют концевые вершины. Обозначим через b₁ первую концевую вершину в последовательности (3.1), а через e₁ = {a₁ , b₁} - соответствующее концевое ребро. Удалив из T ребро E₁ и вершину b₁, мы получим новое дерево T₁ . Для T₁ найдется первая в списке (3.1) концевая вершина b₂ с ребром e₂ = {a₂ , b₂ }. Эта редукция повторяется до тех пор, пока после удаления ребра e_n-2 = (a_n-2 , b_n-2) не останется единственное ребро e_n-1 = (a_n-1 , b_n-1), соединяющее две оставшиеся вершины.

Тогда список

(T) = [a₁ , a₂ , ... , a_n-2 ] (3.2)

однозначно определяются деревом T и двум различным деревьям T и T^, очевидно, соответствуют разные символы такого вида. Каждая вершина a_i появляется в (3.2) (a_i) - 1 раз.

Для ясности приведем несколько примеров деревьев и соответствующих им последовательностей (T).

Примеры.

1.

2.

3.



Наоборот, каждая последовательность (3.2) определяет дерево T с помощью обратного построения. Если дана последовательность (3.2), то находится первая вершина b в списке (3.1), которая не содержится в (3.2). Это определяет ребро e₁ = {a₁ , b₁}. Далее удаляем вершины a₁ из последовательности (3.2) и b₁ из списка (3.1) и продолжаем построение для оставшихся элементов.

Получающийся в результате построения граф является деревом, что может быть установлено, например, по индукции. После удаления e₁ последовательность (3.2) будет содержать n - 3 элемента. Если она соответствует дереву T₁ , то граф T, получаемый из него добавлением e₁ , также есть дерево, так как вершина b₁ не принадлежит T₁ .

B (3.2) каждая вершина может принимать все n возможных значений. Все они соответствуют различным деревьям, откуда и получается формула t_n = n^n-2. 