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