数学建模着色问题.ppt

一、着色模型 物资储存问题 时间表问题 着色方法 最大度数优先的Welsh - Powell算法 * * 已知图G = (V, E ),对图G的所有顶点进行着色时,要求相邻的两顶点的颜色不一样,问至少需要几种颜色? 这就是所谓的顶点着色问题. 若对图G的所有边进行着色时,要求相邻的两条边的颜色不一样,问至少需要几种颜色? 这就是所谓的边着色问题. 这些问题的提出是有实际背景的.值得注意的是,着色模型中的图是无向图.对于顶点着色问题,若是有限图,也可按第一节所述的方法转化为有限简单图.而边着色问题可以转化为顶点着色问题. 一家公司制造n种化学制品 A1, A2, … , An ,其中有些化学制品若放在一起则可能产生危险,如引发爆炸或产生毒气等,称这样的化学制品是不相容的.为安全起见,在储存这些化学制品时,不相容的不能放在同一储存室内.问至少需要多少个储存室才能存放这种化学制品? 今作图G,用顶点v1,v2,… ,vn 分别表示n种化学制品,顶点vi与vj相邻,当且仅当化学制品Ai与Aj 不相容. 于是储存问题就化为对图G的顶点着色问题,对图G的顶点最少着色数目便是最少需要的储存室数. 现有m个工作人员x1, x2, … , xm ,操作n种设备y1, y2, … , yn . 设工作人员xi使用设备yj的时间为aij , 假定使用的时间均以单位时间计算,矩阵A= (aij )m×n称为工作要求矩阵. 假定每一个工作人员在同一时间只能使用一种设备, 某一种设备在同一时间里只能为一个工作人员所使用. 问应如何合理安排, 使得在尽可能短时间里满足工作人员的要求? 和前面讲的匹配问题类似, 问题转为讨论关于X ={x1, x2, … , xm},Y ={ y1, y2, … , yn }的二部图G = ( X, Y, E ). 工作人员xi使用设备yj的每单位时间对应一条从 xi到 yj 的边,这样所得的二部图G过 xi 到 yj 的边可能不止一条. 问题变为对所得的二部图G的边着色问题,有相同的颜色的边可以安排在同一时间里. 由于二部图的特殊性,二部图G =(X, Y, E)的边着色问题有有效算法：将G 的一个最大匹配M中的边着同一种颜色,然后令G = (X,Y,E\M)重复. 对图G =(V, E )的顶点进行着色所需最少的颜色数目用?(G )表示,称为图G的色数. 定理 若图G =(V, E ),d = max{d(v )|v∈V }, 则?(G )≤d + 1. 这个定理给出了色数的上界.着色算法目前还没有找到有效算法,下面给出一种近似算法--最大度数优先的Welsh - Powell算法. 这个算法给出了一个较好的着色方法,但不是最有效的方法, 即所用的颜色数不一定是最少的. 设G =(V, E ),V ={v1, v2, … , vn },且不妨假设 d(v1)≥d(v2)≥…≥d(vn). c1, c2, … , cn为n种不同的颜色. ① 令有序集Ci ={c1, c2, … , ci},i =1, 2, … , n . j = 1.转向②. ② 给vj 着Cj 的第一个颜色Cj 1.若 j = n 时,停; 否则,转向③. ③ ?k＞j ,若vk 和vj 相邻,则令Ck = Ck\{Cj 1}. j = j + 1,转向②. 例: