Все формулы РФ

Математика / Графы, логика

Формула Кэли: число деревьев с помеченными вершинами

Формула Кэли считает неориентированные деревья на заданных n различных вершинах: связные графы без циклов. Метки вершин сохраняются, а расположение рисунка на плоскости не создаёт новых деревьев.

Опубликовано: Обновлено:

КомбинаторикаДискретная математикаАлгебраСтраницы с задачами и решениями

Формула

$$T_n=n^{n-2},\qquad n\ge2$$
Схема Коды Прюфера для четырёх вершин
Коды Прюфера для четырёх вершинКоды Прюфера для четырёх вершин1-я / 2-я12341(1,1)(1,2)(1,3)(1,4)2(2,1)(2,2)(2,3)(2,4)3(3,1)(3,2)(3,3)(3,4)4(4,1)(4,2)(4,3)(4,4)4 × 4 = 16 помеченных деревьев

Каждой из 16 пар соответствует ровно одно дерево.

Обозначения

$Tₙ$
число помеченных неориентированных деревьев, безразмерная величина
$n$
число вершин с различными метками, безразмерная величина

Условия применения

Вершины имеют фиксированные разные метки от 1 до n, n≥2. Граф простой, неориентированный, связный и без циклов; корень не выделен. Разрешено любое ребро между разными вершинами. Два дерева различны, если отличаются наборами пар соединённых меток.

Ограничения

Формула не считает непомеченные формы деревьев и не применяется к произвольному графу с запрещёнными рёбрами. Если корень можно выбирать, число укоренённых помеченных деревьев умножается на n. Для одной вершины отдельно принимают T₁=1, не вычисляя спорные предельные выражения.

Подробное объяснение

У дерева на n вершинах ровно n−1 ребро, но простое выбирание n−1 рёбер из полного графа неверно: среди выбранных наборов будут циклы и несвязные графы. Формула Кэли сразу считает только допустимые связные ациклические наборы рёбер.

Удобное доказательство использует код Прюфера. Пока остаётся больше двух вершин, удаляют лист с наименьшей меткой и записывают метку его соседа. Удаляется n−2 листа, поэтому получается последовательность длины n−2 из чисел от 1 до n.

Из любой такой последовательности дерево восстанавливается однозначно: очередной записанный номер соединяют с наименьшей ещё доступной меткой, отсутствующей в оставшейся последовательности. После удаления этой метки процесс повторяют, а две последние вершины соединяют ребром.

Таким образом, дерево и код соответствуют друг другу взаимно однозначно. В каждой из n−2 позиций кода независимо выбирается одна из n меток; правило произведения даёт n^(n−2). Повтор метки в коде допустим и показывает, что соответствующая вершина имеет больше соседей.

Для четырёх вершин есть два непомеченных типа — звезда и путь, но помеченных деревьев шестнадцать. Разница важна: перестановка номеров может изменить набор рёбер, даже если рисунок остался похожим. При двух вершинах код пуст, что даёт единственный вариант соединения.

Как пользоваться формулой

  1. Убедитесь, что все вершины различаются метками и любое ребро между двумя вершинами допустимо.
  2. Проверьте, что корень и направления рёбер не выделяются, а одинаковые рисунки сравниваются по меткам.
  3. Подставьте число вершин n в n^(n−2); для n=1 отдельно используйте единственное дерево без рёбер.
  4. Для малой задачи проверьте результат кодами Прюфера или разделением деревьев по их форме.

Историческая справка

Результат традиционно носит имя Артура Кэли и занимает центральное место в перечислительной теории графов. В современных университетских курсах рядом с ним рассматривают код Прюфера как конструктивное доказательство: сложный объект превращается в последовательность фиксированной длины. Учебник Applied Combinatorics подробно связывает кодирование с подсчётом деревьев, а курс MIT показывает несколько доказательств той же формулы. Такая множественность доказательств важна для истории математической идеи: название теоремы и имя автора конкретного способа доказательства не обязательно совпадают. В комбинаторике XX–XXI веков код служит также инструментом генерации деревьев и контроля степеней вершин. Поэтому здесь отдельно названы формула Кэли и код Прюфера, без приписывания обоих одному человеку.

Историческая линия формулы

Теорема известна как формула Кэли для помеченных деревьев. Приведённое объяснение использует код Прюфера — другой именованный результат, обеспечивающий биекцию с последовательностями. Утверждение относится к деревьям с сохранением меток и не является формулой количества их непомеченных форм.

Пример

Нужно соединить четыре названных узла 1,2,3,4 в дерево; каждая пара может иметь связь, направления и корня нет. Формула даёт T₄ = 4^(4−2) = 16. Проверим по формам. Звёзд четыре: центральной можно выбрать любую вершину. Путей двенадцать: линейных порядков меток 4! = 24, но прямой и обратный обход одного пути дают один набор рёбер, поэтому 24/2 = 12. Сумма 4 + 12 = 16 совпадает. У каждого дерева три ребра; граф из треугольника и отдельной вершины тоже имеет три ребра, но деревом не является и в ответ не включается. Единица результата — число наборов связей.

Частая ошибка

Не выбирайте просто n−1 рёбер произвольным сочетанием: связность не гарантирована. Не смешивайте количество форм и помеченных деревьев. Не умножайте на n для корня, если он не задан условием как дополнительный выбор. Не применяйте ответ к сети, в которой часть соединений запрещена.

Практика

Задачи с решением

Пять узлов

Условие. Сколько деревьев на пяти фиксированных различных вершинах?

Решение. T₅ = 5^(5−2) = 5³ = 125.

Ответ. 125 деревьев

Выбор корня

Условие. Сколько помеченных деревьев на четырёх вершинах с дополнительно выбранным корнем?

Решение. Сначала 4² = 16 деревьев, затем четыре выбора корня: 16·4 = 64.

Ответ. 64 укоренённых дерева

Дополнительные источники

  • https://www.appliedcombinatorics.org/book/s_graphs_counting-trees.html
  • https://www-math.mit.edu/~apost/courses/18.212/

Связанные формулы

Математика

Число ребер полного графа

$E(K_n)=\binom n2=\frac{n(n-1)}2$

Формула описывает прием «подсчет пар вершин» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.