1.2　着色树

引理1.13　X（Tree）≤2

证明：假定某个节点为树的根。如果一个节点到树根的距离是奇数（偶数），就把它染成1（0）。奇数节点只有偶数邻居，反之亦然。

备注：

●假设每个节点都知道自己在树中的父节点（根节点没有父节点）和子节点，这个构造性证明给出了一个非常简单的算法。

算法1.14　慢树着色

1.根的颜色为0，根向它的孩子发送0

2.每个节点v并发地执行以下代码

3.if节点v从父节点那里接收一个消息cp then

4.　节点v选择一个颜色cv=1-cp

5.　节点v发送颜色cv给它的子节点（除了父节点之外的所有邻居节点）

6.end if

定理1.15　算法1.14是正确的。如果每个节点都知道它的父节点和子节点，那么时间复杂度就是树的高度，而树的高度是由树的直径限定的。

备注：

●如果还没有给定树根，我们如何确定树根呢？后面会讨论。

●算法的时间复杂度就是树的高度。

●好的树，比如平衡二叉树，其高度是节点数的对数，也就是说时间复杂度是对数级的。

●如果树的拓扑结构退化，时间复杂度有可能达到n，即节点数。

这个算法不是很令人激动。我们能不能做得比对数级的时间复杂度更好呢？

下面是算法的思路：我们从具有log n位的颜色标签开始。在每一轮中，我们计算一个新的标签，它的大小相比前一个标签的大小指数倍地缩小，但仍然保证有一个有效的顶点着色！这个算法在log* n的时间内终止。迭代对数①（log*）就是你需要取的对数（以2为底）的次数，从而能降到2，形式上：

注①：迭代对数（iterated log arithm）也称为重复对数，是一个增加非常慢的数学函数，可以视为近似常数。一般用log* n来表示。一个实数的迭代对数是指需对实数连续进行几次对数运算后，其结果才会小于等于1。——译者注

定义1.16（迭代对数（log*））

∀x≤2：log* x:=1　∀x＞2：log* x:=1+log*（log x）

备注：

●迭代对数是一个惊人地缓慢增长的函数。在可观测的宇宙中，所有原子（估计有1080个）的迭代对数是5，所以迭代对数的增长确实很慢。有的函数增长得更慢，比如阿克曼函数的倒数，但是，所有原子的阿克曼函数倒数已经是4了。

例子：

对一棵树按以下部分执行算法1.17：

Grand-parent　0010110000　→　10010　→　…

Parent　　　　1010010000　→　01010　→　111

Child　　　　 0110010000　→　10001　→　001

算法1.17　6种颜色

1.初始时，每个节点v有大小为log n位大小的ID（颜色）号cv

2.每个节点v执行以下代码

3.repeat

4.　将自己的颜色cv传给所有的孩子

5.　从父节点那里接收颜色cp（对于根r的集合cp∈{0，1}≠cr）

6.　将cv和cp编译成位串

7.　令i为最右侧位b的编号，其中cv和cp的不同

8.　节点v的新颜色变为cv=2i+b

9.until对于所有的节点v存在cv∈{0，…，5}

定理1.18　算法1.17在log* n+k时间内终止，其中k是一个独立于n的常数。

证明：我们需要证明父节点p和子节点c总是有不同的颜色。最初，这是真的，因为所有节点都从其唯一的ID开始。在一轮中，设i是子节点c与父节点p出现不同位的最小索引值。如果父节点p与自己的父节点在j处不同，且j≠i，则父节点p和子节点c在该轮中得到不同的颜色。另一方面，如果j=i，则通过一个在i处有不同位的父节点p，打破对称性。

关于运行时间，请注意，除了打破对称性位之外，最大颜色的大小在每一轮中都急剧缩小，完全是一个对数函数。通过一些烦琐而枯燥的机制，可以证明确实每个节点都会在log* n+k轮，取得一个{0，…，5}范围内的颜色。

备注：

●让我们仔细看看这个算法。颜色11＊（二进制值，即十进制的6或7）将不会被选择，因为节点将再进行一轮。这样一来，总共有6种颜色（即颜色0，…，5）。

●那循环的最后一行呢？节点如何知道现在所有节点的颜色都在{0，…，5}范围内？这个问题的答案非常复杂。我们可以在until语句中硬性加入循环次数，使所有节点执行循环的次数完全相同。然而，为了做到这一点，所有节点都需要知道n，即节点数，这很愚蠢。有一些（非平凡的）解决方案，其中节点不需要知道n，见练习。

●可以减少颜色的数量吗？请注意，算法1.9是行不通的（因为一个节点的度可能远远大于6）！为了减少颜色，我们需要让兄弟姐妹单色！

算法1.19　减少

1.每个节点v并发地执行以下代码

2.用父节点的颜色重新着色v

3.根节点从{0，1，2}中选择一个新的（不同的）颜色

引理1.20　算法1.19保留了着色的合法性，同时兄弟姐妹也是单色的。

现在可以使用算法1.21将使用的颜色数量从6种减少到3种。

算法1.21　6种到3种

1.每个节点v并发地执行以下代码

2.for x=5，4，3 do

3.　执行子例程减少（算法1.19）

4.　if cv=x then

5.　　选择最少的可接受的新颜色cv∈{0，1，2}

6.　end if

7.end for

图1-22　算法1.21的可能执行

定理1.23　算法1.17和算法1.21在O（log* n）的时间内给一棵具有三种颜色的树着色。

备注：

●定理1.18中使用的术语O（）被称为大O，在分布式计算中经常使用。粗略地讲，O（f）的意思是按照f的顺序，忽略常数因子和较小的加法项。更正式地说，对于两个函数f和g，如果有常数x0和c，对所有x≥x0，使|f（x）|≤c|g（x）|，则认为f∈O（g）。关于大O的详细讨论，可以参考其他数学或计算机科学入门课程，或者维基百科。

●只用2种颜色的快速树着色比用3种颜色着色的成本要高得多。在一棵退化为列表的树中，远处的节点需要弄清楚它们之间的距离是偶数还是奇数跳，才能得到2种颜色的着色。要做到这一点，就必须向这些节点发送一条消息。这需要耗费的时间与节点数量呈线性关系。

●这个算法的思想可以推广，例如，可以推广到环形拓扑。同时，一个恒定的度为Δ的一般图也可以在O（log* n）时间内用Δ+1种颜色进行着色。其原理如下：在每一步中，一个节点将自己的标签与每一个邻居进行比较，构建一个对数差异标签，如算法1.17。然后，新的标签是所有差异标签的连接。对于恒定的度Δ，这将在O（log* n）步中得到一个3Δ位的标签。然后，算法1.9将颜色的数量减少到Δ+1，需要23Δ步（对于常数Δ，这仍然是一个常数）。

●不幸的是，用这种技术还不能给一般图着色。我们将在下一章中看到另一种技术。使用这种技术，可以在O（log n）时间内为一个具有Δ+1种颜色的一般图着色。

●一个下界表明，在这些迭代对数级的算法中，许多算法都是渐近（直到常数系数）最优的。我们将在后面看到这一点。