Открыть главное меню

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

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

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

Содержание

ИсторияПравить

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

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

 

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

ФормулировкиПравить

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

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

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

  • Количество деревьев на   пронумерованных вершинах оказывается также равным числу разложений  -цикла   в произведение   транспозиции.
  • Количество деревьев на   пронумерованных вершинах оказывается также равным числу (соответствующим образом нормированных) многочленов степени   с заданными   критическими значениями общего положения.

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

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

ЛитератураПравить

  • Ю. М. Бурман, записки курса «Критические значения многочленов»: [1], [2], [3], [4].
  • М. Э. Казарян, записки курса «Геометрия, топология и комбинаторика разветвленных накрытий сферы».
  • A. Cayley (1889). «A theorem on trees». Quart. J. Math. 23: 376–378.
  • T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitz numbers and Hodge integrals.