В математике , формула Кэлей является результатом в теории графов именем Кэлей . В нем говорится, что для каждого положительного целого числа , количество деревьев наМеченые вершины является.
Формула эквивалентно , подсчитывает число остовных деревьев из более полного графа с помеченными вершинами (последовательность A000272 в OEIS ).
Доказательство
Известно множество доказательств формулы дерева Кэли. [1] Одним классическим доказательство формулы использует теорему дерева матрицы Кирхгофа , формула для числа остовных деревьев в произвольном графе с участием определитель матрицы А матрицы . Последовательности Прюфера дают биективное доказательство формулы Кэли. Другое биективное доказательство, выполненное Андре Жоялом , обнаруживает взаимно однозначное преобразование между деревьями n- узлов с двумя выделенными узлами и максимальными направленными псевдолесьями . Доказательство двойным счетом из-за Джима Питмана подсчитывает двумя разными способами количество различных последовательностей направленных ребер, которые могут быть добавлены к пустому графу на n вершинах, чтобы сформировать из него корневое дерево; см. Двойной счет (метод доказательства) § Подсчет деревьев .
История
Формула была впервые открыта Карлом Вильгельмом Борхардтом в 1860 году и доказана с помощью определителя . [2] В короткой заметке 1889 года Кэли расширил формулу в нескольких направлениях, приняв во внимание степени вершин. [3] Хотя он сослался на оригинальную статью Борхардта, название «формула Кэли» стало стандартом в этой области.
Прочие свойства
Формула Кэли сразу дает количество помеченных корневых лесов на n вершинах, а именно ( n + 1) n - 1 . Каждый помеченный корневой лес можно превратить в помеченное дерево с одной дополнительной вершиной, добавив вершину с меткой n + 1 и соединив ее со всеми корнями деревьев в лесу.
Существует тесная связь с корневыми лесами и функциями парковки , поскольку количество функций парковки на n автомобилях также равно ( n + 1) n - 1 . Взаимосвязь между корневыми лесами и функциями парковки была дана депутатом Шютценбергером в 1968 году [4].
Обобщения
Следующее обобщает формулу Кэли на помеченные леса: Пусть T n , k - количество помеченных лесов на n вершинах с k компонентами связности, таких, что вершины 1, 2, ..., k принадлежат различным компонентам связности. Тогда T n , k = k n n - k - 1 . [5]
Рекомендации
- ^ Айгнер, Мартин ; Циглер, Гюнтер М. (1998). Доказательства из КНИГИ . Springer-Verlag . С. 141–146.
- ^ Борхардт, CW (1860). "Uber eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung". Математика. Abh. der Akademie der Wissenschaften zu Berlin : 1–20.
- ^ Кэли, А. (1889). «Теорема о деревьях» . Кварта. J. Pure Appl. Математика . 23 : 376–378.
- ^ Шютценбергер, депутат (1968). «По проблеме перечисления». Журнал комбинаторной теории . 4 : 219–221. Руководство по ремонту 0218257 .
- ^ Такач, Лайош (март 1990 г.). «О формуле Кэли для подсчета лесов» . Журнал комбинаторной теории, Серия А . 53 (2): 321–323. DOI : 10.1016 / 0097-3165 (90) 90064-4 .