用图的着色方法解决排课冲突问题

Based Graph Colouring

图的着色问题已被证明为NP问题。将排课表冲突问题转化为图的着色问题,对图的邻接矩阵中0元素所在的行和列进行叠加,得到图的一个划分的邻接矩阵。重复上述叠加使得邻接矩阵中没有0元素,最终得到的图的划分即是合理的课程安排。

It is proved that the vertex colouring is NP-problem. The conflict of curriculum schedules＇ arrangement can be trans- formed into the vertex colouring problem. Adjacency matrix of the graph＇s partition can be obtained by superimposing the row and column of adjacency matrix 0 element. Repeating the above process, no 0 element is contained in the matrix, finally the graph＇s partition will be a reasonable curriculum schedules＇ arrangement.