文档介绍：1 第 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门科目分别用顶点 v 1, v 2,…,v 10表示。如果有任何一个学生参加某两门科目的考试,那么我们把这两门科目所对应的两个顶点用一条边联结起来。例如,学生 1参加科目 1、4、6的考试,那么我们把顶点 v 1和v 4联结起来,把顶点 v 4和 v 6联结起来,把顶点 v 1和v 6联结起来。学生 2参加科目 1、2、3的考试, 那v 1和v 2,v 2和v 3,v 1和v 3之间各联结一条边, ……最后共联结了 20条边。如同图 26-1,由一些顶点和一些边(这些边可以画成直的,也可以画成弯的,只是表示一条边的两个顶点之间有联结关系)组成的图就是“图论”中所讲的“图”。 2 因为图 26-1中的任一条边都是由于某个学生参加了它所联结的两个顶点所表示的科目的考试而产生,所以图中有边联结的两个顶点所表示的科目不能在同一天考。例如, v 7和v 9之间的边是由于学生 10既参加科目7,又参加科目 9的考试,所以科目 7和科目 9不能在同一天考。对于相联结的两个顶点,我们着不同的颜色,表示对应的考试在不同的日期举行。为了方便起见,我们用记号□、○、△、◇和★添加在各顶点上以表示不同的颜色。在图论中,给一个图着色,就是给它的顶点分配颜色,使得有边联结的两个顶点有不同的颜色。给图着色所需颜色的最少数目,叫做该图的色数。例如,求图 26-2(1) 的色数。我们先给顶点 v 2着色□(见图 26-2(2)) 。因为顶点 v 1、v 4和v 3都分别与 v 2联结,所以它们必须着上与□不同的颜色,又因为 v 1、v 4和v 3相互之间不联结,我们可以把它们着上同一种颜色○(图26-3(3)) 。因此,该图的色数是 2。 3 现在我们已经把考试日程表问题通过图的数学模型转化为图论中求图26 -1所示的图的色数问题。解: 利用表 26-1的信息(注意,只需要部分信息),画出它所对应的图,并加以着色: ○={v 3,v 5,v 7}, △=(v 2,v 4,v 8),□={v 6,v 10}, ◇={v 1,v 9}(见图 26