第1章　顶点着色

顶点着色是一个著名的图论问题。这也是一个有用的玩具型例子，在本章中就可以看出本书的风格。顶点着色确实有不少实际应用，例如在无线网络领域，着色是TDMA MAC协议的基础。一般来说，顶点着色作为一种打破对称性的手段，这是分布式计算的主要方法之一。在本章中，我们不会真正谈论顶点着色的应用，而是抽象地讨论这个问题。在本章结束时，你可能学会有史以来最快的算法。让我们从一些简单的定义和观察开始。