Формула Кэли - Cayley's formula

Полный список всех деревьев на 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 ).

Доказательство

Известно множество доказательств формулы дерева Кэли. Классическим доказательство формулы использует теорему дерева матрицы Кирхгофа , формула для числа остовных деревьев в произвольном графе с участием детерминант в виде матрицы . Последовательности Прюфера дают биективное доказательство формулы Кэли. Другое биективное доказательство, выполненное Андре Жоялом , обнаруживает взаимно однозначное преобразование между деревьями 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} .

Рекомендации