We shall have much more to say about propositional logic in Chapter 12. Exam As another example, suppose we are faced with the problem of scheduling final scheduling examinations for courses. That is, we must assign course exams to time slots so that two courses may have their exams scheduled in the same time slot only if there is no student taking both. At first, it may not be apparent how we should model this problem. One approach is to draw a circle called a node for each course and draw a line called an edge connecting two nodes if the corresponding courses have a student in common.  Given the course-conflict graph, we can solve the exam-scheduling problem by repeatedly finding and removing “maximal independent sets” from the graph.


An independent set is a collection of nodes that have no connecting edges within the Maximal collection. An independent set is maximal if no other node from the graph can be independent set added without including an edge between two nodes of the set. In terms of courses, a maximal independent set is any maximal set of courses with no common students. The set of courses corresponding to the selected maximal independent set is assigned to the first time slot.


We remove from the graph the nodes in the first maximal independent set, along with all incident edges, and then find a maximal independent set among the remaining courses. One choice for the next maximal independent set is the singleton set {CS}.