如何计算给一棵树上色的方法？

Question

6

如何计算用m种颜色给一棵树的节点着色的方案数，以使每条边的端点颜色不同？

任何多项式解决方案都可以。

- newbie

是的，我正在寻找多种方法。 - newbie

它必须使用所有的m种颜色吗？ - Bergi

1

你不需要任何算法，只需要应用一个 O(1) 公式（假设你不必先计算节点）：https://en.wikipedia.org/wiki/Chromatic_polynomial#Examples - Bergi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dave · Accepted Answer

你有m个选择作为树的根节点。如果你从根节点向下涂色，那么每个额外节点都有m-1种选择。如果节点数为n，则涂树的方式有m * (m-1)^(n-1)种。