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

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

Полный список деревьев на 2, 3 и 4 вершинах с , и деревьями соответственно.

История

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

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

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

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

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

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

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

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

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

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

  • Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования -вершинного помеченного дерева упорядоченной последовательностью из номеров его вершин.
  • Одно из доказательств строится на следующем соотношении
на экспоненциальную производящую функцию
где обозначает число корневых деревьев на данных вершинах. По теореме Лагранжа об обращении рядов, из этого соотношения следует, что . Последнее влечёт формулу Кэли поскольку для каждого остовного дерева есть ровно способов выбрать корневую вершину.[3]

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

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

Примечания

  1. 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.
  2. Biggs N. L., Lloyd E. K., Wilson R. J. Graph Theory 1736-1936. Clarendon Press, Oxford, 1976.
  3. Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.