Количество помеченных деревьев с заданным подграфом с использованием кода Пруфера.

Aug 17 2020

Постановка задачи

Я хочу подсчитать количество деревьев с набором вершин $V$ = {1, 2, 3, ..., 10}, которые имеют $\\$

дерево $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (выглядит как 1–2–3) как подграф.

Итак, если я правильно думаю, мне нужно найти количество помеченных деревьев с n вершинами и 2 фиксированными ребрами.

По формуле Кэли есть $n^{n-2}$ деревья с n вершинами.

Я считаю, что алгоритм кода tree -> prufer находит наименьший лист, добавляя последовательность с родителем этого листа и удаляя этот лист и связанное с ним ребро. У нас будет два слота в нашей последовательности пруфера, занятые либо (2,2), (3,2), либо (1, 2). Одна из этих подпоследовательностей может начинаться$n-1$слоты. Остальные слоты могут использоваться любой из n вершин. Итак, мы получаем$3 \cdot (n-1) \cdot n^{n-4}$. Но это совершенно неверно. Я попытался использовать некоторые доказательства аналогичных проблем с одним фиксированным краем, но мне кажется, что у меня проблемы с их пониманием ...

Ответы

1 BrianM.Scott Aug 17 2020 at 08:17

Представьте, что дерево $T$( 3---2---1) стягивается до единственной вершины с меткой$0$. Есть$8^6$ помеченные деревья на множестве вершин $\{0,4,5,6,7,8,9,10\}$. За$k=1,\ldots,7$, в скольких из этих деревьев вершина $0$ иметь степень $k$?

Вершина $0$ появляется $k-1$ раз в коде Прюфера такого дерева, и каждый из этих кодов Прюфера имеет $6$ слоты, так что есть $\binom6{k-1}$ способы разместить $k-1$нули в коде. Тогда есть$7$ выбор для каждого из оставшихся $6-(k-1)=7-k$ слотов, так что всего $\binom6{k-1}7^{7-k}$ такие деревья.

Каждому из них соответствует более одного дерева на множестве вершин $V$ который содержит дерево $T$. В частности, если вершина$0$ имеет степень $k$ в одном из этих деревьев каждое выходящее из него ребро может быть прикреплено к любой из трех вершин $1,2$, и $3$ когда мы расширяем вершину $0$ к $T$, поэтому дерево расширяется до $3^k$ разные деревья на множестве вершин $V$.

Подводя итоги $k=1,\ldots,7$, мы обнаруживаем, что всего

$$\begin{align*} \sum_{k=1}^73^k\binom6{k-1}7^{7-k}&=\sum_{k=0}^6\binom6k3^{k+1}7^{6-k}\\ &=3\sum_{k=0}^6\binom6k3^k7^{6-k}\\ &=3(3+7)^6\\ &=3,000,000 \end{align*}$$

деревья на множестве вершин $V$ которые содержат $T$. (Предпоследний шаг использует биномиальную теорему.)

Этот анализ легко обобщается до формулы для количества помеченных деревьев на $n$ вершины, содержащие определенное поддерево $T$ с участием $m$ вершины.