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

Based Graph Colouring

作　　者：安卫钢[1] 白艳萍[2] 

机构地区：[1]中北大学信息商务学院,030051 [2]中北大学应用数学系,030051

出　　处：《微计算机信息》2012年第10期252-253,共2页Control & Automation

基　　金：基金申请人:白艳萍;基金资助项目名称:人工神经网络在模式识别中的应用;基金颁发部门:山西省自然科学研究基金委;基金编号:2009年山西省自然科学研究基金(2009011018-3)

摘　　要：图的着色问题已被证明为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.

关 键 词：顶点着色 邻接矩阵 排课 划分 

分 类 号：TP15[自动化与计算机技术—控制理论与控制工程]