Как рассчитать способы покрасить дерево?

Question

Как рассчитать способы покрасить дерево?

Как рассчитать способы раскраски узлов дерева m цветами, чтобы концы каждого ребра имели разные цвета?

Любое полиномиальное решение приветствуется.

6

algorithm tree graph-coloring

Источник

user6573669 20 сен '16 в 10:14

1 ответ

Решение

Другие вопросы по тегам algorithm tree graph-coloring

user2041077 20 сен '16 в 11:55 2016-09-20 11:55 · Accepted Answer · 2016-09-20 11:55

У вас есть м выбор для корня. Если вы рисуете вниз от корня, у вас есть выбор m-1 для каждого дополнительного узла. Если число узлов равно n, то количество способов нарисовать дерево равно m * (m-1)^(n-1).

3

Источник

user2041077 20 сен '16 в 11:55