Question

Плата хорошая.
Zadanie 1(Задаание 1).
Найдите деревья со следующими кодами Пруфера:
Zadanie 2(Задание 2).
Найти количество деревьев с n вершинами, в которых вершина номер 1 имеет степень k (k<=n).
Zadanie 3(Задание 3).
Найти количество деревьев с n вершинами, имеющими вершину строки n-2.
​

Answer 1

Задание 1

Ответ в приложении

Задание 2

Тут, очевидно, опечатка, k<n. В дереве на n вершинах не может быть вершины степени n.

n=1:

• k=0 - одно дерево, состоящее из одной вершины.

n=2:

• k=0 => граф не связный => не дерево

• k=1 => одно дерево, состоящее из одного ребра

n>2:

• k=0 => граф не связный => не дерево

• k>0 => Тогда каждому дереву поставим в соответствие код Прюфера. Его длина - n-2. Т.к. вершина 1 имеет степень k, то встречается в нем k-1 раз. Тогда для остальных n-1 вершин остается n-2-(k-1)=n-k-1 мест. Тогда всего таких кодов Прюфера, и, следовательно, деревьев, $\dfrac{(n-2)!}{(k-1)!(n-k-1)!}*(n-1)^{(n-k-1)}$

Задание 3

Найти количество деревьев с n вершинами, имеющими вершину степени n-2.

Зафиксируем номер этой вершины. Тогда в коде Прюфера она встречается n-3 раз. Тогда для остальных n-1 вершин остается n-2-(n-3)=1 место. Кол-во способов выбора номера вершины степени n-2 из n равно n. Тогда искомое число деревьев равно $n*\dfrac{(n-2)!}{(n-3)!1!}*(n-1)^1=n(n-1)(n-2)$