algorithm - 用最小的颜色总和给树着色

Question

问题是用自然数给树顶点着色，使得分配给顶点的数字(颜色)之和最小。

这样做的颜色数量是否有界？

Answer 1

I think 3 colors are enough to do that. How to prove it?

不是。用代数方式描述有根树如下。 V 是一棵单节点树。 E(t1, t2) 是一棵由 t1 和 t2 以及来自 t1 根的边组成的树到 t2 的根， Root 于 t2 的根。以下树 t3 需要四种颜色才能达到最小值 156。

t3 = E(t2, E(t2, E(t2, E(t2, t2))))
t2 = E(t1, E(t1, E(t1, E(t1, t1))))
t1 = E(t0, E(t0, E(t0, E(t0, t0))))
t0 = V

根据一些实验，我猜想可以证明这种构造具有泛化性，因此没有固定数量的颜色足以达到所有树的最小值。

定理 对于所有 d ≥ k ≥ 3，以下归纳构造的树 T(d, k) 至少需要 k 种颜色。 T(d, 1) 是单顶点树。对于 i > 1，T(d, i) 是 T(d, i - 1) 的每个顶点附有 d 个叶子的树。

证明 通过对 k 的归纳。基本情况 k = 3 本质上是您的示例，其中 3 种颜色是优化所必需的。对于 k > 3，考虑仅使用 k - 1 种颜色的 T(d, k) 着色。我们展示了如何使用颜色 k 来改进它。如果某个内部顶点的颜色为 1，那么我们通过将其颜色更改为 k 并将其 d > k - 1 相邻叶子的颜色更改为 1 来改进。如果没有间隔顶点的颜色为 1，并且某些叶子的颜色不是 1，将叶子更改为 1。如果我们还没有改进，则所有叶子的颜色都为 1，并且所有间隔顶点的颜色都 > 1。移除所有叶子并递减标签，我们得到 T(d, k - 1) 的着色，我们可以通过归纳假设对其进行改进。

---

data Tree = V | E Tree Tree
    deriving (Eq, Show)

otherMinimums [x, y] = [y, x]
otherMinimums (x:xs) = minimum xs : map (min x) (otherMinimums xs)

color m V = [1..m]
color m (E t1 t2) = let
    c1 = color m t1
    c2 = color m t2 in
    zipWith (+) (otherMinimums c1) c2

t3 = E t2 $ E t2 $ E t2 $ E t2 $ t2
t2 = E t1 $ E t1 $ E t1 $ E t1 $ t1
t1 = E t0 $ E t0 $ E t0 $ E t0 $ t0
t0 = V

结果:

> color 3 t3
[157,158,163]
> color 4 t3
[157,158,159,156]