下载掌阅APP，畅读海量书库
立即打开
大学的必修课都是按照学生所学专业而设定，一般一个大学生在大学四年中需要修完十几门甚至二十几门的必修课才能够毕业。这些课程之间本身可能存在着先行后续的关系，例如，高等数学一般为基础课，所以都会安排在大一时学习；而一些专业课因为需要有高等数学的基础（数学为它们的先修课程），因此可能安排在靠后的学期进行学习。本节中我们就以一个必修课排课方案为例，讨论一下如何合理高效地制定必修课的课表。
我们以计算机专业的排课方案为例进行讨论。计算机专业的学生必须在大学四年期间学习一系列课程，这些课程有些是基础课程，有些是专业课程，而这些课程之间可能存在着一定的先行后续的关系，也就是说，有些课程作为基础知识必须先修，有些课程需要学过其他必修课之后才能进行学习。表1-3中列出了计算机专业必修的一些课程以及它们之间的先行后续关系。
表1-3 计算机专业必修课
其中，第一列为课程编号，第二列为课程名称，第三列标识出这门课程的先修课编号。例如：线性代数（C2）的先修课程为微积分（C1），微积分没有先修课程。
请根据这个表格的说明安排出该学校在每个学期应该开设的课程。
如果单从这个表格来分析，要合理地排出每个学期应该开设的课程似乎不是一件容易的事情，因为课程之间存在着先后的关系，并且这种关系也并非层次分明，而是交织成网。有没有一种程式化的方法可以快速而准确地理清这些课程之间的先行后续的关系，从而合理地排出每个学期所应开设的课程呢？我们可以借助AOV网（Activity On Vertex Network）的方法处理这类问题。
把每门课程看作一个结点，结点与结点之间的有向弧表示它们之间的先后关系，例如图1-14所示：
图1-14 C1与C2的关系
该图清晰地表达了课程“线性代数（C2）”和课程“微积分（C1）”之间的关系——C2依赖于C1，即C1是C2的先修课程。用这样的表示方法将全部课程的关系表示出来就构成了计算机专业必修课的AOV网。
如何构造全部必修课程的AOV网呢？我们要以没有先修课的课程作为起点开始构造。从题目中可知，只有C1和C4没有先修课，我们就以这两门课程作为起点开始构造整个AOV网。图1-15为必修课AOV网构造-1。
图1-15 必修课AOV网构造-1
接着找出仅以C1或者C4为先修课的课程作为新的结点，并将其与C1、C4通过有向弧连接。从题目中可知C2、C3、C5、C7仅以C1或C4为先修课，C10虽然也以C1和C4为先修课，但是它也以C2为先修课，因此不符合要求。图1-16为必修课AOV网构造-2。
图1-16 必修课AOV网构造-2。
然后找出仅以C1、C4、C3、C2、C5、C7其中一个或多个结点为先修课的课程作为新的结点，并将其与前面的结点用有向弧连接。从题目中可知，C11以C3为先修课，C10以C2、C1、C4为先修课，C6以C5、C4为先修课。C8和C9不符合要求。图1-17为必修课AOV网构造-3。
图1-17 必修课AOV网构造-3
最后找出仅以C1、C4、C3、C2、C5、C7、C11、C10、C6其中一个或多个结点为先修课的课程作为新的结点，并将其与前面的结点用有向弧连接。从题目中可知，C8的先修课程为C6和C11，C9的先修课程为C6。图1-18为必修课AOV网构造-4。
图1-18 必修课AOV网构造-4
图1-18就构成了计算机专业必修课程的AOV网，每个结点都代表一门课程，结点之间的有向弧表示了课程间的先行后续的关系。
下面我们就可以依据这个AOV网排出每个学期的课程计划了。由于每个学期的课程安排必须保证本学期课程的全部先修课都已经在之前的学期中开设完毕，因此我们可以按照以下步骤部署排课方案：
（1）从AOV网中选出没有前驱的结点，把这些结点所代表的课程排在一个学期中；
（2）从AOV网中删除已排好的课程结点，连同所有以这些结点为尾的弧。
重复以上动作，直至将所有的课程排完。
按照上述的步骤，从AOV网中不断删除结点和有向弧，并将每次删除的结点排成同一学期的课程。整个过程如图1-19所示。
图1-19 从AOV网中删除结点的过程
所以，每个学期的排课计划如表1-4所示。
表1-4 计算机专业必修课排课方案
利用AOV网能够很容易实现排课方案。对于没有前驱的结点，说明这些课没有先修课程（或者其先修课程已经全部修完），因此每次将当前没有前驱的结点所代表的课程排在一个学期开设是可行的。然后从AOV网中删除这些结点，连同所有以这些结点为尾的弧也一并删除，这样余下在AOV网中又会出现新的没有前驱的结点。按照这样的方式一层一层地删除结点，并将删除的结点所代表的课程排在同一学期，直到删除AOV网中全部的结点为止。
我们在日常生活和工作中经常会遇到类似的安排工序、设计工作流程等问题。有时要完成一件事情，必须依赖于它先前的某件或某几件事情的完成，而后续的一些事情也可能会依赖当前这件事情完成的情况。遇到这样类似的问题时，我们可以借助AOV网这个工具帮助我们理清事件之间的先后关系和依赖关系，从而可以更快更合理地对每件事情做出安排。
本题目中应用到一个图论中的知识——AOV网。在管理科学中，人们常用有向图来描述和分析一项工程的具体实施过程。一项工程常被划分为若干个子工程，这些子工程被称为活动（Activity）。在有向图中若以顶点（图中的结点）表示活动，以有向边（弧）表示活动之间的先后关系，则这样的图称为AOV网。
这里需要注意一点，在AOV网中是不能出现回环的，例如图1-20表示的有向图就不是AOV网，因为在AOV网中有向边（弧）表示的是活动（图中的结点）之间的先后关系。如果存在回环就意味着某个活动要以自己为先决条件。图中V1的先决条件是V3，V3的先决条件是V6……最终V2的先决条件是V1，这样V1就以自己为先决条件，也就是说V1的发生必须在V1发生之后，这样看上去确实很荒谬。所以，我们在使用AOV网分析问题时要注意这一点。
图1-20 存在回环的有向图
利用AOV网可以帮助我们理清活动与活动之间的先后关系，从而使每件事情的先后顺序变得更加清晰明了，可以有效地提高工作效率和安排工序的合理性。