Теорема Кэли о количестве деревьев на n вершинах. Коды Прюфера

Теорема (Кэли). Имеется ровно n^(n−2) деревьев с множеством вершин V = {1, 2,..., n}.

Определение. Рассмотрим следующую процедуру для дерева G = (V, E):

1. G1 = G.

2. Пусть дано дерево Gi = (Vi, Ei), Выберем наименьшую вершину Ai ∈ Vi степени 1.

Пусть a ∈ Ei — единственное ребро, соединяющее Ai с некоторой вершиной Bi. Определяем дерево

Последовательность B1, B2,... Bn−2 называется кодом Прюфера дерева G.

Теорема. (Кэли). Каждая последовательность B1, B2,..., Bn−2, где Bi = 1..n, является кодом

Прюфера в точности одного дерева с вершинами {1,..., n}.

Доказательство. Если c является кодом Прюфера некоторого дерева G с вершинами {1... n}, то дерево состоит из ребер {Ai, Bi}, i = 1..n − 1, где

1. A1 — наименьшее число, отличное от B1, B2,..., Bn−2;

2. Ai, i = 2..n − 2, — наименьшее число, отличное от A1,... Ai−1, Bi,..., Bn−2;

3. An−1 — наименьшее число, отличное от A1,... An−2;

4. Bn−1 — наименьшее число, отличное от A1,... An−1.