Теорема Кэли о числе помеченных деревьев с р вершинами


Дерево есть связный подграф без циклов.
Индукцией по числу вершин можно показать, что (p,q) дерево имеет q = p-1 рёбер.
Теорема Кэли: Число помеченных деревьев (tp) с p вершинами равно: рр-2, то есть tp = pp-2.

Доказательство Прюфера: Пусть Т – помеченное дерево с р вершинами. V = {1,2,…,p}. Сопоставим дереву Т единственный набор (а1,… ,ар-2) из Vp-2 следующим образом: выберем в Т висячую вершину v с наименьшей пометкой а1. Аналогично найдём наименьшую пометку а2 для висячей вершины в дереве Т-v (Т без v и без принадлежащих v ребер). И так далее… Остается одно ребро из Т. Набор А=(а1,…,ар-2) построен для дерева Т. Так как каждое ai было единственно, то набор а единственный. Так как каждое помеченное дерево с р вершинами связано с единственным набором длины (р-2) из р элементов и так как число таких наборов равно рр-2, то число помеченных деревьев tp ≤ pp-2. Продолжим Доказательство теоремы следующим утверждением.

Утверждение: Каждому набору длины (р-2) из 1,2,…,р можно единственным образом сопоставить помеченное дерево с р вершинами 1,2,…,р

Доказательство: Индукция по р.
Базис: р=2. V = {1,2}. pp-2 = 22-2 = 20 = 1. Набор а пуст. Для пустого набора существует только одно помеченное дерево.
Предположение индукции: предположим, что каждому набору длины (р-3) из 1,2,….,р-1 можно единственным образом сопоставить помеченное дерево с (р-1) вершинами 1,2,…,р-1.
Шаг: Пусть а={а1,а2,…,а(p-2)} длины (р-2) составлен из элементов 1,2,…,р. Пусть b1 есть наименьшее натуральное число не из набора a и пусть с={c2,…,cp-2} есть набор длины (р-3), полученный из а уменьшением всех его координат, больших чем b1, на единицу, тогда набор с состоит из чисел, принадлежащих множеству VP-1={1,2,…,p-1}. Так как набор с состоит из (р-3) элементов, то по предположению индукции набору с соответствует единственное помеченное дерево Тр-1 с (р-1) вершинами из Vp-1. Прибавим в дерево Тр-1 по единице к каждой пометке вершины, превосходящей (b1-1), затем введём вершину р с пометкой b1 и соединим её с вершиной, помеченной числом а1 в дереве Тр-1. Однозначно получено дерево с р вершинами, соответствующее набору а. чтд.

Продолжим доказательство теоремы Кэли. Так как каждому из рр-2 наборов длины (р-2) однозначно соответствует помеченное дерево с р вершинами, то tp ≥ pp-2. Получили: tp ≤ pp-2 и tp ≥ pp-2, следовательно tp = pp-2. чтд.


Комментарии запрещены.




Статистика