数学问题与模式探求第26题 考试日程表

第26题 考试日程 　　表26-1是一个表示20个学生所参加的不同科目考试的表格，其中如果第i个学生参加第j科目的考试，那么在第i行第j列位置上写上1，否则为0。例如，学生4参加科目5、8、9三门的考试，所以在第4行中只有第5、8、9列的位置上写上1，其余皆为0。现在的问题是如何排出一张考试的日程表，每门课考一天，在日程安排中不会出现1个学生在一天中要同时参加2门或2门以上科目考试的冲突现象，并要求考试期的总天数最小。 　　：我们可以排出各种考试日程表，反复进行试验，直至找到符合上述要求的日程表。但是，如果有200个学生和20门科目，用反复试验的方法将会相当麻烦，我们必须寻找一个更好的方法。首先，我们必须设法寻找一个数学模型，将这问题转化为一个数学问题。如图26-1所示，我们把每一门科目都用一个顶点表示，故将10门科目分别用顶点v1，v2，…，v10表示。如果有任何一个学生参加某两门科目的考试，那么我们把这两门科目所对应的两个顶点用一条边联结起来。例如，学生1参加科目1、4、6的考试，那么我们把顶点v1和v4联结起来，把顶点v4和v6联结起来，把顶点v1和v6联结起来。学生2参加科目1、2、3的考试，那v1和v2，v2和v3，v1和v3之间各联结一条边，……最后共联结了20条边。如同图26-1，由一些顶点和一些边(这些边可以画成直的，也可以画成弯的，只是表示一条边的两个顶点之间有联结关系)组成的图就是“图论”中所讲的“图”。 　　因为图26-1中的任一条边都是由于某个学生参加了它所联结的两个顶点所表示的科目的考试而产生，所以图中有边联结的两个顶点所表示的科目不能在同一天考。例如，v7和v9之间的边是由于学生10既参加科目7，又参加科目9的考试，所以科目7和科目9不能在同一天考。对于相联结的两个顶点，我们着不同的颜色，表示对应的考试在不同的日期举行。为了方便起见，我们用记号□、○、△、◇和★添加在各顶点上以表示不同的颜色。在图论中，给一个图着色，就是给它的顶点分配颜色，使得有边联结的两个顶点有不同的颜色。给图着色所需颜色的最少数目，叫做该图的色数。例如，求图26-2(1)的色数。我们先给顶点v2着色□(见图26-2(2))。因为顶点v1、v4和v3都分别与v2联结，所以它们必须着上与□不同的颜色，又因为v1、v4和v3相互之间不联结，我们可以把它们着上同一种颜色○(图26-3(3))。因此，该图的色数是2。 　　现在我们已经把考试日程表问题通过图的数学模型转化为图论中求图26-1所示的图的色数问题。 　　　　 　　解：利用表26-1的信息(注意，只需要部分信息)，画出它所对应的图，并加以着色：○=｛v3，v5，v7｝，△=(v2，v4，v8)，□=｛v6，v10｝，◇=｛v1，v9｝(见图26-3)。 　　由图26-3可以看到，该图的色数为4。我们可以把着有4种颜色的顶点所对应的科目分在4天进行考试。例如，第1天考科目3、5、7；第2天考科目2、4、8；第3天考科目6、10；第4天考科目1、9。考试期是否再能缩短呢？从表26- 1可以看到第8个学生要参加科目3，4，6，9四门考试。因此，考试期的天数最少为4。 　　回顾：考试日程表的排法并不唯一。在着色时可以有不同的方法，于是，可以得到不同的解，但是，无论哪种排法考试期的最少天数总是4。例如，另一个考试日程表为 　　第1天考科目：2，6，8； 　　第2天考科目：4，7； 　　第3天考科目：3，5，10； 　　第4天考科目：1，9。 　　注：对一个图着色，多用些颜色总是可以按要求把它着好(例如n个顶点就用n种颜色)。但对一般问题，要求出“最小”的色数是很困难的，这是因为我们只能用尝试的方法来求色数，然而计算机的使用，使我们对较复杂的图也容易求出它的色数，从而使色数具有很大的实用价值。 练习26 　　1．将地图(图26-4)进行染色，两个有公共边界的国家必须染上不同的颜色，试问最少需要几种颜色？ 　　2．将图26-5中五环染色，要求有公共点的环颜色不能相同，试问最少需要几种颜色？ PAGE 5