张楠　蒋海凤

摘 要：本论文介绍图染色理论，利用Welch-powell算法，解决现实生活中的调度问题，化学品的贮置问题，考试日程安排问题以及教室与课程安排问题。

关键词：图的染色；算法；调度

中图分类号：TP301.6

图的染色问题起源于著名的“四色猜想”问题，四色问题又称四色猜想、四色定理，四色定理是一个著名的数学定理，通俗的说法是：每个平面地图都可以只用四种颜色来染色，而且没有两个邻接的区域颜色相同。图的染色问题是图论的重要研究课题，它不仅具有重要的理论意义，而且具有重要的实际意义，现实生活中的一些问题可以通过图的染色理论得到很好的巧妙解决，而且算法可以在计算机上得到实现。

1 图的染色理论

图的染色问题是指给图的每个顶点（或边，或平面图的面）着色，要求相邻的结点（边或面）具有不同的颜色，并且总的颜色数尽可能少。定义1：对图G的结点着色，是指对G的每个结点指定一种颜色，使得相邻结点有不同的颜色；若用K种颜色给G的结点着色，称图 是点 色可染的；若G是K可着色的，但不是K-1可着色的，则称G是K-色的或K色图，称K是G的色数，记为χ（G）。χ（G）是使G是K着色的最小的K。定义2：对图G的边着色，是指对G的每条边指定一种颜色，使得相邻的边具有不同的颜色；若用K种给G的边着色，則称G是K边可着色的；若G是K边可着色的，但不是边K-1可着色的，则称G是边K可着色的，称K是G的边色数，记为χ（G）。

Welch-powell算法在实际应用中很有效，这种算法适合于颜色数比较少的结点着色方法。……