Saturday, January 03, 2009

Efficient Finals

Well I was reading an algorithms book and here is something that was pointed out that I never considered before.

Assigning times for Final Exams is equivalent to coloring a map.

How so? Well assume that we only have the following restriction, two finals can not be at the same time if they share at least one student. Now let the classes be the vertices of the graph, and place an edge between any two vertices if they share a student. So basically you assign colors (or times) in a way such that no edge has vertices of the same color.

Obviously the four color theorem does not apply when coloring this graph. Just consider the case where a student is taking 5 classes. (go and look up to see how this breaks the necessary assumptions for the theorem). None the less it is still an interesting connection, though I am sure Universities do not use this method to schedule their finals (for some obvious reasons).

No comments: