Professor Chan's Band Coloring
Table of Contents
My first-year undergraduate advisor wrote a small program to save her musical camp director hours of work. Keep in mind that this was 4 years ago, so the details are a little shaky. Her musical camp director had dozens of students, and each of them was in at least 1 band. The problem he was trying to solve was assigning student bands to time slots for practicing. The issue was that students could be in multiple bands but only in one timeslot at a time.
Let's make this problem concrete. Let's say you have 9 students numbered through . Let's say you have 3 time slots 8am-9am, 9am-10am, and 10am-11am. The bands are labeled with letters . This example isn't too hard to schedule by hand, but it would be tricky if you had many more students and many more bands. A solution to this scheduling would look like: to 8am, to 9am, and to 10am. You can check that none of the students overlap in the same time slot.
Now, in comes the graph theory. We can turn this problem into a graph by letting each band be a vertex and each timeslot be a color. Let's say 8am is red, 9am is green, and 10am is blue. Here is the resulting graph:
I've drawn edges between bands that share students. The restriction of a valid coloring means that a student never has to be in the same time slot for two different bands.
This was a very elegant solution to the problem and she said that her code still runs and schedules the bands practice times to this day.