Формула Кэли

Формула Кэли : эта формула сообщает, сколько деревьев можно построить с N вершинами. Это утверждает, что существует N ^{N - 2} помеченных деревьев, что из N узлов. Узлы помечены цифрами 1, 2,…, N , и два дерева различаются, если их структура или маркировка различаются.

Например: когда N равно 4 , количество помеченных деревьев составляет 4 ^{4 - 2} = 16.

Ниже показано количество помеченных деревьев:

На изображении выше дано 4 узла, из которых создано 16 помеченных деревьев.

Формула Кэли, полученная с использованием кодов Прюфера :

Код Прюфера :

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

Ниже приведены шаги для расчета кода Прюфера на следующем графике:

• Дан граф с пятью узлами:

• Удалите узел 1 и добавьте узел 4 в код:

• Затем удалите узел 3 и добавьте узел 4 в код:

• Наконец, удалите узел 4 и добавьте узел 2 в код:

Таким образом, код Прюфера графа задается как {4, 4, 2} .

• Код Прюфера можно построить для любого дерева.
• Исходное дерево можно восстановить по коду Прюфера.
• Следовательно, количество помеченных деревьев из n узлов равно N ^{N - 2.} , количество кодов Прюфера размера N.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .