(8)--拓展阅读：图着色的应用离散数学.doc

拓展阅读1 图着色的应用在有些实际应用中, 图的边表示关联的两个节点有冲突. 例如，化学制品储藏问题. 某公司生产n种化学制品C1, C2, , Cn，其中某些制品是互不相容的. 若它们互相接触，就会引起爆炸.作为一种预防措施，该公司希望把仓库分成若干隔间，以便把不相容的化学制品储藏在不同的隔间里. 这个仓库至少应该分成几个隔间？构造无向图G = (V, E), V=C1, C2, Cn, Ci, CjÎ E Û 化学制品Ci和Cj互不相容. 于是, 仓库的最小隔间数等于G的色数c(G).这样的例子很多. 例如，有20万个服务器的互联网公司, 每隔一段时间要部署新版本软件. 如果一次只更新一个, 会需要太长时间，于是必须同时对多台服务器进行版本更新. 由于服务器更新时需要脱机，具有共同功能的服务器不能同时更新. 这个问题可通过构造20万个节点的冲突图，再对其节点着色，具有相同颜色的节点可同时更新.在为程序变量分配寄存器时，也可用到图着色. 当变量正在使用时，数值需要保存在寄存器中. 但如果在程序执行的重叠间隔内引用了两个不同变量，就需要两个不同的寄存器. 因此寄存器分配也可用到图着色. 冲突图的构造如下：变量作为节点，如果两个变量的间隔相同，则对应的节点邻接. 图的着色数就是寄存器个数.为无限电台分配频率也可用图着色去解决. 如果两个电台的广播区域有重叠，则不能使用相同频率. 频率是珍贵和高价的，需要最小化发放数量，这就相当于找到一个图的节点着色数，这个图的节点是电台，而具有重叠区域的电台是邻接的.