Scheduling Problems

Graph Theory · Axiom Academy

REAL WORLD Scheduling Problems How Graph Theory Solves Everyday Conflicts It's finals week at University, and the registrar has a problem: 200 students need to take 5 different exams, but many students are enrolled in multiple courses. How do you schedule these exams so that no student has two exams at the same time? Here are 5 courses. Students are enrolled in multiple courses (shown by connections). Click on a course to see which other courses have overlapping students: Each line represents students enrolled in both connected courses. These are conflicts - these exams cannot be scheduled at the same time! This is a graph coloring problem ! Each course is a vertex, and edges connect courses that conflict. The goal: assign time slots (colors) so that connected vertices never share the same color. Based on the graph above, what's the minimum number of time slots needed? Now assign time slots to each exam. Remember: courses connected by a line cannot have the same time slot! Beyond Exams: Scheduling Everywhere Graph coloring solves scheduling problems across many industries and applications: Problem: Nearby radio stations interfere if they use the same frequency. Solution: Stations are vertices, edges connect nearby stations. Colors are frequencies. Minimize frequencies needed! Problem: Multiple meetings need rooms, some have time conflicts. Solution: Meetings are vertices, edges connect overlapping times. Colors are rooms. Minimize rooms needed!

This is the written version of the interactive lesson above. See the full Graph Theory course.