Scheduling


Scheduling conflicts can arise in a number of ways. One example is when the members of a legislative body serve on several committees, and time slots must be found which allow all members to attend all of their committee meetings. Ideally, the number of slots is to be kept to a minimum. The conflicts are generally presented in the form of a matrix, in which the rows and columns correspond to the various committees, and an X is placed in the intersection of a row and a column if those two committees have a member in common.

One way of minimizing conflicts in scheduling is by building a certain graph and then coloring it. The graph is constructed in a simple way: There will be as many vertices as there are committees (labeled A, B, C..) and the edges of the graph will be exactly those committees that are in conflict.

Your job is, first, to construct the graph from the matrix. To add an edge click a vertex and drag the line to another vertex. Continue this process until all the conflicts have been accounted for. Once the graph is complete try to color the graph with the minimum number of colors. The New Matrix button will load a new set of conflicts.