Формула Кэли

Полный список всех деревьев на 2,3,4 помеченных вершинах: дерево с 2 вершинами, деревья с 3 вершинами и деревья с 4 вершинами. ${\ displaystyle 2 ^ {2-2} = 1}$${\ displaystyle 3 ^ {3-2} = 3}$${\ displaystyle 4 ^ {4-2} = 16}$

В математике, формула Кэлей является результатом в теории графов именем Кэлей. В нем указано, что для каждого положительного целого числа деревьев на помеченных вершинах равно. ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ Displaystyle п ^ {п-2}}$

Формула эквивалентно, подсчитывает число остовных деревьев из более полного графа с помеченными вершинами (последовательность A000272 в OEIS ).

• 1 Доказательство
• 2 История
• 3 Другая недвижимость
  • 3.1 Обобщения
• 4 ссылки

Известно множество доказательств формулы дерева Кэли. Классическим доказательство формулы использует теорему дерева матрицы Кирхгофа, формула для числа остовных деревьев в произвольном графе с участием детерминант в виде матрицы. Последовательности Прюфера дают биективное доказательство формулы Кэли. Другое биективное доказательство, выполненное Андре Жоялом, обнаруживает взаимно однозначное преобразование между деревьями n узлов с двумя выделенными узлами и максимальными направленными псевдолесьями. Доказательство двойным счетом из-за Джима Питмана подсчитывает двумя разными способами количество различных последовательностей ориентированных ребер, которые могут быть добавлены к пустому графу на n вершинах, чтобы сформировать из него корневое дерево; см. Двойной счет (метод доказательства) § Подсчет деревьев.

Формула была впервые обнаружена Карлом Вильгельмом Борхардтом в 1860 году и доказана с помощью определителя. В короткой заметке 1889 года Кэли расширил формулу в нескольких направлениях, приняв во внимание степени вершин. Хотя он ссылался на оригинальную статью Борхардта, название «формула Кэли» стало общепринятым в этой области.

Формула Кэли сразу дает количество помеченных корневых лесов на n вершинах, а именно ( n + 1) ^{n - 1}. Каждый помеченный корневой лес можно превратить в помеченное дерево с одной дополнительной вершиной, добавив вершину с меткой n + 1 и соединив ее со всеми корнями деревьев в лесу.

Существует тесная связь с корневыми лесами и функциями парковки, поскольку количество функций парковки на n автомобилях также равно ( n + 1) ^{n - 1}. Взаимосвязь между корневыми лесами и функциями парковки была дана депутатом Шютценбергером в 1968 году.

Обобщения

Следующее обобщает формулу Кэли на помеченные леса: Пусть T n, k - количество помеченных лесов на n вершинах с k компонентами связности, причем вершины 1, 2,..., k принадлежат разным компонентам связности. Тогда T n, k = k n ^{n - k - 1}.