1.1　问题和模型

问题1.1（顶点着色）　给定一个无向图G=（V，E），对于每一个顶点v∈V，赋予其一个颜色cv，使得如下式子成立：e=（v；w）∈E⇒cv≠cw。

备注：

●在本书中，我们交替使用术语“顶点”和“节点”。

●应用经常要求我们使用较少的颜色！在TDMA MAC协议中，较少的颜色即意味着较高的吞吐量。然而，在分布式计算中，我们常常对一个次优的解决方案感到满意。在解决方案的最优性（功效）和求解所需的工作/时间（效率）之间存在权衡。

图1-2　有效着色的三色图

假设1.3（节点标识）　每个节点都有一个唯一的标识，例如，IP地址。我们通常假设，如果系统有n个节点，每个标识只由log n位组成。

备注：

●有时我们甚至可以假设节点正好有标识1，…，n。

●很容易看出，节点标识（如假设1.3中定义的）解决了着色问题1.1，但使用n种颜色并不令人兴奋。需要多少种颜色是一个要精心研究的问题。

定义1.4（色数）　给定一个无向图G=（V，E），色数X（G）是求解问题1.1的最少颜色数。

为了更好地理解顶点着色问题，我们先来看一个简单的非分布式（集中式）顶点着色算法。

算法1.5　贪心序列

1.while存在一个未着色的顶点v do

2.　用最少的颜色（数量）给v着色，不与已经着色的邻居相冲突

3.end while

定义1.6（度）　一个顶点v的邻接数，用δ（v）表示，称为v的度。图G中的最大度顶点定义了图的度Δ（G）=Δ。

定理1.7　算法1.5是正确的，并且在n个步骤内结束。该算法最多使用Δ+1种颜色。

证明：由于每个节点最多只有Δ个邻居，所以在{1，…，Δ+1}范围内总是至少有一个颜色是空闲的。

备注：

●在定义1.11中，我们将看到什么是步骤。

●有时候，X（G）<<Δ+1。

定义1.8（同步分布式算法）　在同步分布式算法中，节点以同步轮次运行。在每一轮中，每个节点执行以下步骤。

1.向（大小合理的）图中的邻居发送消息。

2.接收消息（是同一轮的步骤1中的邻居发送的）。

3.做一些本地计算（合理的复杂度）。

备注：

●任何其他步骤排序都可以。

●在这种情况下，合理是什么意思？我们在这里有些灵活，存在不同的模型变体。一般来说，我们会处理那些只做非常简单的计算（比较、加法等）的算法。在这种情况下，指数时间计算通常被认为是有欺骗性的。同样，发送一个带节点ID或者一个值的消息被认为是可以的，而发送真正的长消息则是可疑的。我们以后需要的时候会有更确切的定义。

●我们可以建立一个算法1.5的分布式版本。

算法1.9　归约

1.假设初始时所有的节点都有ID

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

3.节点v发送它的ID给所有邻居

4.节点v接收邻居的ID

5.while节点v有一个ID较高的未着色的邻居do

6.　节点v发送“undecided”给所有邻居

7.　节点v接收从邻居过来的新决策

8.end while

9.节点v选择最小的可接受的自由颜色

10.节点v告知所有邻居它的选择

图1-10　顶点100接收到的颜色数字值可能最小

定义1.11（时间复杂度）　对于同步算法（如定义1.8），时间复杂度是指算法终止前的轮数。当最后一个节点终止时，算法终止。

定理1.12　算法1.9是正确的，并且具有时间复杂度n。该算法最多使用Δ+1种颜色。

证明：节点选择的颜色与邻居不同，没有两个邻居同时选择。在每一轮中，至少有一个节点选择一种颜色，所以我们最多在n轮之后完成。

备注：

●在最坏的情况下，这个算法仍然没有顺序算法好。

●要想出一个快速的算法似乎很难。

●也许先研究一个简单的特例——树，然后再去研究更好。