Деревья

Определение 1. Дерево, имеющее 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].

Пусть Г – граф. Его поддеревом T называется подграф, который является деревом. В этом случае мы будем говорить так же, что T содержится в графе Г. Поддерево T графа Г называется максимальным, если оно не содержится ни в каком отличном от него поддереве T’ графа Г.

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

,

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

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

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

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

.

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

Поиск по сайту: