algorithm - 具有最小颜色总和的着色树

Question

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

执行此操作的颜色数量是否有限？

Answer 1

我认为 3 种颜色足以做到这一点。如何证明？

它不是。用代数方式描述一棵有根树如下。V是一棵单节点树。E(t1, t2)是一棵树，由t1和t2和从t1' 根到t2' 根的边组成，以 ' 根为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) 是有 d 个叶子连接到 T(d, i - 1) 的每个顶点的树。

通过对 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]

Answer 2

首先，2 种颜色对于任何树都足够了。为了证明这一点，您可以使用替代颜色逐级着色树。

其次，逐级着色是唯一有效的二次着色方法。可以通过层次上的归纳来证明。修复根节点的颜色。然后它的所有孩子都应该有不同的颜色，孩子的孩子——第一种颜色，等等。

第三，要选择最佳着色，只需检查两种可能的布局：分别是根节点有颜色的0时候和有颜色的时候1。

Answer 3

对于树，您只能使用两种颜色：一种用于奇数深度的节点，另一种颜色用于偶数深度的节点。

编辑：之前的答案是错误的，因为我不明白这个问题。

如 Wobble 所示，所需的颜色数量没有限制。

Answer 4

具有 n 个节点的树的最小总和的颜色数限制为 O(logn)

E. Kubicka 在她 1989 年的论文 http://dl.acm.org/citation.cfm?id=75430中对此进行了介绍

Answer 5

用 2 种颜色 {0,1} 为任何树着色就足够了，但复杂度将是 O(n)。

用 3 种颜色 {0,1,2} 着色任何树就足够了，但复杂度将是 O(log* (n))

现在的问题是什么是 log*(n)

log* (n) - “log Star n”，即“迭代对数”

简单来说，您可以假设 log* (n)= log(log(log(.....(log* (n))))

log* (n) 非常强大。

例子：

1) Log* (n)=5 其中 n= 宇宙中的原子数

2）在知道欧几里得最小生成树的情况下找到一组点的Delaunay三角剖分：随机O（n log * n）时间。