Теорема Кэли о числе деревьев — теорема, утверждающая, что число деревьев с ${\displaystyle n}$ пронумерованными вершинами равно ${\displaystyle n^{n-2}}$ .

История

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

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

${\displaystyle {(x_{1}+\dots +x_{n})}^{n-2}\cdot (x_{1}\cdot x_{2}\cdot \ldots \cdot x_{n}),}$

то коэффициент при одночлене вида ${\displaystyle x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}}$ будет равен числу деревьев, у которых степени вершин равны степеням переменных данного терма: ${\displaystyle d_{1},\dots ,d_{n}}$ .

Кэли подробно разбирает случай ${\displaystyle n=6}$ и заявляет, что доказательство легко обобщается.

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

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

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

• Число остовных деревьев в полном графе ${\displaystyle K_{n}}$ равно ${\displaystyle n^{n-2}}$ .

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

• Количество деревьев на ${\displaystyle n}$ пронумерованных вершинах оказывается также равным числу разложений ${\displaystyle n}$ -цикла ${\displaystyle (1\dots n)}$ в произведение ${\displaystyle n-1}$ транспозиции .

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

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

• Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования ${\displaystyle n}$ -вершинного помеченного дерева упорядоченной последовательностью из ${\displaystyle n-2}$ номеров его вершин.

• Формула Кэли также легко выводится из матричной теоремы о деревьях .

• Одно из доказательств строится на следующем соотношении

  ${\displaystyle a(x)=x\cdot e^{a(x)}}$

на экспоненциальную производящую функцию

${\displaystyle a(x)=a_{1}\cdot x+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {1}{n!}}\cdot a_{n}\cdot x^{n}+\dots }$

где ${\displaystyle a_{n}}$ обозначает число корневых деревьев на ${\displaystyle n}$ данных вершинах. По теореме Лагранжа об обращении рядов , из этого соотношения следует, что ${\displaystyle a_{n}=n^{n-1}}$ . Последнее влечёт формулу Кэли поскольку для каждого остовного дерева есть ровно ${\displaystyle n}$ способов выбрать корневую вершину.

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

• Количество способов связывания графа, состоящего из ${\displaystyle m}$ несвязных компонент, каждая размером ${\displaystyle x_{i}}$ вершин, равно

  ${\displaystyle T[x_{m}]=x_{1}\cdot x_{2}\dots x_{m}\cdot (x_{1}+x_{2}+\dots +x_{m})^{m-2}=[x_{m}]!\ n^{m-2}}$

  Здесь ${\displaystyle n=x_{1}+x_{2}+\dots +x_{m}}$ — общее количество вершин графа.

  Если каждая компонента состоит из одной вершины ${\displaystyle (x_{i}=1)}$ , то ${\displaystyle n=m}$ , и формула дает исходное число Кэли ${\displaystyle n^{n-2}}$ .

• Число остовных деревьев в полном двудольном графе ${\displaystyle K_{m,n}}$ равно

  ${\displaystyle T(K_{m,n})=m^{n-1}\cdot n^{m-1}.}$

• Матричная теорема о деревьях даёт выражение числа остовных деревьев графа как определитель лапласиана (матрицы Кирхгофа) графа.

Примечания

Литература

• Ю. М. Бурман, записки курса « »: , , , .
• М. Э. Казарян, курса « ».
• A. Cayley. (неопр.) // Quart. J. Math. — 1889. — Т. 23 . — С. 376—378 .
• T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. .