Деревья

Дерево, имеющее n вершин, называется нумерованным, если каждой из его вершин присвоен индивидуальный номер kÎ{1, 2,××× ,n}.

Теорема 1. (Кэли) Число нумерованных графов с n вершинами равно n^n-2.

Доказательство.Сопоставим каждому нумерованному дереву последовательность n-2 чисел принадлежащих {1, 2,××× ,n}. Эта последовательность называется кодом Прюфера и строится следующим образом. В цикле находится висячая вершина с наименьшим номером. Номер вершины смежной с найденной записывается в последовательность. Цикл повторяется n-2 раза. Наоборот, по последовательности n чисел из {1, 2,××× ,n+2} можно построить нумерованное дерево с помощью следующих действий:

Выписываем множество B={1, 2, 3, ∙ ∙ ∙, n+2}. Устанавливаем начальное множество ребер дерева T= Æ. Далее выполняются действия:

for (i=1; i<n-1; i++)

{

b= min { kÎB: k¹a_j " j ≥ i} ;

добавить к T ребро {b,a_i} ;

B = B \ {b} ;

}

Число последовательностей из n-2 чисел принадлежащих множеству {1, 2, ∙ ∙ ∙, n} равно n^n-2, значит число нумерованных деревьев равно n^n-2.

Доказательство следующего утверждения можно найти в [3].

Теорема 2. Число максимальных поддеревьев связного графа равно абсолютной величине алгебраического дополнения произвольного элемента матрицы

,

где d_i – степени вершин графа G, A(G) =( a_{i j} ) – матрица смежности

Пример 1. Рассмотрим граф G, изображенный на рис. 4.4. Вычислим количество его максимальных поддеревьев.

Рис. 4.4. Простой граф

Найдем матрицу M(G).

Отсюда число максимальных поддеревьев равно |A₃₁| = 3.