Читайте также:
|
|
Деревом называется связный граф, не имеющий циклов. Известно, что всякое нетривиальное дерево имеет не менее двух висящих вершин (вершины степени 1). Это Следует из того, что если T – дерево с p вершинами и q ребрами, то
q=p-1.
Теорема. (Кэли 1897). Число tp помеченных деревьев порядка p равно
tp=pp-2.
Доказательство.
Первый подход (Кэли) Установим соответствие между помеченными деревьями и функциями, отображающими множество из p-2 объектов в множество из p объектов. Например, если p=5, то существует 53 функций из {a,b,c} в {v1, v2, v3, v4, v5}. Эти функции перечисляются многочленом
(v1+ v2+ v3+ v4+ v5)3. (16)
Слагаемые этого многочлена сопоставляются функциям естественным образом. Например, соответствует постоянной функции f(x)=v4, слагаемое отвечает трем функциям, которые отображают только один элемент в v1, два других – в v3, 6v2v3v5 дает шесть функций, отображающих по одному элементу в v2, v3 и v5. Теперь, умножая многочлен на v1v2v3v4v5 и получая
(v1+ v2+ v3+ v4+ v5)3 v1v2v3v4v5 (17)
устанавливаем тем самым соответствие между слагаемыми из этого произведения и помеченными деревьями порядка 5. Это соответствие с использованием слагаемого = v1v2v3v4v5) выглядит так
Заметим, что в деревьях, соответствующих слагаемому , степень вершины, помеченной числом k, равна показателю степени у vk. Справедливость этого высказывания может быть установлена и в общем случае. Следовательно, число помеченных деревьев, у которых вершины, помеченные числом k, имеют степень dk, равно полиномиальному коэффициенту
. (18)
Кэли проиллюстрировал это соответствие для p=6 и не стал рассатривать другие случаи, заметив: “Сразу видно, что доказательство, данное для этого частного случая, применимо при любом значении p”.
Второй подход (Прюфер 1917). Пусть дерево с n вершинами, помеченными числами 1, …,n. Свяжем с этим деревом последовательность натуральных чисел i1,…,in-2, построенную следующим образом:
1)положим j=0;
2)повторим следующий процесс n-2 раза:
увеличим значение j на единицу; найдем в дереве лист, помеченный натуральным числом с наименьшим значением. Пусть это значение kj, и пусть отцом листа kj является вершина, помеченная числом ij. Выберем значение ij в качестве j-ого элемента последовательности. Удалим в дереве ребро (ij,kj).
После исполнения этого алгоритма начальное дерево преобразуется в дерево, состоящее из одного ребра либо (in-2,n), либо, в случае in-2=n, – из ребра (n,n-1).
Дата добавления: 2015-09-11; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав |