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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Полный список деревьев на 2, 3 и 4 пронумерованных вершинах: 2^{2-2}=1 дерево с 2 вершинами, 3^{3-2}=3 дерева с 3 вершинами и 4^{4-2}=16 деревьев с 4 вершинами.

Теорема Кэли о числе деревьев — названное в честь А. Кэли явное выражение в теории графов для числа деревьев с данным числом пронумерованных вершин. А именно, оказывается, что на n вершинах, пронумерованных числами от 1 до n, существует ровно n^{n-2} различных деревьев.

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

Литература[править | править исходный текст]