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

История Теорема названа в честь Артура Кэли, который доказал её в 1889 году.Cayley A. A theorem on trees. Quart. J. Pure Appl. Math., 23 (1889), 376–378; Collected Mathematical Papers, Vol. 13, Cambridge University Press, 1897, 26–28. Сам Кэли признавал, что то же утверждение было доказано раньше Карлом Борхардом и в эквивалентной формулировке ещё раньше в статье Джеймса Джозефа Сильвестра 1857 года.Biggs N. L., Lloyd E. K., Wilson R. J. Graph Theory 1736-1936. Clarendon Press, Oxford, 1976.

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

то коэффициент при одночлене вида будет равен числу деревьев, у которых степени вершин равны степеням переменных данного терма: .

Кэли подробно разбирает случай и заявляет, что доказательство легко обобщается.

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

Число различных деревьев на вершинах, пронумерованных числами от до , равно .

Число остовных деревьев в полном графе равно .

Связанные утверждения Количество деревьев на пронумерованных вершинах оказывается также равным числу разложений -цикла в произведение транспозиции.

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

О доказательствах Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования -вершинного помеченного дерева упорядоченной последовательностью из номеров его вершин.

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

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

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

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

Доказательство Марка ЦукреаDavid Benko, «A New Approach to Hilbert's Third Problem» The American Mathematical Monthly Vol. 114, No. 8 (Oct., 2007), pp. 665--676 опирается на биномиальную теорему Абеля и двойной подсчёт.

Доказательство основано на построении биекции между множеством всех отображений из -точечного множетства в себя и , где обозначает множетвоп деревьев с множеством вершин .

Вариации и обобщения Количество способов связывания графа, состоящего из несвязных компонент, каждая размером вершин, равно

Здесь — общее количество вершин графа. Если каждая компонента состоит из одной вершины , то , и формула дает исходное число Кэли .

Число остовных деревьев в полном двудольном графе равно

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

Примечания

Литература Ю. М. Бурман, записки курса «Критические значения многочленов»: , , , . М. Э. Казарян, записки курса «Геометрия, топология и комбинаторика разветвленных накрытий сферы».

T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitz numbers and Hodge integrals.

К Категория:Комбинаторика