Меню Главная Случайная статья Настройки Теорема Кэли о числе деревьев Материал из https://ru.wikipedia.org Теорема Кэли о числе деревьев — теорема, утверждающая, что число деревьев с ${\displaystyle n}$ пронумерованными вершинами равно ${\displaystyle n^{n-2}}$. Содержание 1 История 2 Формулировки 2.1 Связанные утверждения 3 О доказательствах 4 Вариации и обобщения 5 Примечания 6 Литература История Теорема названа в честь Артура Кэли, который доказал её в 1889 году.[1] Сам Кэли признавал, что то же утверждение было доказано раньше Карлом Борхардом и в эквивалентной формулировке ещё раньше в статье Джеймса Джозефа Сильвестра 1857 года.[2] В своей статье Кэли по сути доказывает более общее утверждение. Если раскрыть скобки выражения ${\displaystyle {(x_{1}+\dots +x_{n})}^{n-2}\cdot (x_{1}\cdot x_{2}\cdot \ldots \cdot x_{n}),}$ то коэффициент при одночлене вида ${\displaystyle x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}}$ будет равен числу деревьев, у которых степени вершин равны степеням переменных данного терма: ${\displaystyle d_{1},\dots ,d_{n}}$. Кэли подробно разбирает случай ${\displaystyle n=6}$ и заявляет, что доказательство легко обобщается. Формулировки Две эквивалентные формулировки: Число различных деревьев на ${\displaystyle n}$ вершинах, пронумерованных числами от ${\displaystyle 1}$ до ${\displaystyle n}$, равно ${\displaystyle n^{n-2}}$. Число остовных деревьев в полном графе ${\displaystyle K_{n}}$ равно ${\displaystyle n^{n-2}}$. Связанные утверждения Количество деревьев на ${\displaystyle n}$ пронумерованных вершинах оказывается также равным числу разложений ${\displaystyle n}$-цикла ${\displaystyle (1\dots n)}$ в произведение ${\displaystyle n-1}$ транспозиции. Количество деревьев на ${\displaystyle n}$ пронумерованных вершинах оказывается также равным числу (соответствующим образом нормированных) многочленов степени ${\displaystyle n}$ с заданными ${\displaystyle n-1}$ критическими значениями общего положения. Наконец, это последнее является частным случаем топологической классификации разветвлённых накрытий[англ.] сферы Римана — тем самым, подсчёт числа деревьев оказывается частным случаем вычисления чисел Гурвица, соответствующим случаю накрывающей поверхности рода 0. О доказательствах Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования ${\displaystyle n}$-вершинного помеченного дерева упорядоченной последовательностью из ${\displaystyle n-2}$ номеров его вершин. Формула Кэли легко выводится из матричной теоремы о деревьях. Одно из доказательств строится на следующем соотношении ${\displaystyle a(x)=x\cdot e^{a(x)}}$ на экспоненциальную производящую функцию ${\displaystyle a(x)=a_{1}\cdot x+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {1}{n!}}\cdot a_{n}\cdot x^{n}+\dots }$ где ${\displaystyle a_{n}}$ обозначает число корневых деревьев на ${\displaystyle n}$ данных вершинах. По теореме Лагранжа об обращении рядов, из этого соотношения следует, что ${\displaystyle a_{n}=n^{n-1}}$. Последнее влечёт формулу Кэли поскольку для каждого остовного дерева есть ровно ${\displaystyle n}$ способов выбрать корневую вершину.[3] Доказательство Марка Цукреа[4] опирается на биномиальную теорему Абеля и двойной подсчёт. Вариации и обобщения Количество способов связывания графа, состоящего из ${\displaystyle m}$ несвязных компонент, каждая размером ${\displaystyle x_{i}}$ вершин, равно ${\displaystyle T[x_{m}]=x_{1}\cdot x_{2}\dots x_{m}\cdot (x_{1}+x_{2}+\dots +x_{m})^{m-2}=[x_{m}]!\ n^{m-2}}$ Здесь ${\displaystyle n=x_{1}+x_{2}+\dots +x_{m}}$ — общее количество вершин графа. Если каждая компонента состоит из одной вершины ${\displaystyle (x_{i}=1)}$, то ${\displaystyle n=m}$, и формула дает исходное число Кэли ${\displaystyle n^{n-2}}$. Число остовных деревьев в полном двудольном графе ${\displaystyle K_{m,n}}$ равно ${\displaystyle T(K_{m,n})=m^{n-1}\cdot n^{m-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. Biggs N. L., Lloyd E. K., Wilson R. J. Graph Theory 1736-1936. Clarendon Press, Oxford, 1976. Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977. David Benko, «A New Approach to Hilbert's Third Problem» The American Mathematical Monthly Vol. 114, No. 8 (Oct., 2007), pp. 665--676 Литература Ю. М. Бурман, записки курса «Критические значения многочленов»: [1], [2], [3], [4]. М. Э. Казарян, записки курса «Геометрия, топология и комбинаторика разветвленных накрытий сферы». A. Cayley. A theorem on trees (неопр.) // Quart. J. Math. — 1889. — Т. 23. — С. 376—378. T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitz numbers and Hodge integrals.