57图着色.pptVIP

第五章 图论;例3 完全偶图Km,n的色数是什么？其中m和n都是正整数。 解 需要的颜色数似乎依赖于m和n。不过，仅需要两种颜色。用一种颜色着色m个顶点，而用另一种颜色着色n个顶点。因为边都是只能连接m个顶点中的一个顶点与n个顶点中的一个顶点，所以没有相邻的地点具有相同的颜色。 例5 如何安排一所大学里的期末考试，使得没有学生在同一时间有两门考试？ 解 这样的安排问题可以用图模型来解决，用顶点表示课程，若在两个顶点所表示的课程里有公共的学生，则在这两点之间有边。用不同颜色来表示期末考试的每个时间段。考试的安排就对应于所关联的图的着色。 例如，假定要安排七门期末考试。假定课程编号为1到7。假定下列成对的课程有公共的学生：1和2，1和3，1和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6，3和7，4和5，4和6，5和6，5和7，以及6和7。在???7-85里显示这组课程所关联的图。一种安排就是由这个图的一种着色来组成的。 （接下页） ;（接上页） 因为这个图的色数为4，所以需要4个时间段。在图7-86中显示使用了4种颜色的这个图的着色以及所关联的安排。 例7 变址寄存器 在有效的编译器里，当把频繁地使用的变量暂时地保存在中央处理单元而不是保存在常规内存时，可以加速循环的执行。对于给定的循环来说，需要多少个变址寄存器？可以用图着色模型来讨论这个问题。为了建立这个模型，设图的每个顶点表示循环里的一个变量。若再循环执行期间两个顶点所表示的变量必须同时保存在变址寄存器里，则在这两个顶点之间有边。所以，这个图的色数就给出所需要的变址寄存器数，因为当表示变量的定点在图中相邻时，就必须给这些变量分配不同的寄存器。