Инструменты пользователя

Инструменты сайта


examination:diskretka:question18

Вопрос №18. Формула Кэли

доказательство взято с http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008

Теорема Кэли: Число tn различных деревьев, которые можно построить на n вершин равно n^(n-2).

Доказательство (метод Прюфера):

Кодирование Прюфера переводит помеченные деревья порядка n в последовательности чисел по следующему алгоритму:

  1. Выбирается лист с минимальным номером.
  2. Лист и инцидентное ребро удаляются из дерева, в последовательность Прюфера добавляется номер смежной вершины.
  3. Если в дереве больше двух вершин, то п. 1, иначе — выход.

Распаковка дерева осуществляется по следующему алгоритму: Обозначим A = [a1, a2, …, an-2] — последовательность Прюфера, N = [1, 2, …, n].

  1. Выберем минимальное число v из N, не содержащееся в A.
  2. Соединяем ребром вершину с номером v и вершину, соответствующую первому числу из A.
  3. Удаляем v из N, удаляем первое число из A.
  4. Если в A осталось два числа — соединяем ребром соответствующие вершины, иначе — п. 1.

Очевидно, кодирование Прюфера задаёт взаимно-однозначное соответствие между множеством помеченных деревьев порядка n и множеством числовых последовательностей, состоящих из n - 2 натуральных чисел из отрезка [1 .. n].

Версия с лекций.

Теорема:Число tn различных деревьев, которые можно построить на n вершин равно n^(n-2).

Метод Прюфера:

  1. Обозначим элементы n вершин данного дерева в некотором порядке числами 1,2…n(*)
  2. Установим соответствие со множеством всех деревьев и множеством векторов (n-2) c натуральными значениями компоненты от 1 до n
  3. Согласно 2 св-ву в t найдем 2 концевых вершины.
  4. Обозначим через В концевых вершин последовательность *(звездочка)?, А через E(a1,b1)
  5. Удалим из t- e1, сохранив в дереве а1, исключив b1
  6. Получим t1, для t1 последов * найдется первая по порядку концевая вершина v2
  7. Наконец после удаления e(n-2)

Очевидно, кодирование Прюфера задаёт взаимно-однозначное соответствие между множеством помеченных деревьев порядка n и множеством числовых последовательностей, состоящих из n - 2 натуральных чисел из отрезка [1 .. n].

examination/diskretka/question18.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)