图节点着色问题：GV，E，其中VGC1，C2，C
，每一条边CiCjCiCj∈E的两个端点Ci和Cj表示某一位同学的两门考试课
程。于是考试能够安排的最少场次等于图G的色数G。由于相邻节点着不同
高校大规模考试的安排方案优化
3
f第九届华东地区大学生数学建模邀请赛论文
色，保证了不会出现考试时间冲突。构建简单无向图HV，E，其中HVD1，D2，D
，每一条边DiDjDiDj
∈E的两个端点Di和Dj表示这两门课程可以安排在同一场次考试。于是考试最少需要安排的场次等于图H的逆色数H。
显然图H是上述图G的互补图，根据定理，对求解图G色数和求解图H逆色数的结果是一样的。
图1：假设有A、B、C、D、E、F六门课，相连的两门（如A和E）表示至少一位同学这两门考试课程都要考。
图2图1的补图
图3：图2的逆着色。解为：AB可同时考，DE可同时考，CF可同时考
（3）逆着色问题的解决算法由考试安排问题按节点逆着色构建的简单无向图，其节点的度数反映了对应科目和其它科目组合到一起的难易程度。不同的考试科目对应节点的度数是不均匀分布的。根据这个特点我们采用如下算法步骤。①遍历图，找出度数大于零且度数最小的节点X。②图是否有边存在，没有则算法结束。③节点X是否与其它节点相邻，没有则转①。④找出和节点X相邻的度数最小的节点Y。⑤合并节点X和Y。⑥刷新图后转①。算法结束后图中的节点数就是图的逆着色数。
高校大规模考试的安排方案优化
4
f第九届华东地区大学生数学建模邀请赛论文
需要说明的是，该算法不能保证得到最优解：我们得到的逆着色数不一定是最少的，但该算法较为简洁有效。算法的有效性见第五部分模型检验。
（4）针对其他要求及程序实现的一些问题的说明①用程序实现算法（3）时必须注意的是合并节点X和Y的过程。我们注意到，该算法中的“节点”不一定是一个点；它可能是一个K阶完全图，K〉1（经过合并后认为是一个点了）。节点在这里定义为完全图和单一的点的并集。步骤②、③中的“相邻”实际指的是节点X与节点Y中任意两个单一点之间都有边相连。这时，X与Y一起构成一个更高阶的完全图，从而可以合并为一个新节点。这时该算法的正确性不难加以说明：以上过程可以保证每个节点中任意两个单一点间都有边相连，因此可以着同色。最后的节点数就是图的逆着色数。②由于我们只是假设用作考场的教室在大面积课程错开的前提下数量充足，故图G中任意两门大面积课程间必须人为地以边相连，否则如r