1.2 图的独立集应用

问题描述 各大学教务处每学期临近结束时，都需要根据各任课老师任课计划和学生选课情况，再结合教室资源情况安排下一学期的课程及上课时间和地点.表1.2所示是某大学电信学院的大三各专业部分课程情况.该学院每届学生按专业分班，统一选课.另外，学院只有一间普通机房和一间高级机房.那么应该如何合理地安排这些课程呢?

思路分析 一般来说，在大学里，每学期任课老师都有一定工作量的要求，往往可能要上不止一门课程，或同一门课程有多个教学班，而每位同学需要在学期内完成若干门课程的学习（但受专业限制，同专业所选课程差异较小），因此我们在安排上课时间时一定要保证同一位老师教授的任意两门课程和同一专业的学生学习的任意两门课程不可排在同一时间.另外，对于某些对上课设施有特殊要求的课程，也不可以安排在同一时间，因为特殊设施资源是非常有限的，比如机房、球场等.由于受到教室数量的限制，在同一时段无法安排数量超过教室数量的课程.另外，为了方便开展一些全校性的活动，我们希望有些时段可以不安排课程，所以在安排课程时希望上课的时段尽量少.

模型建立 基于这一要求，我们可以构造图1.13所示的示意图.以每个课程为顶点，两个顶点连一条边，当且仅当两门课程的任课老师为同一人，或有学生同时选了这两门课，或上课教室冲突.那么一个合理的课程安排就是将图中的点进行分化，使得每一个部分里的点都两两不相连.我们把这一划分的过程可以看成是对图的顶点着色，使得相连的两个顶点颜色不一样，这样每一个色部里的点都是两两不相连的，也就是一个独立集.这样每一色部里的点所代表的课程就可以安排在同一个时间段了.在本例中，我们用字母a,b,c,d,e,f,g按序表示上述7门课，得到图1.13.我们寻找划分的主要方法是通过极小覆盖找出图中的极大独立集，然后删去该极大独立集，在剩下的图中找出极大独立集，直到剩下的图为一个独立集.这样，每次得到的独立集就可以作为划分的一部分.由于教室数量有限，如果得到的独立集较大，则可以再进一步划分，以便不超过教室的数量上限.

在本例中，我们可以用代数方法找出一个划分.图1.13中的点表示课程，两点之间的连线则说明这两门课程冲突，不能安排在同一时段.

模型求解 为了得到极小覆盖，对于任意顶点v，选择v或者选择所有邻点.为了有效地执行这个程序，我们利用代数方法.首先把选择顶点v这个指令简记为符号v，随后对给定的指令X和Y，指令“X或Y”和“X与Y”分别记为X+Y（逻辑和）和XY（逻辑积）.例如，指令“选择u与v，或者选择v与w”记为uv+vw.根据逻辑运算规则，我们可以得到

（uv+vw）（u+vx）=uvu+uvvx+vwu+vwvx.

现在考察本例中的图，我们的指令用于求极小覆盖时就是

（a+bd）（b+aceg）（c+bdef）（d+aceg）（e+bcdf）（f+ceg）（g+bdf），

上式可化简为

aceg+bcegd+bdef+bcdf，

换言之，选择a、c、e与g，或者b、c、d、e与g，或者b、d、e与f，或者b、c、d与f.因此{a,c,e,g},{b,c,d,e,g},{b,d,e,f}和{b,c,d,f}是G的极小覆盖.取其补集，得到G的所有极大独立集{b,d,f},{a,f},{a,c,g}和{a,e,g}.我们可以任选一个极大独立集作为划分的第1部分，再用同样的方法求去掉该独立集的图中的极大独立集，选取某一个作为划分的第2部分，这样进行下去，我们就得到一个完整的划分（{b,d,f},{a,e,g},{c}）.在这样的划分下，这些课可以分为3个时段，第1时段的3门课程b,d,f，第2时段的3门课程a,e,g和第3时段的1门课程c.

注意，本模型中所用的求划分的办法本质上来讲是一种枚举法，在求极小覆盖的过程中用的逻辑运算方法的效率受到图的顶点数目的影响，因此本方法只适用于顶点数较少的图.对于顶点数目较多的图，尚无高效的划分数最少的划分方法.