G-факт 20 (формула Кэли для числа помеченных деревьев)

Рассмотрим ниже вопросы.

1. Сколько остовных деревьев может быть в полном графе с n вершинами?
2. Сколько деревьев с метками (обратите внимание на деревья, а не на двоичные деревья) может быть с n вершинами?

Ответ на оба вопроса одинаковый.

При n = 2 имеется 1 дерево.

При n = 3 есть 3 дерева.

Для n = 4 имеется 16 деревьев

Формула утверждает, что для положительного целого числа n количество деревьев на n помеченных вершинах равно n ^n-2.

Источник:
https://en.wikipedia.org/wiki/Cayley%27s_formula

Эта статья предоставлена Вайбхавом Гуптой . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше