Теорема Кэли о числе деревьев
» » Теорема Кэли о числе деревьев

Теорема Кэли о числе деревьев

13.12.2020


Теорема Кэли о числе деревьев — явное выражение для числа деревьев с данным числом пронумерованных вершин.

История

Теорема названа в честь Артура Кэли, который доказал её в 1889 году. Сам Кэли признавал, что то же утверждение было доказано раньше Карлом Борхардом и в эквивалентной формулировке ещё раньше в статье Джеймса Джозефа Сильвестра 1857 года.

В своей статье Кэли по сути доказывает более общее утверждение. А именно если раскрыть скобки в формуле

( x 1 + ⋯ + x n ) n − 2 , {displaystyle (x_{1}+dots +x_{n})^{n-2},}

то коэффициент при x 1 d 1 − 1 ⋯ x n d n − 1 {displaystyle x_{1}^{d_{1}-1}cdots x_{n}^{d_{n}-1}} окажется равным числу деревьев на n {displaystyle n} вершинах, пронумерованных числами от 1 {displaystyle 1} до n {displaystyle n} со степенями d 1 , … , d n {displaystyle d_{1},dots ,d_{n}} соответственно. Кэли подробно разбирает случай n = 4 {displaystyle n=4} , и заявляет, что доказательство легко обобщается.

Формулировки

Две эквивалентные формулировки:

  • Число различных деревьев на n {displaystyle n} вершинах, пронумерованных числами от 1 {displaystyle 1} до n {displaystyle n} равно n n − 2 {displaystyle n^{n-2}} .
  • Число остовных деревьев в полном графе K n {displaystyle K_{n}} равно n n − 2 {displaystyle n^{n-2}} .

Связанные утверждения

  • Количество деревьев на n {displaystyle n} пронумерованных вершинах оказывается также равным числу разложений n {displaystyle n} -цикла ( 1 … n ) {displaystyle (1dots n)} в произведение n − 1 {displaystyle n-1} транспозиции.
  • Количество деревьев на n {displaystyle n} пронумерованных вершинах оказывается также равным числу (соответствующим образом нормированных) многочленов степени n {displaystyle n} с заданными n − 1 {displaystyle n-1} критическими значениями общего положения.
    • Наконец, это последнее является частным случаем топологической классификации разветвлённых накрытий сферы Римана — тем самым, подсчёт числа деревьев оказывается частным случаем вычисления чисел Гурвица, соответствующим случаю накрывающей поверхности рода 0.

О доказательствах

  • Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования n {displaystyle n} -вершинного помеченного дерева упорядоченной последовательностью из n − 2 {displaystyle n-2} номеров его вершин.
  • Формула Кэли также легко выводится из матричной теоремы о деревьях.
  • Одно из доказательств строится на следующем соотношении a ( x ) = x ⋅ e a ( x ) {displaystyle a(x)=xcdot e^{a(x)}}
на экспоненциальную производящую функцию a ( x ) = a 1 ⋅ x + 1 2 ⋅ a 2 ⋅ x 2 + ⋯ + 1 n ! ⋅ a n ⋅ x n + … {displaystyle a(x)=a_{1}cdot x+{ frac {1}{2}}cdot a_{2}cdot x^{2}+dots +{ frac {1}{n!}}cdot a_{n}cdot x^{n}+dots } где a n {displaystyle a_{n}} обозначает число корневых деревьев на n {displaystyle n} данных вершинах. По теореме Лагранжа об обращении рядов, из этого соотношения следует, что a n = n n − 1 {displaystyle a_{n}=n^{n-1}} . Последнее влечёт формулу Кэли поскольку для каждого остовного дерева есть ровно n {displaystyle n} способов выбрать корневую вершину.

Вариации и обобщения

  • Число остовных деревьев в полном двудольном графе K m , n {displaystyle K_{m,n}} равно m n − 1 ⋅ n m − 1 . {displaystyle m^{n-1}cdot n^{m-1}.}
  • Матричная теорема о деревьях даёт выражение на число остовных деревьев графа через определитель определённой матрицы построенной по графу.